• 实验八：二叉树的创建于应用(2课时）

树和二叉树是应用极为广泛的数据结构，也是这门课程的重点。本次实验将操作进一步集中在遍历操作上，因为遍历操作是其他众多操作的基础。 

 （一）问题描述 很多涉及二叉树操作的算法都是以遍历操作为基础的。试写一程序，实现对二叉树的遍历。 1．分别用三种递归方法：先序、中序和后序。

 2．利用队列按层次遍历。注意正确使用队列中的定义和函数。 其实，二叉树也可以实现非递归的遍历，有兴趣的可以试着写写，书上有中序非递归遍历算法。 

 （二）基本要求 

 1．用二叉链表的形式存储一棵二叉树，见书上Create（）函数。 注意输入先序前必须补齐空的结点，可用 # 号补齐。 

 2． 分别用三种递归方法：先序、中序和后序输出结果。 利用队列按层次遍历。注意正确使用队列中的定义和函数 

 （三）测试数据 请至少准备3棵不同形态二叉树进行测试。 可自拟，也可采用书上的。 

 （四）实现提示 二叉树的建树过程参照131页算法6.4，下图的二叉树，输入的先序序列应为 abd##e#g##cf###，而不是abdegcf。

 （五）拓展学习：1．求二叉树的层次（高度） 2．求二叉树的叶子个数 3．求二叉树的总结点个数；

至少选择一个实现。

按要求提交实验报告。

以下是参考代码:

int level(BiTree T) /*计算二叉树的层次*/

{

 int l1,l2;

 if(T==NULL) return 0;

 else{l1=level(T->lchild);

      l2=level(T->rchild);

      return l1>l2?l1+1:l2+1;

 }

}

 

二叉树创建（实践)