巩固树和二叉树的相关知识，特别是二叉树的相关内容。学会运用灵活应用。

1.回树和二叉树的逻辑结构和存储方法，清楚掌握树和二叉树的遍历操作。

2.学习树的相关知识来解决实际问题。

3.进一步巩固程序调试方法。

4.进一步巩固模板程序设计。

实验内容

1.自己设计一个二叉树，深度最少为4，请递归算法分别用前序、中序、后序遍历输出树结点。

1.头文件：Bitree.h

#ifndef Bitree_h
#define Bitree_h
template<class T>
struct BTnode
{
T data;
BTnode<T>*lchild,*rchild;
};
template<class T>
class Bitree
{
public:
Bitree(){ root = create(root); }
~Bitree(){ release(root); }
void preorder(){ preorder(root); }
void inorder(){ inorder(root); }
void postorder(){ postorder(root); }
private:
BTnode<T> *root;
BTnode<T> *create(BTnode<T>*bt);
void release(BTnode<T>*bt);
void preorder(BTnode<T>*bt);
void inorder(BTnode<T>*bt);
void postorder(BTnode<T>*bt);
};
template<class T>
BTnode<T> *Bitree<T>::create(BTnode<T> *bt) //构造函数
{
char ch;
cout << "输入创建二叉树的结点数据：";
cin >> ch;
if (ch == '#' || ch == '*') return NULL;
else
{
bt = new BTnode<T>;
bt->data = ch;
bt->lchild = create(bt->lchild);
bt->rchild = create(bt->rchild);
}
return bt;
}

template<class T>
void Bitree<T>::preorder(BTnode<T> *bt)//前序遍历
{
if (bt == NULL) return;
else
{
cout << bt->data;
preorder(bt->lchild);
preorder(bt->rchild);
}
}
template<class T>
void Bitree<T>::inorder(BTnode<T> *bt) //中序遍历
{
if (bt == NULL) return;
else
{
inorder(bt->lchild);
cout << bt->data;
inorder(bt->rchild);
}
}
template<class T>
void Bitree<T>::postorder(BTnode<T> *bt) //后序遍历
{
if (bt == NULL) return;
else
{
postorder(bt->lchild);
postorder(bt->rchild);
cout << bt->data;
}
}
template < class T >
void Bitree<T>::release(BTnode<T> *bt) //析构函数
{
if (bt != NULL)
{
release(bt->lchild);
release(bt->rchild);
delete bt;
}
}
#endif

2.源文件.cpp

#include<iostream>
#include"Bitree.h"
#include<stdlib.h>
using namespace std;
int main()
{
cout << "创建一棵二叉树：" << endl;
Bitree<char> T;
int choose = 0;
system("pause");
system("cls");
while (1)
{
cout << "(1).前序遍历" << endl;
cout << "(2).中序遍历" << endl;
cout << "(3).后序遍历" << endl;
cout << "(0).退出" << endl;
cout << "请输入相应的功能编号：";
cin >> choose;
if (choose == 0) break;
switch (choose)
{
case 1:
cout << "前序遍历的结果是：";
T.preorder();
cout << endl;
break;
case 2:
cout << "中序遍历的结果是：";
T.inorder();
cout << endl;
break;
case 3:
cout << "后序遍历的结果是：";
T.postorder();
cout << endl; break;
default:
break;
}
}
system("pause");
return 0;
}