简单的二叉树的操作代码

Question

1.实现二叉树的2种构造方法（输入扩展二叉树的前序遍历序列构造二叉树和已知二叉树的前序、中序序列，构造此二叉树）

2．对二叉树进行前序、中序、后序和层次遍历；

4．求二叉树结点数、叶子结点和高度；

5．将二叉树所有结点的左右子树交换。

 

Answer 1

#include"iostream.h"
#include"erchashu.h"
//先序创建一个树
void CreatTree(BiTree &T)
{
           elemtype ch;
           cin>>ch;
			   if(ch == '#')
            T = NULL;
           else
           {
                     if(!(T = new BiNode))//分配内存空间失败就退出
                                exit(0);
                      T->data = ch;
                      CreatTree(T->lchild);
                      CreatTree(T->rchild);
		   }
           
}
 
//先序遍历
void PreOrderTree(BiTree T)
{
           if(T)
           {
                      cout<<T->data;
                      PreOrderTree(T->lchild);
                      PreOrderTree(T->rchild);
           }
}
//中序遍历
void InOrderTree(BiTree T)
{
           if(T)
           {
                      InOrderTree(T->lchild);
                      cout<<T->data;
                      InOrderTree(T->rchild);
           }
}
//后序遍历
void LastOrderTree(BiTree T)
{
           if(T)
           {
                      LastOrderTree(T->lchild);
                      LastOrderTree(T->rchild);
                      cout<<T->data;
           }
}
//层次遍历
void LevOrderTree(BiTree T)
{
           BiTree temp[NUM];///开辟一个数组，用于按层次存放结点
           int i,j,t;
           if(T)
                      temp[0] = T;
           i=0; j=0;//j 是计算有几个结点
           while (temp[i] && i<=j)
           {//本来以0开始计数，现在全部为1
                      if(temp[i]->lchild)
                      {//递归左子树
                                 j++;
                                 temp[j] = temp[i]->lchild;
                      }
                      if(temp[i] ->rchild)
                      {//递归右子树
                                 j++;
                                 temp[j] = temp[i]->rchild;
                      }
                      i++;
           }
		   //结点全部都在这个数组里面
           for(t=0;t<=j;t++)
            cout<<temp[t]->data;
}
//计算深度
int Depth(BiTree T)
{
           if(T == NULL)
                      return 0;
           else
           {
                      int m = Depth(T->lchild);
                      int n = Depth(T->rchild);
                      return (m>n?m:n)+1;
           }
}
//计算结点个数
int NodeCount(BiTree T)
{
           if(T == NULL)
                      return 0;
           else
			   return NodeCount(T->lchild)+NodeCount(T->rchild)+1;
}
//计算叶子结点
int LeafCount(BiTree T)
{
           if(T==NULL)
                      return 1;
           
           else
                      return LeafCount(T->lchild)+LeafCount(T->rchild);
}
 
//交换左右子树
void Swapchild(BiTree T)
{
    BiTree t;
    if(T)
    {
        t=T->lchild;
        T->lchild=T->rchild;
        T->rchild=t;
        //交换左右子树的指针
 
        Swapchild(T->lchild);
        Swapchild(T->rchild);
    }
 
}
 
//主函数
int main()
{
	       char e;
		   char nil='#';//
		   cout<<"欢迎使用本程序！"<<endl;
           cout<<"按先序输入一个二叉树（#结束）：";
           BiTree Tre;
           CreatTree(Tre);
 
           cout<<"先序遍历结果为：";
           PreOrderTree(Tre);
           cout<<endl;
 
           cout<<"中序遍历结果为：";
           InOrderTree(Tre);
           cout<<endl;
 
           cout<<"后序遍历结果为：";
           LastOrderTree(Tre);
           cout<<endl;
 
           cout<<"层次遍历结果为：";
           LevOrderTree(Tre);
           cout<<endl;
           
           cout<<"二叉树的高度:"<<Depth(Tre)<<endl;
           
           cout<<"二叉树的结点数:"<<NodeCount(Tre)<<endl;
           
           cout<<"二叉树的叶子结点数:"<<LeafCount(Tre)/2<<endl;
 
		   cout<<"二叉树的左右子树交换后的结果为："<<endl;
		   Swapchild(Tre);
           cout<<"先序遍历结果为：";
           PreOrderTree(Tre);
           cout<<endl;
 
           cout<<"中序遍历结果为：";
           InOrderTree(Tre);
           cout<<endl;
 
           cout<<"后序遍历结果为：";
           LastOrderTree(Tre);
           cout<<endl;
 
           cout<<"层次遍历结果为：";
           LevOrderTree(Tre);
           cout<<endl;
 
           return 0;
}