二叉树的建立和遍历实验报告

1、实验4二叉树的构建和遍历大学专科班学号的名字一.实习目的1.掌握二进制列表的存储结构。2.掌握二进制列表的建立。3.确定二叉树的第一次序遍历、中间序遍历、下一次序遍历的递归算法；掌握二叉树遍历算法的应用。二.实践内容1.二进制树的二进制树二进制列表(算法6.4)(空树显示为#)2.生成的二进制树的第一次顺序遍历，中间顺序遍历，最后顺序遍历，结果输出。统计二叉树中的节点数。找到二叉树的高度。三.实验阶段1.定义二进制列表的存储结构# include“stdio . h”# include“stlib . h”Typedef char TElemTypeTypedef struct BiTNode

2、TElemType dataStruct BiTNode *lchild，* rchild/左右儿童指针BiTNode，* BiTree2.写入函数CreateBiTree，以第一顺序写入二进位树状结构的二进位清单；测试的字符序列为abdg # # # e # # c# f # #；是程序代码如下：Void CreateBiTree(BiTree T)/算法6.4:按照第一个顺序输入二进制树的节点值(文字或整数，可以在主路径中定义)，以配置二进制链接表表示的二进制树t。将空树标记为#TElemType chScanf(%c ，ch)；If(ch=#) /nullt=空；Elset=(bi tr

3、ee)malloc(size of(bitnode)；/创建根节点If(！t)exit(-1)；t-data=ch；create bitree(T-lchild)；/递归配置左侧子树create bitree(T-rchild)；/组织右侧的子树2.为二进制树的第一次顺序遍历、中间顺序遍历和下一次顺序遍历编写递归算法Int preOrderTraverse(BiTree T)/初始条件：二叉树t存在，第一个迭代遍历t；if(T=NULL)return 1；If(T)！=NULL) /T非空printf( ，T-data)；/访问根节点preorder traverse(T-lchild)；/依

4、次导航左侧的子树preorder traverse(T-rchild)；/依次导航右侧的子树Int inOrderTraverse(BiTree T)/初始条件：二叉树t存在，中间迭代遍历t；if(T=NULL)return 1；If(T)！=NULL) /T非空inorder traverse(T-lchild)；/遍历中间顺序左侧的子树printf(“”，T-data)；/访问根节点inorder traverse(T-rchild)；/遍历中间顺序右侧的子树Int postOrderTraverse(BiTree T)/初始条件：具有二进制树t。/工作结果：递归遍历t；if(T=NULL

5、)return 1；If(T)！=NULL) /T非空postor der traverse(T-lchild)；/依次导航左侧的子树postor der traverse(T-rchild)；/以下顺序通过右侧子树printf(“”，T-data)；/访问根节点编写计算二叉树中节点数的函数。(遍历算法)Int countND(BiTree T)int n=0，k=0，m=0；If(T=NULL)return 0；Elseif(T-lchild)！=NULL)k=count nd(T-lchild)；/依次导航左侧的子树以获取左侧的子树节点数If(T-rchild)！=NULL)m=count

6、 nd(T-rchild)；/依次导航右侧的子树n=m k 1；return n；编写查找二叉树高度的函数。Int Bitheight(BiTree T)int lh，rh，th；if(T=NULL)return 0；LH=Bitheight(T-lchild)；/t递归查找左侧子树的高度LHRH=Bitheight(T-rchild)；/t右侧子树的高度RH递归if(lhrrh)th=lh1；else th=RH 1；Return th4.编写main函数、调用函数、输出结构Void main()Int i、k、h；BiTree T；Printf(首先输入“二进制树”(例如，ab#是根节点，b是左侧子树的二进制树) n )；create bitree(T)；Printf(第一次遍历结果如下： n )；I=preorder traverse(T)；printf(“ n”)；Printf(中间顺序遍历结果如下： n )；I=inorder traverse(T)；printf(“ n”)；Printf(后置遍历结果如下： n )；I=postor der traverse(T)；printf(“ n”)；k=count nd(T)；Printf(“节点数%dn”，k)。h=Bitheight(T)；Pri