6樹和二叉樹(數(shù)據(jù)結(jié)構(gòu)第6章)

1、第六章樹和二叉樹6.1樹tree的概念在日常生活中，可以見到很多情形可以歸結(jié)為樹結(jié)構(gòu)。如：家族譜系、行政管理機構(gòu)、DOS和Windows 磁盤文件管理系統(tǒng)等。我們討論的樹和自然界的樹在生長方向上正好相反，它是倒長的樹，即根朝上，枝干和葉子朝下。例1:某家族譜系的一局部宏恩景可宏福意海意河意江意民意凌意山意水例2：國家行政管理機構(gòu)的一局部例3: DO環(huán)口 Windows磁盤文件的一局部TC20VC6.0數(shù)據(jù)結(jié)構(gòu)課件數(shù)據(jù)結(jié)構(gòu)講稿第一章第二章MyTc程序一Tc1Tc2MyVc程序Vc1Vc2樹是一種層次結(jié)構(gòu)，屬于非線性結(jié)構(gòu)。我們學(xué)過的 線性表可以靈活組織數(shù)據(jù)，但它受到線性結(jié)構(gòu)的限制, 表達層次結(jié)構(gòu)不

2、太方便。樹的定義樹T是nn?0個結(jié)點的有限集合。它滿足:(1)僅有一個特定的結(jié)點，稱為根root丨結(jié)點;(2)其余結(jié)點分為m(詳0)個互不相交的非空有限集合T1,1 T 21-, Tm，其中每個集合自身又是一棵樹，稱為根的子樹subtree。為了表述方便，把沒有結(jié)點的樹稱為空樹。樹的定義具有遞歸性：即一棵樹是由根及假設(shè)干 棵子樹構(gòu)成的，而子樹又是由根及假設(shè)干棵子樹構(gòu)成 的，。表達樹的方法通常有4種：樹形、凹入、集合和廣 義表(1)樹形表示法、Il DI E M F (2)凹入表示法(4)廣義表表示法T(A(B,C(E,F),D(G,H)樹的根本術(shù)語為了對樹的形態(tài)表述清楚和形象，通常引用樹和人的

3、特征及術(shù)語來描述。1結(jié)點和樹的度degree結(jié)點所擁有的子樹的個數(shù)稱為該結(jié)點的度，而樹中各結(jié)點的度的最大值稱為該樹的度。1-.Br、 ITjr=riLeI FLg_J如：結(jié)點B、E、F、G和H的度數(shù)是0結(jié)點C和D的度數(shù)都是2結(jié)點A的度數(shù)是3;顯然3也是樹的度數(shù)2葉子leaf結(jié)點和分支結(jié)點度為0的結(jié)點稱為葉子結(jié)點終端結(jié)點；度不為0 的結(jié)點稱為分支結(jié)點非終端結(jié)點。一棵樹除了葉子結(jié)點就是分支節(jié)點。IAf r% E JI FD結(jié)點B、E、F、G和H是葉子結(jié)點結(jié)點A、C和D是分支結(jié)點3孩子child結(jié)點、雙親parents又稱父親 結(jié)點、兄弟brother及堂兄弟結(jié)點樹中一個結(jié)點的子樹的根稱為該結(jié)點的孩

4、子，該 結(jié)點稱為其孩子結(jié)點的雙親結(jié)點。同一個雙親的孩子 結(jié)點互稱為兄弟。雙親在同一層的結(jié)點互為堂兄弟Iab丿 c丿 d1 1FL EF .f1L G 丿.H丿如:結(jié)點B、C和D均為結(jié)點A的孩子結(jié)點；A是B、 C和D的雙親結(jié)點結(jié)點E和F為孩子C的結(jié)點；C是E和F的雙 親結(jié)點結(jié)點G和H為孩子D的結(jié)點；D是G和H的雙 親結(jié)點顯然結(jié)點A沒有雙親結(jié)點因為A不是子樹的根結(jié)點B、C和D互為兄弟；結(jié)點E和F互為兄弟； 結(jié)點G和H互為兄弟。但結(jié)點E、F為一方和G、H 為另一方互為堂兄弟4祖先ancestor和子孫descendant結(jié)點的祖先是從根到該所經(jīng)分支上的所有結(jié)點。反 之，以某結(jié)點為根的子樹中的任一結(jié)點

5、稱為該結(jié)點的 子孫。顯然祖先和子孫關(guān)系是父子關(guān)系的延伸。.A J卩fy rL C : D E.F.G-H如：結(jié)點A是結(jié)點B、C、D、E、F、G和H的祖先； 反之，結(jié)點B、C、D、E、F、G和H是的結(jié)點A的 子孫5結(jié)點的層數(shù)level和樹的深度depth，或稱 高度 height結(jié)點的層次從根結(jié)點開始算起，根結(jié)點的層數(shù)為1, 其余結(jié)點的層數(shù)等于其雙親結(jié)點的層數(shù)加1。比方，如果某個結(jié)點的層數(shù)為h，那么其子樹就在第h+1層。樹中各個結(jié)點層數(shù)的最大值稱為樹的深度高度。LA一 、B.C、D ._I1r 0棵互不相交的樹的IAD樹的邏輯關(guān)系:1樹的任一結(jié)點都可以有 0個或多個直接的后 繼結(jié)點孩子，這也是非

6、線性的原因，但至多只能 有一個直接的前驅(qū)結(jié)點雙親結(jié)點；2只有根結(jié)點沒有前驅(qū)，葉子結(jié)點終端結(jié)點 沒有后繼；3祖先與子孫關(guān)系是父子關(guān)系的延伸，它定義 了樹中各結(jié)點之間的縱向次序；4在有向樹中，同一組兄弟結(jié)點從左至右有長 幼之分。它定義了樹中各結(jié)點之間的橫向次序。樹的根本操作常見的操作：建立、遍歷、查詢、求深度、求結(jié)點的雙親和孩子、求樹的深度、求結(jié)點的層數(shù)和判空等。6.2二叉樹一般的樹規(guī)律性差，二叉樹結(jié)構(gòu)簡單，存儲和處理相對容易，而且一般的樹可以轉(zhuǎn)化為二叉樹處理621二叉樹的定義二叉樹是nn0個結(jié)點的有限集合，除了空 樹n=0之外，由一個根結(jié)點及兩棵不相交的左子 樹和右子樹組成；二叉樹每個結(jié)點的度數(shù)

7、w 2;二叉樹的定義是一個遞歸定義。二叉樹有5種根本形態(tài)：空樹?只有根結(jié)點?只有右子樹?只有左子樹?完整二叉樹二叉樹的性質(zhì) 性質(zhì)1 :二叉樹的第i層的結(jié)點數(shù)量最多為2i1i i證明：第1層的結(jié)點數(shù)目最多為1 20丨，第2層的 結(jié)點數(shù)目最多為2 21， ，那么第i層的結(jié)點數(shù)目 最多為2 1性質(zhì)2:深度為k的二叉樹結(jié)點數(shù)目最多為2k 1k 1 證明：當(dāng)其每層的結(jié)點數(shù)到達最大值時，該二叉樹的結(jié)點數(shù)最多，由性質(zhì)1可知，深度為k的二叉樹結(jié) 點數(shù)是：012k 1k2 2 2 . 2 2 1。性質(zhì)3:在任意二叉樹中，假設(shè)葉子終端結(jié)點的個數(shù)為no，度為2的結(jié)點數(shù)為n2，那么有no n2 1。證明：設(shè)n為結(jié)點總

8、數(shù)，門為1度的結(jié)點數(shù)，那么 n no m n?公式 1先分析二叉樹的結(jié)點度數(shù)和分支數(shù)的關(guān)系：由于度數(shù)為2的結(jié)點有兩個分支，度數(shù)為1的結(jié)點 有一個分支，度數(shù)為0的結(jié)點沒有分支，所以總的分 支數(shù)為n1 2 n2 ；此外，再分析二叉樹的雙親結(jié)點和分支數(shù)的關(guān)系： 除根結(jié)點之外的每個結(jié)點都是其雙親結(jié)點的一個 分支，所以總分支數(shù)為n 1，可得關(guān)系式ni 2n2 n 1 即 n ni 2n2 1公式 2；由公式1和2, 可得作厲1 證畢。如：葉子數(shù)為3C，E，F(xiàn)，度數(shù)為2的結(jié)點數(shù)為2A，B，滿足性質(zhì)3* D I EVH J又如：葉子數(shù)為2F，G，度數(shù)為2的結(jié)點數(shù)為1A，滿足性質(zhì)3BCI1 : *DE3=f

9、iJ滿二叉樹的定義：深度為k 1且結(jié)點數(shù)為2k i 的二叉樹。滿二叉樹的結(jié)點數(shù)到達最大值。女口：深度為3的滿二叉樹結(jié)點到達7個完全二叉樹的定義：對于滿二叉樹的結(jié)點，按以 下規(guī)那么編號：?從根結(jié)點開始，自上而下；?同一層自左至右。滿二叉樹的結(jié)點編號后，任意取滿二叉樹的前假設(shè)干個連續(xù)的結(jié)點所對應(yīng)的二叉樹，稱為完全二叉樹。完全二叉樹中，除最后一層外，其余各層均是滿的, 最后一層，結(jié)點連續(xù)出現(xiàn)在左邊。女口：深度為4的完全二叉樹又如：第2層結(jié)點不是連續(xù)出現(xiàn)在左側(cè)，所以不是 完全二叉樹再如：第3層未滿，所以不是完全二叉樹.匚D兀eG性質(zhì)4:具有n個結(jié)點的完全二叉樹的深度為：1 +(in log2n。證明：

10、由完全二叉樹和滿二叉樹的關(guān)系可知，一棵深度為k的完全二叉樹的結(jié)點數(shù)必介于深度為k-1和深度為k的滿二叉樹的結(jié)點數(shù)之間，那么有2k1 1 n 2k 1取等號的情況是：完全二叉樹是深度 為k的滿二叉樹，由此推出2k1 n 2k 1 2k，即 k 1 log2n k，所以 k 1intlog2n性質(zhì)5:如果一棵完全二叉樹有n個結(jié)點，對所有 結(jié)點按層次編號即從上到下，每層從左到右從1 開始編號，那么對任意結(jié)點i K i 1，那么其雙親為inti/2;?假設(shè)2i n，那么其無左子樹。假設(shè) 2i+1 n， 那么其無右子樹。分析：編號為i=4的結(jié)點D，亥樹的結(jié)點數(shù)n=10; 因i1，所以其雙親結(jié)點是(int

11、)(i/2)=2(即B);又因 2i=2*4 10,所以該結(jié)點有左子樹，左孩子編號為2i=8 即 H;再因2i+1=9 1 ,所以其雙親 結(jié)點是(int)(i/2)=2(即B);又因2i=2*5 10, 所以該結(jié)點沒有右子樹。6.3 二叉樹的存儲結(jié)構(gòu) 常用順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)。6.3.1 二叉樹的順序存儲結(jié)構(gòu)對于完全二叉樹進行結(jié)點編號后，編號可以反映 結(jié)點的分支和附屬關(guān)系,可以將這些結(jié)點存入一維數(shù) 組,編號和數(shù)組下標可以對應(yīng)起來。對于一般的二叉樹,不易直接采用順序存儲,可 以補成完全二叉樹后再用順序存儲的方法存儲。以上兩點是定義完全二叉樹的原因之一。如：一棵普通二叉樹由上圖用虛結(jié)點補成的

12、完全二叉樹再順序存 儲A1B2I C3I_ 4D5LjLE6J71L 84 1.p9T 1F10T11 11Il12G13 iLj位置i2345678910111213結(jié)點ABCDEFG定義:#defi ne MAXSIZE 100typedef char DataType;typedef structDataType btMAXSIZE+1;int num;SeqBTree;順序存儲結(jié)構(gòu)比較適合于完全全二叉樹，對于一 般的二叉樹需要引進虛結(jié)點，補成完全二叉樹后再順 序存儲。632二叉樹的鏈式存儲結(jié)構(gòu)定義:typedef struct nodeDataType data;struct node

13、 *lchild,*rchild;BTree;此種定義稱為二叉樹的二叉鏈表。在鏈式結(jié)構(gòu)中，通過每個結(jié)點的左右指針域，可以 找到其孩子結(jié)點，但要找雙親結(jié)點不方便，可以增加一個指針域保存雙親結(jié)點的地址，稱為帶雙親指針的 二叉鏈表。Ichilddatapare ntsrchildroot結(jié)點模式：定義：typedef struct nodeDataType data;struct node *lchild,*pare nts,*rchild;ThTree;6.4二叉樹的遍歷遍歷首先從根結(jié)點進入，對每個結(jié)點都要遍歷到 且每個結(jié)點僅遍歷一次。可以采用遞歸方法程序簡單和非遞歸方法程 序稍復(fù)雜。3+1 種:

14、-第一種方法:先序遍歷：根，左子樹，右子樹 遍歷的結(jié)果：A，B，C遍歷的足跡：沿途經(jīng)過各結(jié)點的“左部第二種方法:中序遍歷：左子樹，根，右子樹遍歷的結(jié)果：B，A，C遍歷的足跡：沿途經(jīng)過各結(jié)點的“下部第三種方法：后序遍歷：左子樹，右子樹，根遍歷的結(jié)果：B, C, A遍歷的足跡：沿途經(jīng)過各結(jié)點的“右部第四種方法：逆先序遍歷：根，右，左B第五種方法:逆中序遍歷:右，根，左C, A,B第六種方法： 逆后序遍歷:右，左，根C, B ,A第七種方法：按層次遍歷：從上根到下逐層進行，自左至右諸個結(jié)點進行 遍歷的結(jié)果：A , B , C例如：對以下二叉樹，分別用四種方法遍歷D,1.觀察：A根B , D, F根的

15、左子樹C, E, G根的右子樹2. 中序遍歷的結(jié)果：B , F, D, A , E, G, C 觀察：B, F , D根的左子樹A根E, G , C根的右子樹3. 后序遍歷的結(jié)果：F , D, B, G , E, C , A觀察：F, D, B根的左子樹G , E, C根的右子樹A根4. 按層次遍歷的結(jié)果：A, B , C, D, E , F , G 觀察：先A根，左右子樹次序打亂可以證明：1當(dāng)二叉樹的結(jié)點各不相同，假設(shè)中序遍歷序 列確定，假設(shè)再有先序或后序遍歷序列也確定， 那么該二叉樹唯一確定；2假設(shè)二叉樹的先序遍歷和后序遍歷確定，那么 該二叉樹不能唯一確定；女口：以下兩棵不同的二叉樹先序遍

16、歷都是A，B，而后序遍歷都是B，A。二叉樹的先序遍歷及其算法遍歷規(guī)律：先遍歷根結(jié)點，再遍歷左子樹，最后遍歷右子樹先序遍歷的遞歸算法和程序較簡單void PreOrder(BTree *bt)if(bt!=NULL)printf( “ %c ,dbat ta); /遍歷根結(jié)點輸出數(shù)據(jù) PreOrder(bt lchild); /遞歸遍歷左子樹 PreOrder(bt rchild); /遞歸遍歷右子樹先序遍歷的非遞歸算法和程序稍復(fù)雜void PreOrder1(BTree *bt)BTree *s100,*p=bt; /使用了指針數(shù)組int top=0; /使用了棧while(p!=NULL|t

17、op0)while(p!=NULL) /遍歷根和左子樹printf(“ %c d,apta); s+top=p; p=plchild;p=stop - ;p=p rchild; /遍歷右子樹6.4.2 二叉樹的中序遍歷 遍歷規(guī)律：先遍歷左子樹， 再遍歷根結(jié)點， 最后遍 歷右子樹。中序遍歷的遞歸算法和程序較簡單void InOrder(BTree *bt)if(bt!=NULL)InOrder(bt lchild); /遞歸遍歷左子樹printf(“%c ,dbatta); /遍歷根結(jié)點輸出數(shù)據(jù)InOrder(bt rchild); /遞歸遍歷右子樹中序遍歷的非遞歸算法和程序稍復(fù)雜void In

18、Order1(BTree *bt)BTree *s100,*p=bt;int top=0;while(p!=NULL|top0) while(p!=NULL)s+top=p;p=p lchild; /遍歷左子樹 p=stop - ;printf(“%c,p data);p=p rchild; /遍歷根和 右子樹6.4.3 二叉樹的后序遍歷遍歷規(guī)律： 先遍歷左子樹， 再遍歷右子樹， 最后遍 歷根結(jié)點。后序遍歷的遞歸算法和程序較簡單void PostOrder(BTree *bt)if(bt!=NULL)PostOrder(bt lchild); /遞歸遍歷左子樹PostOrder(bt rchi

19、ld); /遞歸遍歷右子樹printf( “%c ,dbatta); /遍歷根結(jié)點輸出數(shù)據(jù)后序遍歷的非遞歸算法和程序稍復(fù)雜void PostOrder1(BTree *bt)BTree *s1100,*p=bt;int s2100,b,top=0;dowhile(p!=NULL) /遍歷左子樹s1top=p;s2top+=0;p=p lchild;if(top0)b=s2-top; p=s1top;if(b=0)s1top=p;s2top+=1;p=p rchild; /遍歷右子樹else printf( “ %cdata,p); p=NULL; /遍歷根while(top0);6.4.4 二

20、叉樹的按層次遍歷先遍歷根結(jié)點，再遍歷根結(jié)點的孩子結(jié)點，再遍歷孩子結(jié)點的孩子結(jié)點，。具體如下：? 設(shè)置一個隊列，將其置空，假設(shè)樹非空，先將根 結(jié)點入隊；? 重復(fù)下述操作，直至隊列為空：隊首結(jié)點出隊，遍歷該結(jié)點；假設(shè)該結(jié)點有左子樹，那么將左子樹的根結(jié)點入隊；假設(shè)該結(jié)點有右子樹， 那么將右子樹的根結(jié)點入隊。typedef structBTree *sMAXSIZE;int front,rear;Sequence; /順序隊列類型void ScanLevel(BTree *t)/ 按層次遍歷二叉樹 非遞歸 Sequence que;/ 定義隊列 que.front=que.rear=0;/ 初始化隊列

21、 if(t!=NULL)/ 樹非空，將根結(jié)點入隊 que.rear+; que.sque.rear=t;printf( 二叉樹的層次結(jié)點是： ); while(que.front!=que.rear)/ 隊列非空 que.front+;/ 隊頭出隊 t=que.sque.front;printf(%c ,t data); / 遍歷結(jié)點if(t lchild!=NULL)/ 左孩子入隊que.rear+;que.sque.rear=t lchild;if(t rchild!=NULL)/ 右孩子入隊que.rear+;que.sque.rear=t rchild;根據(jù)按層次遍歷的思想，創(chuàng)立二叉樹

22、；由于二叉樹的結(jié)點構(gòu)成比較復(fù)雜，創(chuàng)立和遍歷時 必須有規(guī)律才能在機器上實施，這就想到以前講過的 完全二叉樹，完全二叉樹結(jié)點有對應(yīng)的編號，然后按 層次逐個輸入各結(jié)點的編號和數(shù)據(jù)，直至結(jié)束。假設(shè) 輸入非根結(jié)點，根據(jù)其編號偶數(shù)為左子樹結(jié)點，奇 數(shù)為右子樹結(jié)點 ，將其鏈接到其雙親結(jié)點的相應(yīng)指 針域上。例如：上述曾經(jīng)討論過的二叉樹用添加虛結(jié)點的方法補成一棵完全二叉樹且對結(jié)點編號;3C 一 . . .45門匸789 Q|Of l1 l2 l3G這里帶的結(jié)點是虛結(jié)點；除根結(jié)點外，左子樹結(jié)點 都是偶數(shù)編號，右子樹結(jié)點都是奇數(shù)編號。BTree *CreateTree()FILE *fp;BTree *t,*p,*

23、seqMAXSIZE;DataType x;int i;fp=fopen(p6 -1.dat,r);printf( 輸入二叉樹的層次結(jié)點： n); fscanf(fp,%d %c,&i,&x);printf(%d %cn,i,x)if(x!=)/ 建立根結(jié)點t=(BTree *)malloc(sizeof(BTree);t data=x;t lchild=NULL;t rchild=NULL;else return NULL;seqi=t;fscanf(fp,%d %c,&i,&x);printf(%d %cn,i,x); while(x!=)p=(BTree *)malloc(sizeof(

24、BTree);p data=x;p lchild=NULL;p rchild=NULL;seqi=p;if(i%2=0)seqi/2 lchild=p;/ 建立左子樹 else seqi/2 rchild=p;/ 建立右子樹 fscanf(fp,%d %c,&i,&x);printf(%d %cn,i,x);fclose(fp);printf(n);return t;程序 p6-1.c 二叉樹的層次建立和遍歷 輸入時注意結(jié)點的編號 作為結(jié)束標志匚訂Q3 CO訂CO C輸入文件編號和內(nèi)容，作為結(jié)束標志：1A2B3C 5D6E10F13G0 作為結(jié)束標志#define MAXSIZE 100 #i

25、n clude typedef char DataType; typedef struct nodeDataType data; struct node *lchild,*rchild;BTree;typedef structBTree *sMAXSIZE; int front,rear;Sequence;BTree *CreateTree()FILE *fp;BTree *t,*p,*seqMAXSIZE;DataType x;int i;fp=fopen(p6 -1.dat,r);printf( 輸入二叉樹的層次結(jié)點： n);fscanf(fp,%d %c,&i,&x);printf(%d

26、 %cn,i,x);if(x!=)t=(BTree *)malloc(sizeof(BTree);l. ujniejJC.uvJwuudKclesoioj Tee% p%11)wuud ：(xg!gQ% p%11tdj)jueosj Jd=p|iqo乙/!bes es|e ：d 二 PI!U5s/!bes(o=2%!)4!Jd=ibesFnN 二 Pig dFnN 二 PI!U5 d Jx=eiep d J(eejig)joezis)oo|eiJuG eejig)=d (.=ix)e|!M/v KxThUXO% p%11)wuudJ(xt!t11o% p%11tdj)jueosj =!bes

27、FnN un冋 es|eFnN 二 PI!US FriN 二 PI!U5 Jx=eiep void ScanLevel(BTree *t)Sequence que;que.front=que.rear=0;if(t!=NULL)que.rear+;que.sque.rear=t;printf( 二叉樹的層次結(jié)點是： );while(que.front!=que.rear)que.front+;t=que.sque.front;printf(%c ,tdata); / 遍歷結(jié)點if(t lchild!=NULL)que.rear+;que.sque.rear=t lchild;if(t rchi

28、ld!=NULL)que.rear+;que.sque.rear=t rchild;void main()BTree *t;t=CreateTree();ScanLevel(t);printf(n);二叉樹遍歷的應(yīng)用通過遍歷二叉樹，可以輸出樹中的結(jié)點數(shù)據(jù)，統(tǒng)計 和查找結(jié)點中的信息等。 如統(tǒng)計樹中結(jié)點數(shù)、 葉子數(shù)、 樹的深度，查找最大小結(jié)點的值等。(1) 求二叉樹的結(jié)點數(shù)中序法int NodeNumber=0;/ 統(tǒng)計結(jié)點個數(shù)計數(shù)變量void InOrder(BTree *bt)if(bt!=NULL) InOrder(bt lchild);/ 遍歷左子樹NodeNumber+;/ 遍歷根結(jié)點統(tǒng)

29、計結(jié)點 InOrder(bt rchild);/ 遍歷右子樹(2) 二叉樹的遞歸建立BTree *CreateTree()/ 先序法建立BTree *t;DataType x; scanf(%c,&x); if(x= ) return NULL;elset=(BTree *)malloc(sizeof(BTree);/ 建立根結(jié)點 t data=x;t lchild=CreateTree();/ 建立左子樹t rchild=CreateTree();/ 建立右子樹 return t;p6-2.c遞歸“先序建立二叉樹并用四種方法遍歷先序、中序、后序和按層次AEIF注意：這棵樹不是完全二叉樹，但每

30、個結(jié)點要指明它的左右子樹是否存在，假設(shè)不存在補上一個空結(jié)點為的是容易存儲和判斷。輸入先序文件： ABDFCEG #define MAXSIZE 100 #include typedef char DataType;typedef struct nodeDataType data;struct node *lchild,*rchild;BTree;FILE *fp;BTree *CreatTree( ) /先序遞歸建立二叉樹char x;BTree *t; x=fgetc(fp); if(x=)return NULL;elset=(BTree *)malloc(sizeof(BTree);t d

31、ata=x;t lchild=CreatTree();t rchild=CreatTree();return t;void PreOrder(BTree *bt) /先序遞歸遍歷if(bt!=NULL)printf(%3c,bt data);PreOrder(bt lchild);PreOrder(bt rchild);void PreOrder1(BTree *bt) /先序非遞歸遍歷BTree *s100,*p=bt;int top=0;while(p!=NULL|top0)while(p!=NULL)宀 pinff(=%3c=p dafa)八 s+foplrp 八 PHP -ch=5PH

32、S&pkpHP rchi-auoid -node(BTee *bo 二號書丘&逗 宀if(bfHNULL)宀-norders-ch=d)八 pinff(=%3c=bf das-)八-nordersch=dxvoid -node=(BTee *bf) /甘書亠 EyLU-B汪 宀BTree *SMAXS_ZEL*PH2in二 OPHPwhi_e(pHNUL u-fopvo)宀whi-e(pHNULL)宀 s+fopHpPHP -ch=5np=stop -;printf(%3c,pdata);p=p rchild;void PostOrder(BTree *bt) / 后序遞歸遍歷if(bt!=N

33、ULL)PostOrder(bt lchild);PostOrder(bt rchild);printf(%3c,bt data);void PostOrder1(BTree *bt) /后序非遞歸遍歷BTree *s1MAXSIZE,*p=bt;int s2MAXSIZE,b,top=0;dolchild;while(p!=NULL)s1top=p;s2top+=0;p=p if(top0)b=s2-top; p=s1top;if(b=0)s1top=p;s2top+=1;p=p rchild;else printf(%3c,p data); p=NULL;while(top0);void

34、LevelOrder(BTree *bt) /按層次遍歷BTree *qMAXSIZE,*p;int front,rear;q1=bt;front=rear=1;while(front=rear)p=qfront;front+;printf(%3c,p data);if(p lchild!=NULL)rear+;qrear=plchild;if(p rchild!=NULL)rear+;qrear=prchild;void main()BTree *t;fp=fopen(p6 -2.dat,r);printf( 輸入數(shù)據(jù)在文件中讀出！ nn);t=CreatTree();fclose(fp);

35、printf( 先序遞歸法遍歷： printf( 先序非遞歸法遍歷： printf(nn);printf( 中序遞歸法遍歷： printf(n);printf( 中序非遞歸法遍歷： printf(nn);printf( 后序遞歸法遍歷： printf(n);printf( 后序非遞歸法遍歷： printf(nn);printf( 按層次遍歷： printf(nn););PreOrder(t);printf(n);PreOrder1(t););InOrder(t););InOrder1(t););PostOrder(t););PostOrder1(t););LevelOrder(t);程序 p6

36、-3.c 家族樹的建立和統(tǒng)計該家族的平均年齡；指定的某個家族成員的輩分；輸出指定的某個輩分的所有家族成員景奇60宏恩58宏亮5弓新民661 1新主69新誠881新勝70vrvr意海430意河86意江73意凌弓 0意山6|意水6 C匚叮口匚CICOC匚。I訂匚叮按先序輸入其中0為虛結(jié)點：60 景奇(Ji ngqi)58 宏恩(Ho ngen)66 新民(Xi nmin)43 意海(Yihai)0 XX0 XX0 XX69 新主(Xin zhu)86 意河(Yihe)0 XX0 XX73 意江(Yijia ng)0 XX0 XX55 宏亮 (Hongliang)88 新誠 (Xincheng)55 意凌 (Yi