程序二叉树的存贮与遍历.pdf

数据结构 课程实验报告 学号： 姓名： 实验日期： 实验名称：二叉树的存贮与遍历 一、实验目的 掌握二叉树结构的非线性和递归性特点，以及用指针类型描述和访问二叉树 的运算。 二、实验内容与实验步骤 问题描述： 建立任意二叉树的二叉链表存储，并对其进行先序、中序、后序遍历，求出 叶子结点和总结点数目。(有能力的同学加上层次遍历) 基本要求： 采用二叉链表作为存储结构，以加入虚结点的先序序列输人建立该二叉树的 存储，并设菜单，依据选项分别输出该二叉树的先序、中序、后序和层次遍历序 列及叶子结点和总结点数目、二叉树的深度。二叉树结点的数据域可采用字符。 （用菜单形式） 测试数据：建立如图所示的二叉树存储。 A 建立时的输入序则为：ABD000CE00F00, B C 测试先序、中序、后序、层次遍历的结果 以及叶子结点和总结点数目。 D E F 提示：用递归方式实现建立、先序遍历、中序遍历和后序遍历，用队列实现层 次遍历，求叶子结点和总结点数目时，可采用任何一种遍历方法来实现，只是 加入一个计数器，当遍历到某个结点时对其进行判断，若符合条件，则将计数 器加1，最后输出计数器的值。 三、附录： #includestdio.h #includemalloc.h int 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 ==NULLbt-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) {