樹和二叉樹（數(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：DOS和Windows磁盤文件的一部分C:TC20VC6.0數(shù)據(jù)結(jié)構(gòu)課件 數(shù)據(jù)結(jié)構(gòu)講稿 第一章 第二章 MyTc程序 Tc1 Tc2 MyVc程序 Vc1 Vc2 樹是一種層次結(jié)構(gòu)，屬于非線性結(jié)構(gòu)。我們學(xué)過的線性表可以靈活組織數(shù)據(jù)，但它受到線性結(jié)構(gòu)的限制，表達層次結(jié)構(gòu)不太方便。6.1

2、.1樹的定義 樹T是n（n0）個結(jié)點的有限集合。它滿足：(1)僅有一個特定的結(jié)點，稱為根（root）結(jié)點;(2)其余結(jié)點分為m(m0)個互不相交的非空有限集合,其中每個集合自身又是一棵樹，稱為根的子樹（subtree）。 為了表述方便，把沒有結(jié)點的樹稱為空樹。樹的定義具有遞歸性：即一棵樹是由根及若干棵子樹構(gòu)成的，而子樹又是由根及若干棵子樹構(gòu)成的，。表達樹的方法通常有4種：樹形、凹入、集合和廣義表(1) 樹形表示法ABCDEFGH(2) 凹入表示法ABCEFDGH(3) 集合嵌套表示法 ACDB(4) 廣義表表示法 T(A(B,C(E,F),D(G,H)6.1.3 樹的基本術(shù)語 為了對樹的形態(tài)表

3、述清楚和形象，通常引用樹和人的特征及術(shù)語來描述。（1）結(jié)點和樹的度（degree）結(jié)點所擁有的子樹的個數(shù)稱為該結(jié)點的度，而樹中各結(jié)點的度的最大值稱為該樹的度。ABCDEFGH如：結(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é)點。ABCDEFGH如: 結(jié)點 B、E、F、G和H是葉子結(jié)點結(jié)點A、C和D是分支結(jié)點（3）孩子（child）結(jié)點、雙親（parents又稱父親）結(jié)點、兄弟（brother）及堂兄弟結(jié)點樹中

4、一個結(jié)點的子樹的根稱為該結(jié)點的孩子，該結(jié)點稱為其孩子結(jié)點的雙親結(jié)點。同一個雙親的孩子結(jié)點互稱為兄弟。雙親在同一層的結(jié)點互為堂兄弟。ABCDEFGH如:結(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)系的延伸。ABCDEFGH 如：結(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ù)的最大值稱為樹的深度（高度）。ABCDEFGH如:結(jié)點A的層數(shù)為1；結(jié)點B、C和D的層數(shù)為2；結(jié)點E、F、G和H的層數(shù)為3樹的深度（高度）為3。（6）有序樹（orderedtree）和無序樹（unor

6、deredtree）若一棵樹中結(jié)點的各子樹從左到右是有次序的，即若交換了某結(jié)點各子樹的相對位置就構(gòu)成不同的樹，則稱這棵樹為有序樹，否則稱為無序樹。（7）路徑（path）從樹中的一個結(jié)點到另一個結(jié)點的路途ABCDEFGH 如：A-C-E,A-D-H等 但B-A-D-G不是路徑，因為樹不能這樣遍歷。（8）森林（forest）：m（m0）棵互不相交的樹的集合ABCDEFGHABCD樹的邏輯關(guān)系：（1）樹的任一結(jié)點都可以有0個或多個直接的后繼結(jié)點（孩子，這也是非線性的原因），但至多只能有一個直接的前驅(qū)結(jié)點（雙親結(jié)點）；（2）只有根結(jié)點沒有前驅(qū)，葉子結(jié)點（終端結(jié)點）沒有后繼；（3）祖先與子孫關(guān)系是父子關(guān)

7、系的延伸，它定義了樹中各結(jié)點之間的縱向次序；（4）在有向樹中，同一組兄弟結(jié)點從左至右有長幼之分。它定義了樹中各結(jié)點之間的橫向次序。6.1.4樹的基本操作常見的操作：建立、遍歷、查詢、求深度、求結(jié)點的雙親和孩子、求樹的深度、求結(jié)點的層數(shù)和判空等。6.2 二叉樹一般的樹規(guī)律性差，二叉樹結(jié)構(gòu)簡單，存儲和處理相對容易，而且一般的樹可以轉(zhuǎn)化為二叉樹處理。6.2.1二叉樹的定義二叉樹是n（n0）個結(jié)點的有限集合，除了空樹（n=0）之外，由一個根結(jié)點及兩棵不相交的左子樹和右子樹組成；二叉樹每個結(jié)點的度數(shù)2；二叉樹的定義是一個遞歸定義。二叉樹有5種基本形態(tài)：空樹 只有根結(jié)點 只有右子樹 只有左子樹 完整二叉樹

8、 6.2.2 二叉樹的性質(zhì)性質(zhì)1：二叉樹的第i層的結(jié)點數(shù)量最多為。ABCDEFG證明：第1層的結(jié)點數(shù)目最多為1（），第2層的結(jié)點數(shù)目最多為2（），則第i層的結(jié)點數(shù)目最多為。性質(zhì)2：深度為k的二叉樹結(jié)點數(shù)目最多為。證明：當其每層的結(jié)點數(shù)達到最大值時，該二叉樹的結(jié)點數(shù)最多，由性質(zhì)1可知，深度為k的二叉樹結(jié)點數(shù)是：。性質(zhì)3：在任意二叉樹中，若葉子（終端）結(jié)點的個數(shù)為，度為2的結(jié)點數(shù)為，則有。證明：設(shè)n為結(jié)點總數(shù)，為1度的結(jié)點數(shù)，則（公式1）先分析二叉樹的結(jié)點度數(shù)和分支數(shù)的關(guān)系：由于度數(shù)為2的結(jié)點有兩個分支，度數(shù)為1的結(jié)點有一個分支，度數(shù)為0的結(jié)點沒有分支，所以總的分支數(shù)為；此外，再分析二叉樹的雙親結(jié)

9、點和分支數(shù)的關(guān)系：除根結(jié)點之外的每個結(jié)點都是其雙親結(jié)點的一個分支，所以總分支數(shù)為，可得關(guān)系式，即（公式2）；由公式1和2，可得，證畢。如：葉子數(shù)為3（C，E，F(xiàn)），度數(shù)為2的結(jié)點數(shù)為2（A，B），滿足性質(zhì)3。 又如：葉子數(shù)為2（F，G），度數(shù)為2的結(jié)點數(shù)為1（A），滿足性質(zhì)3。 滿二叉樹的定義：深度為k（k1）且結(jié)點數(shù)為的二叉樹。滿二叉樹的結(jié)點數(shù)達到最大值。如：深度為3的滿二叉樹結(jié)點達到7個 A1B2C3D4E5F6G7完全二叉樹的定義：對于滿二叉樹的結(jié)點，按下列規(guī)則編號：從根結(jié)點開始，自上而下；同一層自左至右。滿二叉樹的結(jié)點編號后，任意取滿二叉樹的前若干個連續(xù)的結(jié)點所對應(yīng)的二叉樹，稱為完全二

10、叉樹。完全二叉樹中，除最后一層外，其余各層均是滿的，最后一層，結(jié)點連續(xù)出現(xiàn)在左邊。如：深度為4的完全二叉樹 又如：第2層結(jié)點不是連續(xù)出現(xiàn)在左側(cè)，所以不是完全二叉樹 再如：第3層未滿，所以不是完全二叉樹性質(zhì)4：具有n個結(jié)點的完全二叉樹的深度為：1+。證明：由完全二叉樹和滿二叉樹的關(guān)系可知，一棵深度為k的完全二叉樹的結(jié)點數(shù)必介于深度為k-1和深度為k的滿二叉樹的結(jié)點數(shù)之間，則有（取等號的情況是：完全二叉樹是深度為k的滿二叉樹），由此推出，即，所以性質(zhì)5：如果一棵完全二叉樹有n個結(jié)點，對所有結(jié)點按層次編號（即從上到下），每層從左到右從1開始編號，則對任意結(jié)點i（1in），有： 若i=1，則其為根，沒

11、有雙親。若i1，則其雙親為(int)(i/2); 若2in（即它有左子樹），則其左子樹編號為2i;若2in，則其無左子樹。若2i+1n（即它有右子樹），則其右子樹的編號為2i+1; 若2i+1n，則其無右子樹。分析：編號為i=4的結(jié)點D，該樹的結(jié)點數(shù)n=10；因i1，所以其雙親結(jié)點是(int)(i/2)=2(即B)；又因2i=2*410，所以該結(jié)點有左子樹，左孩子編號為2i=8（即H）；再因2i+1=910, 所以該結(jié)點有右子樹，右孩子編號為2i+1=9（即I）再分析：編號為i=5的結(jié)點E，因i1，所以其雙親結(jié)點是(int)(i/2)=2(即B)；又因2i=2*510，所以該結(jié)點有左子樹，左孩

12、子編號為2i=10（即J）；再因2i+1=1110, 所以該結(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é)點（）補成的完全二叉樹再順序存儲 位置1 2345678910111213結(jié)點ABCDEFG定義：#define MAXSIZE 100typedef char

13、DataType;typedef struct DataType btMAXSIZE+1; int num;SeqBTree;順序存儲結(jié)構(gòu)比較適合于完全全二叉樹，對于一般的二叉樹需要引進虛結(jié)點，補成完全二叉樹后再順序存儲。6.3.2 二叉樹的鏈式存儲結(jié)構(gòu)lchild data rchild 結(jié)點模式： rootA E B C D G F 定義：typedef struct node DataType data; struct node *lchild,*rchild;BTree; 此種定義稱為二叉樹的二叉鏈表。在鏈式結(jié)構(gòu)中，通過每個結(jié)點的左右指針域，可以找到其孩子結(jié)點，但要找雙親結(jié)點不方便，可

14、以增加一個指針域保存雙親結(jié)點的地址，稱為帶雙親指針的二叉鏈表。lchild data parents rchild結(jié)點模式： rootA C B ED F G 定義：typedef struct node DataType data; struct node *lchild,*parents,*rchild;ThTree;6.4 二叉樹的遍歷遍歷首先從根結(jié)點進入，對每個結(jié)點都要遍歷到且每個結(jié)點僅遍歷一次。可以采用遞歸方法（程序簡單）和非遞歸方法（程序稍復(fù)雜）。 ABC遍歷二叉樹，可有6+1種方法（實際采用3+1種）：第一種方法：先序遍歷：根，左子樹，右子樹 遍歷的結(jié)果：A，B，C遍歷的足跡：沿

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

16、右子樹） 2. 中序遍歷的結(jié)果：B，F(xiàn)，D，A，E，G，C觀察：B，F(xiàn)，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(xiàn)，G 觀察：先A（根），左右子樹次序打亂可以證明：（1）當二叉樹的結(jié)點各不相同，若中序遍歷序列確定，若再有先序（或后序）遍歷序列也確定，則該二叉樹唯一確定；（2）若二叉樹的先序遍歷和后序遍歷確定，則該二叉樹不能唯一確定； 如：下列兩棵不同的二叉樹先序遍歷都是（A，B），而后序遍歷都是（B，A）。 6.4.1 二

17、叉樹的先序遍歷及其算法 遍歷規(guī)律：先遍歷根結(jié)點，再遍歷左子樹，最后遍歷右子樹。 先序遍歷的遞歸算法和程序（較簡單） void PreOrder(BTree *bt) if(bt!=NULL) printf(“%c ”,btdata); /遍歷根結(jié)點（輸出數(shù)據(jù)）PreOrder(btlchild); /遞歸遍歷左子樹PreOrder(btrchild); /遞歸遍歷右子樹 先序遍歷的非遞歸算法和程序（稍復(fù)雜） void PreOrder1(BTree *bt) BTree *s100,*p=bt; /使用了指針數(shù)組 int top=0; /使用了棧 while(p!=NULL|top0) whi

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

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

20、d); /遞歸遍歷右子樹printf(“%c ”,btdata); /遍歷根結(jié)點（輸出數(shù)據(jù)） 后序遍歷的非遞歸算法和程序（稍復(fù)雜） void PostOrder1(BTree *bt) BTree *s1100,*p=bt; int s2100,b,top=0; do while(p!=NULL) /遍歷左子樹s1top=p;s2top+=0;p=plchild; if(top0) b=s2-top; p=s1top; if(b=0)s1top=p;s2top+=1;p=prchild; /遍歷右子樹else printf(“%c ”,pdata); p=NULL; /遍歷根 while(to

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

22、隊列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 ,tdata); / 遍歷結(jié)點if(tlchild!=NULL)/左孩子入隊que.rear+;que.sque.rear=tlchild;if(trchild!=NULL)/右孩子入隊que.rear+;que.sque.rear=trchild; 根據(jù)按層次遍歷的思想，創(chuàng)建二叉樹; 由于二叉樹的結(jié)點構(gòu)成比較復(fù)

23、雜，創(chuàng)建和遍歷時必須有規(guī)律才能在機器上實施，這就想到以前講過的完全二叉樹，完全二叉樹結(jié)點有對應(yīng)的編號，然后按層次逐個輸入各結(jié)點的編號和數(shù)據(jù)，直至結(jié)束。若輸入非根結(jié)點，根據(jù)其編號（偶數(shù)為左子樹結(jié)點，奇數(shù)為右子樹結(jié)點），將其鏈接到其雙親結(jié)點的相應(yīng)指針域上。例如：上述曾經(jīng)討論過的二叉樹 用添加虛結(jié)點的辦法補成一棵完全二叉樹且對結(jié)點編號； 這里帶的結(jié)點是虛結(jié)點；除根結(jié)點外，左子樹結(jié)點都是偶數(shù)編號，右子樹結(jié)點都是奇數(shù)編號。BTree *CreateTree()FILE *fp;BTree *t,*p,*seqMAXSIZE;DataType x;int i;fp=fopen(p6-1.dat,r);pr

24、intf(輸入二叉樹的層次結(jié)點：n);fscanf(fp,%d %c,&i,&x);printf(%d %cn,i,x);if(x!=)/建立根結(jié)點t=(BTree *)malloc(sizeof(BTree);tdata=x;tlchild=NULL;trchild=NULL;else return NULL;seqi=t; fscanf(fp,%d %c,&i,&x);printf(%d %cn,i,x); while(x!=) p=(BTree *)malloc(sizeof(BTree);pdata=x;plchild=NULL;prchild=NULL;seqi=p;if(i%2=0

25、)seqi/2lchild=p;/建立左子樹else seqi/2rchild=p;/建立右子樹 fscanf(fp,%d %c,&i,&x);printf(%d %cn,i,x);fclose(fp);printf(n);return t;程序p6-1.c 二叉樹的層次建立和遍歷 輸入時注意結(jié)點的編號（作為結(jié)束標志）輸入文件（編號和內(nèi)容， 作為結(jié)束標志）：1A2B3C5D6E10F13G0 /作為結(jié)束標志#define MAXSIZE 100#includetypedef char DataType;typedef struct nodeDataType data;struct node *

26、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 %cn,i,x);if(x!=)t=(BTree *)malloc(sizeof(BTree);tdata=x;tlchild=NULL;trchild=NULL

27、;else return NULL;seqi=t; fscanf(fp,%d %c,&i,&x);printf(%d %cn,i,x); while(x!=)p=(BTree *)malloc(sizeof(BTree);pdata=x;plchild=NULL;prchild=NULL;seqi=p;if(i%2=0)seqi/2lchild=p;else seqi/2rchild=p; fscanf(fp,%d %c,&i,&x);printf(%d %cn,i,x);fclose(fp);printf(n);return t;void ScanLevel(BTree *t)Sequenc

28、e 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(tlchild!=NULL)que.rear+;que.sque.rear=tlchild;if(trchild!=NULL)que.rear+;que.sque.rear=trchild;void main()BTree *t;t=CreateTree();ScanL

29、evel(t); printf(n);6.4.5二叉樹遍歷的應(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(btlchild);/遍歷左子樹 NodeNumber+;/遍歷根結(jié)點（統(tǒng)計結(jié)點） InOrder(btrchild);/遍歷右子樹 (2) 二叉樹的遞歸建立BTree *CreateTree()/先序法建立BTree *t

30、;DataType x;scanf(%c,&x);if(x=) return NULL; elset=(BTree *)malloc(sizeof(BTree);/建立根結(jié)點tdata=x;tlchild=CreateTree();/建立左子樹trchild=CreateTree();/建立右子樹return t; p6-2.c遞歸“先序”建立二叉樹并用四種方法遍歷（先序、中序、后序和按層次）。 注意：這棵樹不是完全二叉樹，但每個結(jié)點要指明它的左右子樹是否存在，若不存在補上一個空結(jié)點（）為的是容易存儲和判斷。輸入（先序）文件：ABDFCEG#define MAXSIZE 100#include

31、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);tdata=x;tlchild=CreatTree();trchild=CreatTree();return t;void PreOrder(BTree *bt)/先序遞歸遍歷if(

32、bt!=NULL)printf(%3c,btdata); PreOrder(btlchild);PreOrder(btrchild);void PreOrder1(BTree *bt)/先序非遞歸遍歷 BTree *s100,*p=bt; int top=0; while(p!=NULL|top0) while(p!=NULL)printf(%3c,pdata); s+top=p; p=plchild; p=stop-;p=prchild; void InOrder(BTree *bt)/中序遞歸遍歷if(bt!=NULL)InOrder(btlchild);printf(%3c,btdata

33、);InOrder(btrchild);void InOrder1(BTree *bt)/中序非遞歸遍歷 BTree *sMAXSIZE,*p=bt; int top=0; while(p!=NULL|top0) while(p!=NULL)s+top=p;p=plchild; p=stop-;printf(%3c,pdata);p=prchild; void PostOrder(BTree *bt)/后序遞歸遍歷if(bt!=NULL)PostOrder(btlchild);PostOrder(btrchild);printf(%3c,btdata);void PostOrder1(BTre

34、e *bt)/后序非遞歸遍歷 BTree *s1MAXSIZE,*p=bt; int s2MAXSIZE,b,top=0; do while(p!=NULL)s1top=p;s2top+=0;p=plchild; if(top0) b=s2-top; p=s1top; if(b=0)s1top=p;s2top+=1;p=prchild; else printf(%3c,pdata); p=NULL; while(top0);void LevelOrder(BTree *bt)/按層次遍歷BTree *qMAXSIZE,*p;int front,rear;q1=bt;front=rear=1;w

35、hile(front=rear)p=qfront;front+;printf(%3c,pdata);if(plchild!=NULL)rear+;qrear=plchild; if(prchild!=NULL)rear+;qrear=prchild;void main()BTree *t;fp=fopen(p6-2.dat,r);printf(輸入數(shù)據(jù)在文件中讀出！nn);t=CreatTree();fclose(fp);printf(先序遞歸法遍歷： );PreOrder(t);printf(n);printf(先序非遞歸法遍歷：);PreOrder1(t);printf(nn);print

36、f(中序遞歸法遍歷： );InOrder(t);printf(n);printf(中序非遞歸法遍歷：);InOrder1(t);printf(nn);printf(后序遞歸法遍歷： );PostOrder(t);printf(n);printf(后序非遞歸法遍歷：);PostOrder1(t);printf(nn);printf(按層次遍歷： );LevelOrder(t);printf(nn);程序p6-3.c 家族樹的建立和統(tǒng)計該家族的平均年齡； 指定的某個家族成員的輩分； 輸出指定的某個輩分的所有家族成員。按先序輸入（其中0為虛結(jié)點）：60 景奇(Jingqi)58 宏恩(Hongen)

37、66 新民(Xinmin)43 意海(Yihai)0 XX0 XX0 XX69 新主(Xinzhu)86 意河(Yihe)0 XX0 XX73 意江(Yijiang)0 XX0 XX55 宏亮(Hongliang)88 新誠(Xincheng)55 意凌(Yiling)0 XX0 XX0 XX70 新勝(Xinsheng)66 意山(Yishan)0 XX0 XX66 意水(Yishui)0 XX0 XX/建立二叉樹家族，求家族平均年齡和輩份#define MAX 100#includetypedef structint age;char name20;DataType;typedef str

38、uct nodeDataType data;struct node *lchild,*rchild;BTree;FILE *fp;int TotalAge,TotalNumber;BTree *CreateTree();void Traversing(BTree *t);void PreOrder(BTree *t);void NodeLevel(BTree *t,int h,DataType x);void OutPutLevelNode(BTree *t,int h);void visitstring(BTree *t,int h);void main()BTree *root;DataT

39、ype x;int h;fp=fopen(p6-3.dat,r);root=CreateTree();fclose(fp);TotalAge=0;TotalNumber=0;PreOrder(root);if(TotalNumber=0)printf(n家族為空！n);exit(0);printf(一、家族的平均年齡：%.2fn,(float)TotalAge/TotalNumber);printf(n二、輸入要查找的家族成員的年齡：);scanf(%d,&x.age);printf(年齡為%d的的家族成員：n姓名 年齡 輩份n,x.age);NodeLevel(root,1,x);print

40、f(n三、輸入輩份：);scanf(%d,&h);printf(輩份為%d的所有家族的成員：n姓名 年齡 輩份n,h);if(h0)OutPutLevelNode(root,h); printf(n);BTree *CreateTree()/層次創(chuàng)建二叉樹BTree *root,*s;DataType pp;root=NULL;fscanf(fp,%d%s,&pp.age,);if(pp.age!=0)s=(BTree *)malloc(sizeof(BTree);sdata=pp;slchild=CreateTree();srchild=CreateTree();root=s;

41、return root;void Traversing(BTree *t)TotalAge+=tdata.age;TotalNumber+;void visitstring(BTree *t,int h)printf(%s%6d%6dn,,tdata.age,h);void PreOrder(BTree *t)/先序查找if(t!=NULL)Traversing(t);PreOrder(tlchild); PreOrder(trchild);void NodeLevel(BTree *t,int h,DataType x)/層次遍歷統(tǒng)計年齡if(t!=NULL) if(td

42、ata.age=x.age)visitstring(t,h); NodeLevel(tlchild,h+1,x); NodeLevel(trchild,h+1,x);void OutPutLevelNode(BTree *t,int h)/層次遍歷輸出BTree *sMAX;int i,begin,last,level,num;begin=1;last=1;level=1;num=1;slast=t;while(levelh)for(i=1;i=num;i+)if(sbeginlchild!=NULL)last+;slast=sbeginlchild; if(sbeginrchild!=NUL

43、L)last+;slast=sbeginrchild;begin+;num=last-begin+1;level+;for(i=begin;i=last;i+)visitstring(si,h);6.5 線索二叉樹rootA E B C D G F 二叉樹的指針域，有許多處于空狀態(tài)，可以加以利用，保存遍歷時該結(jié)點的直接前驅(qū)或直接后繼結(jié)點的地址，這些地址稱為線索，帶有線索的二叉樹稱為線索二叉樹。處理這樣的樹既便利又可以提高效率。 給二叉樹的結(jié)點添加線索的過程，稱為二叉樹的線索化。這樣的二叉樹稱為線索二叉樹。 如先序線索二叉樹： NULL如中序線索二叉樹： NULL NULL lchildltagdatartagrchild 其中l(wèi)tag和rtag為標志位：當ltag=0時，表示lchild為指向左孩子結(jié)點的指針；當ltag=1時，表示lchild為線索，指向前驅(qū)結(jié)點。當rtag=0時，表示rchild為指向右孩子結(jié)點的指針；當rtag=1時，表示rchild為線索，指向后