数据结构实验四树与二叉树.docx

《数据结构实验四树与二叉树.docx》由会员分享，可在线阅读，更多相关《数据结构实验四树与二叉树.docx（7页珍藏版）》请在三一办公上搜索。

1、数据结构实验四 树与二叉树数据结构实验四 树与二叉树 班级 学号 姓名 分数 一、实验目的： 1、掌握二叉树的定义、性质及存储方式，各种遍历算法。 2、掌握这种存储结构的构造算法以及基于每一种结构上的算法设计 3、初步掌握算法分析方法并对已设计出的算法进行分析，给出相应的结果。 二、实验要求： 采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序以及按层次遍历的操作，求所有叶子及结点总数的操作。 三、实验内容及分析： 1、分析、理解程序。 2、调试程序，设计一棵二叉树，输入完全二叉树的先序序列，用#代表虚结点，如ABD#CE#F#，建立二叉树，求出先序、中序和后序以及按层次遍历序列，

2、求所有叶子及结点总数。 四、程序的调试及运行结果 先序遍历中序遍历后序遍历树的深度及叶子树层次遍历五、程序代码 #includestdio.h #includestdlib.h #includestring.h #define Max 20 /结点的最大个数 typedef struct node char data; struct node *lchild,*rchild; BinTNode; /自定义二叉树的结点类型 typedef BinTNode *BinTree; /定义二叉树的指针 int NodeNum,leaf; /NodeNum为结点数，leaf为叶子数 /=基于先序遍历算法

3、创建二叉树= /=要求输入先序序列，其中加入虚结点#以示空指针的位置= BinTree CreatBinTree(void) BinTree T; char ch; if(ch=getchar)=#) return(NULL); /读入#，返回空指针 else T= (BinTNode *)malloc(sizeof(BinTNode); /生成结点 T-data=ch; T-lchild=CreatBinTree; /构造左子树 T-rchild=CreatBinTree; /构造右子树 return(T); /=NLR 先序遍历= void Preorder(BinTree T) if(T

4、) printf(%c,T-data); /访问结点 Preorder(T-lchild); /先序遍历左子树 Preorder(T-rchild); /先序遍历右子树 /=LNR 中序遍历= void Inorder(BinTree T) if(T) Inorder(T-lchild); /中序遍历左子树 printf(%c,T-data); /访问结点 Inorder(T-rchild); /中序遍历右子树 /=LRN 后序遍历= void Postorder(BinTree T) if(T) Postorder(T-lchild); /后序遍历左子树 Postorder(T-rchild

5、); /后序遍历右子树 printf(%c,T-data); /访问结点 /=采用后序遍历求二叉树的深度、结点数及叶子数的递归算法= int TreeDepth(BinTree T) int hl,hr,max; if(T) hl=TreeDepth(T-lchild); /求左深度 hr=TreeDepth(T-rchild); /求右深度 max=hlhr? hl:hr; /取左右深度的最大值 NodeNum=NodeNum+1; /求结点数 if(hl=0&hr=0) leaf=leaf+1; /若左右深度为0，即为叶子。 return(max+1); else return(0); /

6、=利用先进先出队列，按层次遍历二叉树= void Levelorder(BinTree T) int front=0,rear=1; BinTNode *cqMax,*p; /定义结点的指针数组cq cq1=T; /根入队 while(front!=rear) front=(front+1)%NodeNum; p=cqfront; /出队 printf(%c,p-data); /出队，输出结点的值 if(p-lchild!=NULL) rear=(rear+1)%NodeNum; cqrear=p-lchild; /左子树入队 if(p-rchild!=NULL) rear=(rear+1)%

7、NodeNum; cqrear=p-rchild; /右子树入队 /=数叶子节点个数= int countleaf(BinTree T) int hl,hr; if(T) hl=countleaf(T-lchild); hr=countleaf(T-rchild); if(hl=0&hr=0) /若左右深度为0，即为叶子。 return(1); else return hl+hr; else return 0; /=主函数= void main BinTree root; char i; int depth; printf(n); printf(Creat Bin_Tree； Input pr

8、eorder:); /输入完全二叉树的先序序列， / 用#代表虚结点，如ABD#CE#F# root=CreatBinTree; /创建二叉树，返回根结点 do /从菜单中选择遍历方式，输入序号。 printf(t* select *n); printf(t1: Preorder Traversaln); printf(t2: Iorder Traversaln); printf(t3: Postorder traversaln); printf(t4: PostTreeDepth,Node number,Leaf numbern); printf(t5: Level Depthn); /按层

9、次遍历之前，先选择4，求出该树的结点数。 printf(t0: Exitn); printf(t*n); fflush(stdin); scanf(%c,&i); /输入菜单序号 switch (i-0) case 1: printf(Print Bin_tree Preorder: ); Preorder(root); /先序遍历 break; case 2: printf(Print Bin_Tree Inorder: ); Inorder(root); /中序遍历 break; case 3: printf(Print Bin_Tree Postorder: ); Postorder(root); /后序遍历 break; case 4: depth=TreeDepth(root); /求树的深度及叶子数 printf(BinTree Depth=%d BinTree Node number=%d,depth,NodeNum); printf( BinTree Leaf number=%d,countleaf(root); break; case 5: printf(LevePrint Bin_Tree: ); Levelorder(root); /按层次遍历 break; default: exit(1); printf(n); while(i!=0);