二叉树的存贮与遍历.doc

数据结构课程实验报告学号：姓名： 实验日期： 实验名称：二叉树的存贮与遍历一、实验目的掌握二叉树结构的非线性和递归性特点，以及用指针类型描述和访问二叉树的运算。二、实验内容与实验步骤问题描述：建立任意二叉树的二叉链表存储，并对其进行先序、中序、后序遍历，求出叶子结点和总结点数目。(有能力的同学加上层次遍历)基本要求：采用二叉链表作为存储结构，以加入虚结点的先序序列输人建立该二叉树的存储，并设菜单，依据选项分别输出该二叉树的先序、中序、后序和层次遍历序列及叶子结点和总结点数目、二叉树的深度。二叉树结点的数据域可采用字符。 （用菜单形式）ABDCFAE测试数据：建立如图所示的二叉树存储。建立时的输入序则为：ABD000CE00F00,测试先序、中序、后序、层次遍历的结果以及叶子结点和总结点数目。提示：用递归方式实现建立、先序遍历、中序遍历和后序遍历，用队列实现层次遍历，求叶子结点和总结点数目时，可采用任何一种遍历方法来实现，只是加入一个计数器，当遍历到某个结点时对其进行判断，若符合条件，则将计数器加1，最后输出计数器的值。 三、附录： #include#includeint count=0,count1=0;typedef struct node char ch; struct node *Lchild; struct node *Rchild;Bitnode;Bitnode* CreateBtree() char a; Bitnode *bt=NULL; scanf(%c,&a); if(a!=#) if(a=0) bt=NULL; else bt=(Bitnode *)malloc(sizeof(Bitnode); bt-ch=a; bt-Lchild =CreateBtree(); bt-Rchild =CreateBtree(); return bt;void DLR(Bitnode *bt) if(bt!=NULL) printf(%c,bt-ch); DLR(bt-Lchild); DLR(bt-Rchild); void LDR(Bitnode *bt) if(bt!=NULL) LDR(bt-Lchild); printf(%c,bt-ch); LDR(bt-Rchild); void LRD(Bitnode *bt) if(bt!=NULL) LRD(bt-Lchild); LRD(bt-Rchild); printf(%c,bt-ch); int leafcount(Bitnode *bt) if(bt!=NULL) leafcount(bt-Lchild ); leafcount(bt-Rchild ); if(bt-Lchild =NULL&bt-Rchild =NULL) count+; return count;int btcount(Bitnode *bt) if(bt!=NULL) btcount(bt-Lchild ); btcount(bt-Rchild ); count1+; return count1;int TreeDepth(Bitnode *bt ) int hl,hr,max,x; if(bt!=NULL) hl=TreeDepth(bt-Lchild ); hr=TreeDepth(bt-Rchild ); max=hlhr?hl:hr; x=max+1; else x=0; return x;void main() Bitnode *t; int n; do printf(*n); printf(*1、二叉表存储*n); printf(*2、先序遍历*n); printf(*3、中序遍历*n); printf(*4、后序遍历*n); printf(*5、叶子节点数目*n); printf(*6、总节点数目*n); printf(*7、树的深度*n); printf(*8、结束*n); printf(*n); printf(请选着要操作的序号:); scanf(%d,&n); switch(n) case 1:printf(请输入根节点的值，并以#结束:n);t=CreateBtree();printf(二叉树已创建n);break; case 2:DLR(t);break; case 3:LDR(t);break; case 4:LRD(t);break; case 5:leafcount(t);printf(叶子节点数是%dn,count);break; case 6:btcount(t);printf(总节点数是%dn,count1-1);break; case 7:printf(树的深度是%