实验三：二叉树的基本操作

 

一．实验内容：实现创建和遍历二叉树的基本操作

二．实验目的：

（1）掌握二叉树的定义和存储表示，学会建立一棵特定二叉树的方法；

（2）掌握二叉树的遍历算法（先序、中序、后序遍历算法）的思想，并学会遍历算法的递归实现和非递归实现。

三．问题描述： 

（1）编程实现构造一棵二叉树的算法，适合任意合法输入的二叉树的建立，并进行相应异常处理。

（2）编程实现在二叉链表这种存储方式下，实现二叉的遍历，可采用递归或者非递归实现，遍历算法可在先序、中序和后序遍历算法中任选其一。

四．问题的实现

（1）二叉树的二叉链表存储表示

typedef struct BiTNode      

{

  char data;

  struct BiTNode *lchild,*rchild;   //指向该结点的左右孩子指针

}BiTNode,*BiTree;

（2）主要的实现思路：

a.首先定义二叉树的存储形式，这里使用了二叉链表

b.用CreateBiTree(T)构造二叉链表表示的二叉树T，并用i和n来记录和控制当前输入的结点个数

c.用InorderTraverse(T)遍历该二叉树

 

五．总结

这个小程序很基本，但是只能按先序次序输入合法的结点的值。像这样的输入就不行：

明明已经超过了结点的个数，但还是继续运行

 

正确的运行结果：

 

 

 

附：主要源程序代码（包含程序备注）

 

int i=1;//全局变量，用来记录结点的个数

 

typedef struct BiTNode

{

     char data;

     struct BiTNode *lchild,*rchild; //指向该结点的左右孩子指针

}BiTNode,*BiTree;

 

 

BiTree CreateBiTree(BiTree &T)     //构造二叉链表表示的二叉树T

{

     char ch;

  

     cout<<"第"<<i<<"个结点：";

     cin>>ch;

     if(ch=='#')  // #表示空树

     {

         T=NULL;

     }

     else

     {

        

          T=(BiTNode*)malloc(sizeof(BiTNode));

          if(!T)

           {

              cout<<"内存分配失败！"<<endl;

              return 0;

           }

          else

          {

              i=i+1;

              T->data=ch;

              CreateBiTree(T->lchild);

              CreateBiTree(T->rchild);

          }

     }

     return T;

}

 

void visit(char ch)

{

     cout<<ch<<endl;

}

 

void InorderTraverse(BiTree T)

{

     if(T)

     {

        

         InorderTraverse(T->lchild);//访问左子树

         visit(T->data);//访问根结点

         InorderTraverse(T->rchild);//访问右子树

     }

}

 

 

void main()

{

 

     int n;  

     BiTree T;

     cout<<"请输入结点个数"<<endl;

     cin>>n;

     cout<<"按先序次序输入二叉树中结点的值（一个字符），#表示空树"<<endl; 

    while(i<=n)

     {

      T=CreateBiTree(T);

     }

      cout<<"下面进行中序遍历"<<endl;

      InorderTraverse(T);

    

     system("pause");

 

 

}