二叉樹操作設(shè)計和實現(xiàn)實驗報告

1、二叉樹操作設(shè)計和實現(xiàn)實驗報告一、 目的：掌握二叉樹的定義、性質(zhì)及存儲方式，各種遍歷算法。一、 要求：采用二叉樹鏈表作為存儲結(jié)構(gòu)，完成二叉樹的建立，先序、中序和后序以及 按層次遍歷的操作，求所有葉子及結(jié)點總數(shù)的操作。三、實驗內(nèi)容：1、分析、理解程序程序的功能是采用二叉樹鏈表存儲結(jié)構(gòu)，完成二叉樹的建立，先序、中序和 后序以及按層次遍歷的操作。如輸入二叉樹 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、 調(diào)試程序，設(shè)計一棵二叉樹，輸入完全二叉樹的先序序列，用#代表虛結(jié)點(空 指針)，如ABD#CE#F#建立二叉樹，求出先序、中序和后序以及按層次遍 歷序列，求所有葉子及結(jié)點總數(shù)。(1) 輸入完全二叉樹的先序序列 ABD#CE#F#程序運行結(jié)果如下：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)所有葉子及結(jié)點總數(shù)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/結(jié)點的最大個數(shù)typedef struct nodechar data;struct node *lchild,*rchild;BinTNode;/自定義二叉樹的結(jié)點類型typedef BinTNode *BinTree;/ 定義二叉樹的指針int No

9、deNum,leaf;/NodeNum/= 基于先序遍歷算法創(chuàng)建二叉樹 /=要求輸入先序序列，其中加入虛結(jié)點為結(jié)點數(shù)，leaf為葉子數(shù)"#"以示空指針的位置=Bi nTree CreatBi nTree(void)Bi nTree T;char ch; if(ch=getchar()='#') return(NULL);/ 讀入 # ，返回空指針else T=(BinTNode *)malloc(sizeof(BinTNode); / 生成結(jié)點T->data=ch;/ 構(gòu)造左子樹/ 構(gòu)造右子樹/ 訪問結(jié)點/ 先序遍歷左子樹 / 先序遍歷右子樹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);/= 采用后序遍歷求二叉樹的深度、結(jié)點數(shù)及葉子數(shù)的遞歸算法 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)/ 求左深度/ 求右深度/ 取左右深度的最大值/ 求結(jié)點數(shù)/ 若左右深度為 0，即為葉子隊列，按層次遍歷二叉樹/ 定義結(jié)點的指針數(shù)組 cq / 根入隊front=(front+1)%NodeNum;p=cqfront; / 出隊printf(&qu

13、ot;%c",p->data); / 出隊，輸出結(jié)點的值 if(p->lchild!=NULL)rear=(rear+1)%NodeNum;cqrear=p->lchild; / 左子樹入隊if(p->rchild!=NULL)rear=(rear+1)%NodeNum;cqrear=p->rchild; / 右子樹入隊/= 主函數(shù) =void main()BinTree root; int i,depth; printf("n");printf("Creat Bin_Treeroot=CreatBinTree(); do

14、Input preorder:"); / 輸入完全二叉樹的先序序列，/ 用# 代表虛結(jié)點，如 ABD#CE#F#/ 創(chuàng)建二叉樹，返回根結(jié)點/ 從菜單中選擇遍歷方式，輸入序號。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 ，求出該樹的結(jié)點 數(shù)。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);/ 求樹的深度及葉子數(shù)printf("