实验项目：二叉树的建立和遍历操作根据实验内容描述需求分析：用二叉链表作为存储结构，完成二叉树的建立，前序、中序和后序遍历的操作，求所有
叶子及结点总数的操作等。（1）输入的形式和输出值的范围：ElemType（2）输出的形式：若左子树不空，则输入左子树；若右子树
不空，则输入右子树（3）程序所能达到的功能：利用前序遍历、中序遍历、后序遍历所建二叉树。（4）测试数据：包括正确的输入输出结果
和错误的输入及输出结果。Abdg!!!e!!C!f!!;2、数据结构定义：对用到的数据结构进行定义，具体包括：（1）确定数据对象
及结构：二叉树是n个有限元素的集合，该集合或者为空、或者由一个称为根（root）的元素及两个不相交的、被分别称为左子树和右子树的二
叉树组成，是有序树。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个结点（2）存储结构的选择和定义：用二叉链表作
链式存储结构可以用以下程序来定义：#include“stdio.h”#include“stdlib.h”Typedefch
arTElemTypetypedefstructBiTNode{TElemTypedata；StructBiTNode
lchild，rchild；//左右孩子指针}BiTNode,BiTree(BiTree&T);3.主程序的流程及各程序
模块之间的调用关系。（1）根据实验内容确定需要实现的全部函数。voidCreateBiTree(BiTree&T)//二叉树的
创建intcountND(BiTreeT)//二叉树结点个数的统计intpreOrderTraverse(BiTreeT)
//先序遍历intBitheight（BiTreeT）//二叉树的深度计算（2）要求给出主程序的调用流程图4、程序实现：//先
序次序的代码，构造二叉链表表示的二叉树T。以！表示空树voidCreateBiTree(BiTree&T)TElemTy
pech;scanf(“%c”,&ch);if(ch==’！’)//空T=NULL;else{T=(BiTree)malloc
(sizeof(BiTNode));if(!T)exit(-1);T->data=ch;CreateBiTree(T->l
child);CreateBitree(T->rchild);}}//编写二叉树的先序遍历，中序遍历，后序遍历的递归算法intp
reOrderTraverse(BiTreeT){//初始条件：二叉树T存在，递归遍历T；if(T==NULL)return1
;if(T!=NULL)//T不空{printf(“%5c”,T->data);访问根节点preOrderTraverse(T->
lchild);//先序遍历左子树preOrderTraverse（T->rchild）;}}intinOrderTravers
e(BiTreeT){//初始条件：二叉树T存在，中序递归遍历T；if（T==NULL）return1；if（T!=
NULL）//T不空{inOrderTraverse(T->lchild);//中序遍历左子树printf（“%5c”，T->da
ta）;inOrderTraverse(T->rchild);//中序遍历右子树}}intpostOrderTraverse（B
iTreeT）{//初始条件：二叉树T存在//操作结果：后序递归遍历T;if(T==NULL)return1;if(T！=
NULL)//T不空{postOrderTraverse(T->lchild);//后序遍历左子树postOrderTrav
erse(T->rchild);//后序遍历右子树printf(“%5c”,T->data);//访问根结点}}//编写函数
统计二叉树中结点个数：（遍历算法）intcountND(BiTreeT){intn=0,k=0,m=0;
if(T==NULL)return0;else{if(T->lchild!=NULL)k=countND
(T->lchild);//后序遍历左子树，得到左子树结点个数if(T->rchild!=NULL)m=countND(T-
>rchild);n=m+k+1;}returnn;}//编写函数求二叉树的高度：intBitheight（BiTr
eeT）{intlh,rh,th;if(T==NULL)return0;lh=Bitheight(T->lchil
d);//递归求T的左子树高度lhrh=Bitheight(T->rchild);if(lh>rh)th=lh+1;
returnth;}//编写main函数，调用函数，输出结构voidmain（）{inti,j,k;BiTreeT;
printf(“请按先序输入二叉树\n”);CreateBiTree(T);print(“先序遍历的结果为：\n”);i=
preOrderTraverse(T);printf(“\n”);printf(“中序遍历的结果为：\n”);i=inOrderT
raverse(T);printf(“\n”);printf(“后序遍历的结果为：\n”);i=postOrderTraverse
(T);printf(“\n”);k=countND(T);printf(“结点个数为%d\n”,k);h=Bitheight(T
);printf(“输出树的高度为%d\n”,h);h=Bitheight(T);printf(“输出树的高度为%d\n”,h);
}5、调试分析：（1）所遇问题：问题一：遍历的时候根据遍历类型的不同来导致左右孩子的输出顺序不同，同样使用了迭代方法。问题二：输出
时只有第一个结点的数据输出来了，其他的没有输出出来问题三：刚开始程序写的侧重点是数据且只是整形数据（输入字符串等其他类型并不能输出
，原因是开始设置的输入类型是char后来改成ElemType）（2）算法的时空分析：BitTreeCreateLink()//
二叉树的创建O(1)intGetTreeDeep(BiTreeT)//计算二叉树的深度O(1)voidInOrder(
BiTreeT)//中序遍历O(1)voidPostOrder(BiTreeT)//后序遍历O(1)StatusCre
ateBiTree(BiTree&T)//初始化遍历O(1)6、运行结果：第一组：第二组：第三组：7、总结：对二叉树基本概念的理解是对这种模型的一个最基本的认识，从使用递归的调用到前中后序的遍历都用到了算法的分析操作，不仅如此，输入输出的格式要求也要严格遵循，否则就会报错无法正常输出 |
|
