二叉树操作设计和实现实验报告

1、二叉树操作设计和实现实验报告一、 目的：掌握二叉树的定义、性质及存储方式，各种遍历算法。一、 要求：采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序以及 按层次遍历的操作，求所有叶子及结点总数的操作。三、实验内容：1、分析、理解程序程序的功能是采用二叉树链表存储结构，完成二叉树的建立，先序、中序和 后序以及按层次遍历的操作。如输入二叉树 ABD#CE#F#，链表示意图如下：2、添加中序和后序遍历算法=LNR 中序遍历=void Ino rder(B in Tree T)if(T)Ino rder(T->lchild);prin tf("%c",T->

2、;data); In order(T->rchild);/=LRN 后序遍历=void Postorder(B in Tree T)if(T)Postorder(T->lchild);Postorder(T->rchild); prin tf("%c",T->data); 3、 调试程序，设计一棵二叉树，输入完全二叉树的先序序列，用#代表虚结点(空 指针)，如ABD#CE#F#建立二叉树，求出先序、中序和后序以及按层次遍 历序列，求所有叶子及结点总数。(1) 输入完全二叉树的先序序列 ABD#CE#F#程序运行结果如下：Ci*eat Bin_Ti&#

3、39;ee ； I npu.t preopdep-口RDtlltltCEMltFtntKK XXX XXX XX Select XtOtXHXHXKXXX1； Prerder Iruepsal2： ITi*au©raal3 i Post&i'dei* t:i*auePE5il4： PostTeeDepthMode number, Leaf nun tier 5: Level Depth0： Exit(2) 先序序列:>int Bin_t>'ee PFeorder! ABDCEFxw昇畀wrxwKxx select xxxxsKSHiWMSKmx1:

4、 Pt'eoi'deE* Ti'auei'sol2 1order Traversal3: Postoi?der traversal4： t'astTt'eebeptlifNode numberLeaf nunhei'5 = Leuel Deptli0： Exit疋豐慎餐且 w 餐豐 unit nitifjtitxitafjijtafjiit/jut*(3) 中序序列:i-int Bin_Tr»o Inopd&r： DBAHCF* seLeet *1! Pl*fe&PdfeP Tl*AUfeI*S：AL2 -1 u

5、i'de i' Ti'auei"s：al3: Postni*dei' ti"avei*s：al4； PostTr&eDcpth. Node nunl>&rr nunb&r 5; Level Depth0： Exit(4) 后序序列:2Print Bin_rPostorder= DBEFClftKmUlCMXKKim gg Jen t 拭其其兀與:其冥其輒其其兀1； Pi'eorder rrauersal2 - lopclet' IrauerAl3: Postapdei* tirauepsatl4：

6、 PosztlvseDptehrHode numbeik*r Leaf numbev- £： Level De pt h a： Exit(5)所有叶子及结点总数inTree Depth=3 BinTree Node nunhei1 BinTee Leaf nunibeF=3 貝其員耳算闿耳胄科算 5q 号qt KlOClOtXXJf KJOC1: Ppeovdep Tvauepsal2- lovder Trauevsal3 * Potovder trauersa14= PostTr'eeDepth,Node nunberLeaf ntiiljer 5: Level Depth

7、0= ExitX X K H K Mi X X X X X H K Mi K *f K K If K K K *f K X Jf 3< Jf Jf K(6)按层次遍历序列：LeuePrint Bin_Tpee： ABCDEF aeleet mtxzK員xMmtxz1: Ppeapdep T rauei'sal2 :1 n r-de v- Tphu鼻pghl3 : Po st o rdei1 ti*av&尸!：比14： PostTi'-e&Dapth,Node ftumbet*Leaf nunbev S - Leue 1 Dept：It0: Exitmcni

8、c JOCjCaiCICITKKKKKXXimKXXXaiOCKXKXXXBPt*ess any key to ontinue四、源程序代码#i nclude"stdio.h"#i nclude"stri ng.h"#i nclude"stdlib.h"#defi ne Max 20/结点的最大个数typedef struct nodechar data;struct node *lchild,*rchild;BinTNode;/自定义二叉树的结点类型typedef BinTNode *BinTree;/ 定义二叉树的指针int No

9、deNum,leaf;/NodeNum/= 基于先序遍历算法创建二叉树 /=要求输入先序序列，其中加入虚结点为结点数，leaf为叶子数"#"以示空指针的位置=Bi nTree CreatBi nTree(void)Bi nTree T;char ch; if(ch=getchar()='#') return(NULL);/ 读入 # ，返回空指针else T=(BinTNode *)malloc(sizeof(BinTNode); / 生成结点T->data=ch;/ 构造左子树/ 构造右子树/ 访问结点/ 先序遍历左子树 / 先序遍历右子树T->

10、;lchild=CreatBinTree();T->rchild=CreatBinTree(); return(T);/=NLR 先序遍历 =void Preorder(BinTree T)if(T) 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->rchil

11、d);/=LRN 后序遍历 = void Postorder(BinTree T) if(T)Postorder(T->lchild);Postorder(T->rchild);printf("%c",T->data);/= 采用后序遍历求二叉树的深度、结点数及叶子数的递归算法 int TreeDepth(BinTree T)int hl,hr,max;if(T)hl=TreeDepth(T->lchild); hr=TreeDepth(T->rchild);max=hl>hr? hl:hr;NodeNum=NodeNum+1;if(hl

12、=0&&hr=0) leaf=leaf+1; return(max+1);else return(0);/= 利用"先进先出 "(FIFO)void Levelorder(BinTree T)int front=0,rear=1;BinTNode *cqMax,*p;cq1=T;while(front!=rear)/ 求左深度/ 求右深度/ 取左右深度的最大值/ 求结点数/ 若左右深度为 0，即为叶子队列，按层次遍历二叉树/ 定义结点的指针数组 cq / 根入队front=(front+1)%NodeNum;p=cqfront; / 出队printf(&qu

13、ot;%c",p->data); / 出队，输出结点的值 if(p->lchild!=NULL)rear=(rear+1)%NodeNum;cqrear=p->lchild; / 左子树入队if(p->rchild!=NULL)rear=(rear+1)%NodeNum;cqrear=p->rchild; / 右子树入队/= 主函数 =void main()BinTree root; int i,depth; printf("n");printf("Creat Bin_Treeroot=CreatBinTree(); do

14、Input preorder:"); / 输入完全二叉树的先序序列，/ 用# 代表虚结点，如 ABD#CE#F#/ 创建二叉树，返回根结点/ 从菜单中选择遍历方式，输入序号。printf("t* select*n");printf("t1: Preorder Traversaln");printf("t2: Iorder Traversaln");printf("t3: Postorder traversaln");printf("t4: PostTreeDepth,Node number,Le

15、af numbern");printf("t5: Level Depthn"); / 按层次遍历之前， 先选择 4 ，求出该树的结点 数。printf("t0: Exitn");printf("t*n");scanf("%d",&i); / 输入菜单序号( 0-5 )switch (i)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("