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

1、第六章樹和二叉樹6.1樹tree的概念在日常生活中，可以見到很多情形可以歸結(jié)為樹結(jié)構(gòu)。如：家族譜系、行政管理機(jī)構(gòu)、DOS和Windows 磁盤文件管理系統(tǒng)等。我們討論的樹和自然界的樹在生長(zhǎng)方向上正好相反，它是倒長(zhǎng)的樹，即根朝上，枝干和葉子朝下。例1:某家族譜系的一局部宏恩景可宏福意海意河意江意民意凌意山意水例2：國家行政管理機(jī)構(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)的限制, 表達(dá)層次結(jié)構(gòu)不

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

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

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

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

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

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

8、數(shù)，門為1度的結(jié)點(diǎn)數(shù)，那么 n no m n?公式 1先分析二叉樹的結(jié)點(diǎn)度數(shù)和分支數(shù)的關(guān)系：由于度數(shù)為2的結(jié)點(diǎn)有兩個(gè)分支，度數(shù)為1的結(jié)點(diǎn) 有一個(gè)分支，度數(shù)為0的結(jié)點(diǎn)沒有分支，所以總的分 支數(shù)為n1 2 n2 ；此外，再分析二叉樹的雙親結(jié)點(diǎn)和分支數(shù)的關(guān)系： 除根結(jié)點(diǎn)之外的每個(gè)結(jié)點(diǎn)都是其雙親結(jié)點(diǎn)的一個(gè) 分支，所以總分支數(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é)點(diǎn)數(shù)為2A，B，滿足性質(zhì)3* D I EVH J又如：葉子數(shù)為2F，G，度數(shù)為2的結(jié)點(diǎn)數(shù)為1A，滿足性質(zhì)3BCI1 : *DE3=f

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

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

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

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

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

14、-第一種方法:先序遍歷：根，左子樹，右子樹 遍歷的結(jié)果：A，B，C遍歷的足跡：沿途經(jīng)過各結(jié)點(diǎn)的“左部第二種方法:中序遍歷：左子樹，根，右子樹遍歷的結(jié)果：B，A，C遍歷的足跡：沿途經(jīng)過各結(jié)點(diǎn)的“下部第三種方法：后序遍歷：左子樹，右子樹，根遍歷的結(jié)果：B, C, A遍歷的足跡：沿途經(jīng)過各結(jié)點(diǎn)的“右部第四種方法：逆先序遍歷：根，右，左B第五種方法:逆中序遍歷:右，根，左C, A,B第六種方法： 逆后序遍歷:右，左，根C, B ,A第七種方法：按層次遍歷：從上根到下逐層進(jìn)行，自左至右諸個(gè)結(jié)點(diǎn)進(jìn)行 遍歷的結(jié)果：A , B , C例如：對(duì)以下二叉樹，分別用四種方法遍歷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é)點(diǎn)各不相同，假設(shè)中序遍歷序 列確定，假設(shè)再有先序或后序遍歷序列也確定， 那么該二叉樹唯一確定；2假設(shè)二叉樹的先序遍歷和后序遍歷確定，那么 該二叉樹不能唯一確定；女口：以下兩棵不同的二叉樹先序遍

16、歷都是A，B，而后序遍歷都是B，A。二叉樹的先序遍歷及其算法遍歷規(guī)律：先遍歷根結(jié)點(diǎn)，再遍歷左子樹，最后遍歷右子樹先序遍歷的遞歸算法和程序較簡(jiǎn)單void PreOrder(BTree *bt)if(bt!=NULL)printf( “ %c ,dbat ta); /遍歷根結(jié)點(diǎn)輸出數(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é)點(diǎn)， 最后遍 歷右子樹。中序遍歷的遞歸算法和程序較簡(jiǎn)單void InOrder(BTree *bt)if(bt!=NULL)InOrder(bt lchild); /遞歸遍歷左子樹printf(“%c ,dbatta); /遍歷根結(jié)點(diǎn)輸出數(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é)點(diǎn)。后序遍歷的遞歸算法和程序較簡(jiǎn)單void PostOrder(BTree *bt)if(bt!=NULL)PostOrder(bt lchild); /遞歸遍歷左子樹PostOrder(bt rchi

19、ld); /遞歸遍歷右子樹printf( “%c ,dbatta); /遍歷根結(jié)點(diǎn)輸出數(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é)點(diǎn)，再遍歷根結(jié)點(diǎn)的孩子結(jié)點(diǎn)，再遍歷孩子結(jié)點(diǎn)的孩子結(jié)點(diǎn)，。具體如下：? 設(shè)置一個(gè)隊(duì)列，將其置空，假設(shè)樹非空，先將根 結(jié)點(diǎn)入隊(duì)；? 重復(fù)下述操作，直至隊(duì)列為空：隊(duì)首結(jié)點(diǎn)出隊(duì)，遍歷該結(jié)點(diǎn)；假設(shè)該結(jié)點(diǎn)有左子樹，那么將左子樹的根結(jié)點(diǎn)入隊(duì)；假設(shè)該結(jié)點(diǎn)有右子樹， 那么將右子樹的根結(jié)點(diǎn)入隊(duì)。typedef structBTree *sMAXSIZE;int front,rear;Sequence; /順序隊(duì)列類型void ScanLevel(BTree *t)/ 按層次遍歷二叉樹 非遞歸 Sequence que;/ 定義隊(duì)列 que.front=que.rear=0;/ 初始化隊(duì)列

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

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

23、seqMAXSIZE;DataType x;int i;fp=fopen(p6 -1.dat,r);printf( 輸入二叉樹的層次結(jié)點(diǎn)： n); fscanf(fp,%d %c,&i,&x);printf(%d %cn,i,x)if(x!=)/ 建立根結(jié)點(diǎn)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 二叉樹的層次建立和遍歷 輸入時(shí)注意結(jié)點(diǎn)的編號(hào) 作為結(jié)束標(biāo)志匚訂Q3 CO訂CO C輸入文件編號(hào)和內(nèi)容，作為結(jié)束標(biāo)志：1A2B3C 5D6E10F13G0 作為結(jié)束標(biāo)志#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é)點(diǎn)： 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é)點(diǎn)是： );while(que.front!=que.rear)que.front+;t=que.sque.front;printf(%c ,tdata); / 遍歷結(jié)點(diǎn)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é)點(diǎn)數(shù)據(jù)，統(tǒng)計(jì) 和查找結(jié)點(diǎn)中的信息等。 如統(tǒng)計(jì)樹中結(jié)點(diǎn)數(shù)、 葉子數(shù)、 樹的深度，查找最大小結(jié)點(diǎn)的值等。(1) 求二叉樹的結(jié)點(diǎn)數(shù)中序法int NodeNumber=0;/ 統(tǒng)計(jì)結(jié)點(diǎn)個(gè)數(shù)計(jì)數(shù)變量void InOrder(BTree *bt)if(bt!=NULL) InOrder(bt lchild);/ 遍歷左子樹NodeNumber+;/ 遍歷根結(jié)點(diǎn)統(tǒng)

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

30、個(gè)結(jié)點(diǎn)要指明它的左右子樹是否存在，假設(shè)不存在補(bǔ)上一個(gè)空結(jié)點(diǎn)為的是容易存儲(chǔ)和判斷。輸入先序文件： 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 二號(hào)書丘&逗 宀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)計(jì)該家族的平均年齡；指定的某個(gè)家族成員的輩分；輸出指定的某個(gè)輩分的所有家族成員景奇60宏恩58宏亮5弓新民661 1新主69新誠881新勝70vrvr意海430意河86意江73意凌弓 0意山6|意水6 C匚叮口匚CICOC匚。I訂匚叮按先序輸入其中0為虛結(jié)點(diǎn)：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