第7章樹和二叉樹

1、第7章 樹煙臺大學計算機學院數據結構課程組樹例與特征n社會的組織結構社會的組織結構n家族的族譜家族的族譜n計算機中的目錄組織計算機中的目錄組織描述層次結構，是一種一對多的邏輯關系描述層次結構，是一種一對多的邏輯關系樹的定義 w 樹樹(Tree)(Tree)是n(n=0)個結點的有限集。n=0時稱為空樹。w（注：（注：KNUTH定義樹不能為空）定義樹不能為空）n有且僅有一個稱為根的結點（Root）；nn1時，其余結點可分為m(m0)個互不相交的有限集T1,T2,Tm,其中每個集合又是一棵樹，稱為子樹(SubTree)ABCDEHFI1234G樹定義ACBGFEHIJDMKLAT1T2T3樹的抽象

2、數據類型樹的抽象數據類型ADT Tree數據對象數據對象 D：D是具有相同特性的數據元素的是具有相同特性的數據元素的集合。集合。 數據關系數據關系 R：若：若D為空集，則稱為空樹；為空集，則稱為空樹； 若若D僅含有一個數據元素，則僅含有一個數據元素，則R為空集，否為空集，否則則R=H，H是如下定義的二元關系：是如下定義的二元關系：（1 1）在在D中存在唯一的稱為根的數據元素中存在唯一的稱為根的數據元素root，它在關系，它在關系H下無前驅；下無前驅； （轉下頁）（轉下頁） 樹的抽象數據類型樹的抽象數據類型（2）若）若D-root,則存在則存在D-root的一個劃分的一個劃分D1，D2,Dm（m

3、0）,對任意對任意j k(1 j,k m)有有Dj Dk= ,且對任意的且對任意的i(1 i m ),存在唯一數據元素存在唯一數據元素xi Di , H;（ 3 ） 對 應 于） 對 應 于 D - r o o t 的 劃 分 ，的 劃 分 ， H -,有唯一的一個劃分有唯一的一個劃分H1, H2,Hm(m0),對任意對任意j k(1 j,k m)有有Hj Hk= ,且且對任意對任意i(1 i m )，Hi是是Di上的二元關系，（上的二元關系，（Di，Hi）是一棵符合本定義的樹，稱為根）是一棵符合本定義的樹，稱為根root的子樹。的子樹。 （轉下頁）（轉下頁）TreeInit(T);TreeC

4、hild(T,x,i);Treebuild(T,F);TreeClear(T);Traverse(T);TreeRoot(T);TreeParent(T,x);TreeRightBrother(T,x);TreeLeftBrother(T,x);TreeInsert(T,y,i,x);ADT Tree樹的抽象數據類型樹的其它表示方式ACBGFEHIJDMKLAJIMHDGCFLKEB凹入表示凹入表示ABFEKLGCDHMIJ嵌套集合嵌套集合（文氏圖）（文氏圖）(A(B(E(K,L),F),C(G),D(H(M),I,J)廣義表廣義表（括號法）（括號法）w 結點結點：一個數據元素及若干指向其子樹

5、的分支；一個數據元素及若干指向其子樹的分支；w 結點的度結點的度：結點擁有的子樹的數目。結點擁有的子樹的數目。w 樹的度樹的度：樹內各結點的度的最大值；：樹內各結點的度的最大值；w 葉子葉子（終端結點）：度為（終端結點）：度為0的結點；的結點；w 分支結點分支結點（非終端結點）：度不為（非終端結點）：度不為0的結點；除的結點；除根結點外，也稱內部結點；根結點外，也稱內部結點；樹的概念ACBGFEHIJDMKLw 孩子，雙親，孩子，雙親，兄弟，兄弟，堂兄堂兄：結點的子樹的根稱：結點的子樹的根稱為該結點的孩子；該結點稱為孩子的雙親；同為該結點的孩子；該結點稱為孩子的雙親；同一個雙親的孩子之間互稱兄

6、弟；一個雙親的孩子之間互稱兄弟；其父結點是兄其父結點是兄弟的結點互稱堂兄。弟的結點互稱堂兄。樹的概念ACBGFEHIJDMKL概念w 祖先祖先：從根結點到該結點所經分支上的所：從根結點到該結點所經分支上的所有結點。有結點。w 子孫子孫：以某結點為根的子樹中的任一結點：以某結點為根的子樹中的任一結點都稱為該結點的子孫。都稱為該結點的子孫。w 層次層次：結點在樹結構中的層（：結點在樹結構中的層（一般定義根一般定義根為為1層）層）ACBGFEHIJDMKL概念w 深度深度：樹中結點的最大層次稱為樹的深度；：樹中結點的最大層次稱為樹的深度；w 有序樹有序樹：結點的子樹在樹中的位置固定，：結點的子樹在樹

7、中的位置固定，不能互換，稱有序樹不能互換，稱有序樹w 無序樹無序樹：可以互換：可以互換w 森林森林：m(m0)棵互不相交的樹的集合?？没ゲ幌嘟坏臉涞募?。ACBGFEHIJDMKL二叉樹的概念 w 二叉樹二叉樹(Binary Tree)(Binary Tree)：或者是一棵空樹，或者是一棵空樹，或者是一棵由一個根結點和兩棵互不相交或者是一棵由一個根結點和兩棵互不相交的左子樹和右子樹所組成的非空樹，左子的左子樹和右子樹所組成的非空樹，左子樹和右子樹又同樣都是二叉樹樹和右子樹又同樣都是二叉樹 w 特征特征：n每個結點最多只有兩棵子樹每個結點最多只有兩棵子樹n子樹有左右之分，其次序子樹有左右之分，其

8、次序不能任意顛倒，只有一棵子不能任意顛倒，只有一棵子樹時也必須分清左右子樹。樹時也必須分清左右子樹。 D D E EB B F F G G C CA A二叉樹的抽象數據類型ADT BinTree 數據對象數據對象D：D是具有相同特性的數據元素的集合。是具有相同特性的數據元素的集合。 數據關系數據關系R：若：若D= ，則，則R= ，稱二叉樹為空二叉樹；，稱二叉樹為空二叉樹； 若若D，則，則R=H，H是如下二元關系：是如下二元關系： （1）在）在D中存在唯一的稱為根的數據元素中存在唯一的稱為根的數據元素root，它在關系，它在關系H下無下無前驅；前驅； （2）若）若D-root,則存在則存在D-r

9、oot=D1,Dr,且且 D1 Dr； （3）若）若D1，則，則D1中存在唯一的元素中存在唯一的元素x1, H,且存在且存在D1上的關系上的關系H1 H；若；若Dr,則則Dr中存在唯一的元素中存在唯一的元素xr, H, 且存在且存在Dr上的關系上的關系Hr H；H=, H1, Hr; （4）（）（D1，H1）是一棵符合本定義的二叉樹，稱為根的左子）是一棵符合本定義的二叉樹，稱為根的左子樹，（樹，（Dr，Hr）是一棵符合本定義的二叉樹，稱為根的右子）是一棵符合本定義的二叉樹，稱為根的右子樹。樹。基本操作如下：基本操作如下：二叉樹的抽象數據類型BiTreeInit (BT);BiTreeRoot(

10、BT);BiTreeParent(BT,x);BiTreeLeftChild (BT,x);BiTreeRightChild (BT,x);BiTreeBuild(BT,LBT,RBT);BiTreeInsertLeft(BT,y,x);BiTreeInsertRight(BT,y,x);BiTreeDeleteLeft(BT,x);BiTreeDeleteRight(BT,x);BiTreeClear(BT);BiTraverse(BT);ADT BinTree 二叉樹的五種形態(tài)(a)(a)(b)(b)(c)(c)(d)(d)(e)(e)二叉樹的性質1.1.一個非空二叉樹的第一個非空二叉樹的

11、第i i層上至多有層上至多有2 2i-1i-1個結個結點（點（i i 1 1） 證明：i = 1, 只有根結點，顯然成立設i = k時成立，最多有2k-1當i= k+1時，最多的 結點個數： 2k-1 * 2 = 2k-1+1 = 2k = 2( k+1)-11891011121314154526732.2.深度為深度為k k的二叉樹至多有的二叉樹至多有2 2k k-1-1個結點個結點(k(k 1)1) 二叉樹的性質證明：二叉樹的結點個數為：1 + 2 + + 2k-1= 2k-1189101112131415452673二叉樹的性質3.3.對任何一棵二叉樹對任何一棵二叉樹T T，如果其終端結

12、點數，如果其終端結點數為為n0n0，度為，度為2 2的結點數的結點數為為n2n2，則，則n0=n2+1n0=n2+1。證明：設n1為T中度為1的結點數，則總結點數：n = n0 + n1 + n2 (1) 189101112452673二叉樹的性質另：除根結點外，所有結點都有且僅有一個雙親結點，也就是僅有一個分支進入，若B為分支數，則n= B+1 = n1 + 2 * n2+1 (2) 由(1)和(2)有： n1 + 2 * n2 1 = n0 + n1 + n2 故 n0 = n2 + 1;189101112452673滿二叉樹w 滿二叉樹滿二叉樹：深度為深度為k且有且有2k-1個結點的二叉

13、樹個結點的二叉樹189101112131415452673滿二叉樹滿二叉樹w考慮到有序性，考慮到有序性，任一結點在樹中任一結點在樹中都有確切的位置，都有確切的位置，因此可以對滿二因此可以對滿二叉樹進行編號。叉樹進行編號。編號方式為：從編號方式為：從上到下，從左到上到下，從左到右。右。完全二叉樹w 完全二叉樹：完全二叉樹：深度為深度為k，有，有n個結點的二叉?zhèn)€結點的二叉樹，當且僅當樹，當且僅當其每一個結點其每一個結點都與深度為都與深度為k的的滿二叉樹編號滿二叉樹編號從從1到到n的結點的結點一一對應時，一一對應時，稱為完全二叉稱為完全二叉樹。樹。189101112452673完全二完全二叉樹叉樹完

14、全二叉樹w特征：特征：n葉子結點只可能在層次最大的兩層上葉子結點只可能在層次最大的兩層上出現。出現。n任一結點，若其右分支下的子孫的最任一結點，若其右分支下的子孫的最大層次為大層次為l，則其左分支下的最大層次，則其左分支下的最大層次為為l或或l+1，即若結點，即若結點無左子女無左子女，決不決不應有右子女應有右子女。完全二叉樹的特性（1）1.1.具有具有n n個結點的完全二叉樹的深度個結點的完全二叉樹的深度 k = k = loglog2 2n n +1 +1 （ x 表示不大于表示不大于x的最大整數的最大整數）證明：設二叉樹的深度為證明：設二叉樹的深度為k，則：，則： 2k-1 1 n 2k

15、1 2k-1 n 2k k-1 log2n 1,則其雙親結點是則其雙親結點是 i/2 。 （b）如果）如果2in,則結點則結點i無左孩子，無左孩子，i為葉子結點為葉子結點,否則其左孩子是結點否則其左孩子是結點2i。 （c）如果）如果2i+1n，則結點，則結點i無右孩子，否則其右無右孩子，否則其右孩子是結點孩子是結點2i+1。 示意圖2i2i2i+12i+1i i2i+22i+22i+32i+3i+1i+1 i/2i/2 j層j+1層示意圖189101112452673性質舉例1.1.設一棵完全二叉樹共有設一棵完全二叉樹共有700700個結點，則該個結點，則該二叉樹有幾個葉子結點，有幾個度為二叉

16、樹有幾個葉子結點，有幾個度為1 1的的結點？結點？2.2.設樹設樹T T的度為的度為4 4，其中度為，其中度為1 1，2 2，3 3，4 4的結的結點個數分別為點個數分別為4 4，2 2，1 1，1 1。則。則T T中有幾個中有幾個葉子結點。葉子結點。 350350個，個，1 1個個 8 8個個n=n0+n1+n2+n3+n4n=n0+n1+n2+n3+n4 =B+1=4n4+3n3+2n2+n1 +1 =B+1=4n4+3n3+2n2+n1 +1n0=3n4+2n3+n2+1=3+2+2+1n0=3n4+2n3+n2+1=3+2+2+1完全二叉樹性質的推論w n個結點的完全二叉樹個結點的完全

17、二叉樹中：中：n 度為度為1的結點的結點數為數為(n+1)%2; n 度為度為0的結點數為的結點數為 (n+1)/2 ；n 度為度為2的結點數為的結點數為 (n+1)/2 -1；n 編號最大的分支結點是編號最大的分支結點是 n/2 ；n 編號最小的葉子結點是編號最小的葉子結點是 n/2 +1。w n個結點的二叉樹：個結點的二叉樹：n高最多為高最多為n；n最低為最低為 log2n +1（完全二叉樹）。（完全二叉樹）。二叉樹的存儲儲結構w順序存儲結構w鏈式存儲結構二叉樹的順序存儲結構n整個二叉樹可以按照從上到下，從左到整個二叉樹可以按照從上到下，從左到右的順序編號；右的順序編號；n對于滿對于滿/完

18、全二叉樹，可以從根結點開始完全二叉樹，可以從根結點開始按序號存放；按序號存放；n對于一般的二叉樹，可以參照滿二叉樹對于一般的二叉樹，可以參照滿二叉樹的編號方法進行編號，位置空的結點空的編號方法進行編號，位置空的結點空置。置。順序存儲結構舉例A AH HI I J JD DE EB BF FG GC C完全二叉樹12345678910ABCDEFGHIJ順序存儲結構舉例ABCDEFGHA AG G H HD DE EB BF FC C一般二叉樹一般二叉樹12345678910順序存儲結構舉例非完全二非完全二叉樹叉樹ABCXABCA B C 二叉樹的鏈式存儲結構w 二叉鏈表二叉鏈表w 三叉鏈表三叉

19、鏈表w （線索鏈表）（線索鏈表）lchilddatarchilddatalchild rchildlchilddatarchildparentdatalchild rchildparent鏈式存儲結構示例ACFEDBADBCEFABCDEF二叉鏈表二叉鏈表三叉鏈表三叉鏈表二叉鏈表的類C表示 二叉樹的二叉鏈表存儲表示二叉樹的二叉鏈表存儲表示typedef struct Node ElemType data; struct Node * *lchild, * *rchild; 左右孩子指針左右孩子指針 BTNode,*BiTree；二叉樹的遍歷二叉樹的遍歷 二叉樹的遍歷的定義二叉樹的遍歷的定義：

20、按某種規(guī)律，訪問二叉樹的結點，使每按某種規(guī)律，訪問二叉樹的結點，使每個結點被訪問一次且僅一次。訪問的含義個結點被訪問一次且僅一次。訪問的含義包括查詢、打印、計算、修改等對結點的包括查詢、打印、計算、修改等對結點的操作。操作。 二叉樹的遍歷二叉樹的遍歷 遍歷的過程，實際上是按某種規(guī)律，遍歷的過程，實際上是按某種規(guī)律，將一個非線性結構的結點排成一個線性序將一個非線性結構的結點排成一個線性序列，使每個結點在這種遍歷中有唯一前驅列，使每個結點在這種遍歷中有唯一前驅和后繼關系。和后繼關系。 一棵二叉樹的遍歷序列（在某種遍歷一棵二叉樹的遍歷序列（在某種遍歷方式下）是唯一的，但一般說，二叉樹不方式下）是唯一

21、的，但一般說，二叉樹不能由某一遍歷序列唯一確定。能由某一遍歷序列唯一確定。二叉樹的遍歷二叉樹的遍歷 w 層次遍歷層次遍歷w 遞歸遍歷遞歸遍歷ACFEDBDLR，DRL，LDR，RDL，LRD，RLDABCDEFDLR二叉樹的遍歷二叉樹的遍歷 w 前序遍歷二叉樹前序遍歷二叉樹w 中序遍歷二叉樹中序遍歷二叉樹w 后序遍歷二叉樹后序遍歷二叉樹訪問根結點；訪問根結點；前序遍歷左子樹；前序遍歷左子樹；前序遍歷右子樹前序遍歷右子樹； 中序遍歷左子樹；中序遍歷左子樹；訪問根結點；訪問根結點；中序遍歷右子樹；中序遍歷右子樹； 后序遍歷左子樹；后序遍歷左子樹；后序遍歷右子樹；后序遍歷右子樹； 訪問根結點；訪問根

22、結點；D DL LR RLDRLDR、LRDLRD、DLRDLRRDLRDL、RLDRLD、DRLDRL若二叉樹為空，則空操作，否則：若二叉樹為空，則空操作，否則：ADBCD L RAD L RD L RBDCD L R前序遍歷序列：前序遍歷序列：A B D CA B D C前序遍歷ADBCL D RBL D RL D RADCL D R中序遍歷序列：中序遍歷序列：B D A CB D A C中序遍歷ADBC L R DL R DL R DADCL R D后序遍歷序列：后序遍歷序列： D B C AD B C A后序遍歷B遞歸遍歷舉例abcdgefABCDEF前序序列：前序序列：abdefcg

23、中序序列：中序序列：dfebagc后序序列：后序序列：fedbgca前序序列：前序序列：abcdef中序序列：中序序列：cbefda后序序列：后序序列：cfedba中序遍歷二叉樹的遞歸算法void InOrder (BTNode *T) if(T) 二叉樹非空二叉樹非空 InOrder (T-lchild); 中序遍歷左子樹中序遍歷左子樹 visit(T-data); 訪問根結點訪問根結點 InOrder (T-rchild); 中序遍歷右子樹中序遍歷右子樹 if InOrder 前序遍歷前序遍歷(PreOrder)和后序遍歷和后序遍歷(PostOrder)同同中序遍歷的區(qū)別只是中序遍歷的區(qū)別

24、只是visit的位置不同。的位置不同。圖例CFEDBABCEF DA二叉樹的層次遍歷算法void LevelOrder (BTNode *T) BTNode *p; if(T) 二叉樹非空二叉樹非空 InitQueue (Q); /初始化隊列初始化隊列 EnQueue (Q,T); 根首先入隊根首先入隊 while(QueueEmpty (Q)!=true) DeQueue(Q,p); /取出隊首元素放入取出隊首元素放入p中中 visit(p-data); /訪問元素，例如訪問元素，例如coutdata if(p-lchild!=NULL) /左孩子非空入隊左孩子非空入隊 EnQueue (Q

25、,p-lchild); if(p-rchild!=NULL) /右孩子非空入隊右孩子非空入隊 EnQueue (Q,p-rchild); if ACFEDB二叉樹的中序非遞歸遍歷 設設S為一個棧，為一個棧，t為指向根結點的指針，為指向根結點的指針， 其處理其處理過程為：過程為：（1）當）當t非空時，將非空時，將t所指結點的地址進棧，并所指結點的地址進棧，并將將t指向該結點的左子樹；指向該結點的左子樹；（2）當）當t為空時，彈出棧頂元素，顯示結點元素為空時，彈出棧頂元素，顯示結點元素，并將，并將t指向該結點的右子樹；指向該結點的右子樹；（3）重復（）重復（1）、（）、（2）步驟，直到?？涨遥┎襟E

26、，直到?？涨襱 也為也為空空。 void inorder (BTNode *t) BTNode *sn+1; top=0; while (t!=null | top!=0) while (t!=null) s+top=t; t=t-lchild ; if (top!=0) t=stop-; coutdata; t=t-rchild; InOrder中序非遞歸遍歷 算法cba非遞歸中序遍歷棧S的變化cbat”t”t”a”at”NULL”a出棧出棧t”NULL”出棧出棧bt”b”t”NULL”b出棧出棧t”NULL”出棧出棧t”c”ct”NULL”c出棧出棧t”NULL”棧空?？战Y束結束void

27、preorder (BTNode *t) BTNode *sn+1; top=0; while (t!=null | top!=0) while (t!=null) coutdata; s+top=t; t=t-lchild ; if (top!=0) t=stop-rchild; preorder前序非遞歸遍歷 算法cbavoid postorder (BTNode *t) typedef struct node BTNode *t; int tag; /tag 0.1，0表示表示 stack; /未遍歷右子樹未遍歷右子樹 stack sn+1 ; top=0; while (t!=null

28、 | top!=0) while (t!=null) s+top.t=t; stop.tag=0; t=t-lchild; while (top!=0 & stop.tag=1) coutdata; if (top) stop.tag=1; t=stop.t-rchild ; postorder后序非遞歸遍歷 算法cba建立二叉樹BTNode* CreatBiTree() 按前序構造二叉鏈表表示的二叉樹按前序構造二叉鏈表表示的二叉樹T BTNode *T; cinch; if(ch= =# ) T=NULLNULL; /以以#表示空表示空 else / T=new BTNode; T-

29、data=ch; 生成根結點生成根結點 T-lchild=CreatBiTree(); 生成左子樹生成左子樹 T-rchild=CreatBiTree(); 生成左子樹生成左子樹 if return T; CreatBiTree 輸入序列為：輸入序列為：- -a#b#c#a#b#c#cba#遍歷舉例ACFEDB前序序列為：前序序列為：A B E C D FA B E C D F 中序序列為：中序序列為：B E A D F CB E A D F C 后序序列為：后序序列為：E B F D C AE B F D C A 已知前序和中序遍歷序列，畫出已知前序和中序遍歷序列，畫出二叉樹二叉樹，寫出后，

30、寫出后序序遍歷序序列。遍歷序序列。若序列為：若序列為：C F D A E B ,C F D A E B ,應如何遍歷應如何遍歷 二叉樹結構的性質w 已知二叉樹的已知二叉樹的先序序列和中序序列先序序列和中序序列，可，可以唯一確定一棵二叉樹。以唯一確定一棵二叉樹。w 已知二叉樹的已知二叉樹的后序序列和中序序列后序序列和中序序列，可，可以唯一確定一棵二叉樹；以唯一確定一棵二叉樹；w 已知二叉樹的已知二叉樹的先序序列和后序序列先序序列和后序序列，不，不能唯一確定一棵二叉樹；能唯一確定一棵二叉樹；(如如AB與與BA)w 已知二叉樹的已知二叉樹的層次序列和中序序列層次序列和中序序列，可，可以唯一確定一棵二

31、叉樹。以唯一確定一棵二叉樹。表達式的二叉樹表示+*+fhg*+abc+de用二叉樹可以表示表達式用二叉樹可以表示表達式前序遍歷：前序遍歷：*+ab*c+def+gh中序遍歷：中序遍歷：a+b+c*d+e+f*g+h后序遍歷：后序遍歷：ab+cde+*+f+gh+*表達式表達式: (a+b)+c*(d+e)+f)*(g+h)二叉樹遍歷算法的應用(1)w 以二叉鏈表作存儲結構，試編寫求二叉樹深度以二叉鏈表作存儲結構，試編寫求二叉樹深度的算法。的算法。w int BTHeight(BTNode *T)w if(T=NULL)return 0;w elsel=BTHeight (T-lchild);w

32、 r=BTHeight (T-rchild);w return(lr?l:r)+1);w w ACFEDB二叉樹遍歷算法的應用(2)w 以二叉鏈表作為存儲結構，試編寫求二叉樹中葉子數以二叉鏈表作為存儲結構，試編寫求二叉樹中葉子數的算法。的算法。w int LeafCount(BTNode *T) w if(!T) return 0; /空樹沒有葉子空樹沒有葉子 w else if(!T-lchild&!T-rchild) return 1; /葉子結點葉子結點 w else return LeafCount(T-lchild)+LeafCount(T-rchild); /左子樹葉子數加

33、上右子樹葉子數左子樹葉子數加上右子樹葉子數 w 二叉樹遍歷算法的應用(3)w 以二叉鏈表作為存儲結構，試編寫求二叉樹中葉子數以二叉鏈表作為存儲結構，試編寫求二叉樹中葉子數的算法。的算法。(與上例不同與上例不同)w int num=0;w void LeafCount(BTNode *T) w if(T) w LeafCount(T-lchild) ; /中序遍歷左子樹中序遍歷左子樹w if(!T-lchild & !T-rchild) num+; /訪問根結訪問根結點點w LeafCount(T-rchild) ; /中序遍歷右子樹中序遍歷右子樹w w 二叉樹遍歷算法的應用(4)w 以

34、二叉鏈表作為存儲結構，設計算法交換二以二叉鏈表作為存儲結構，設計算法交換二叉樹中所有結點的左、右子樹。叉樹中所有結點的左、右子樹。w void change(BTNode *&T)w if(T!=NULL)w change(T-lchild);w change(T-rchild);w t=T-lchild;w T-lchild=T-rchild;w T-rchild=t;ww 二叉樹遍歷算法的應用(5)w 以二叉鏈表作為存儲結構，設計算法拷貝二叉樹。以二叉鏈表作為存儲結構，設計算法拷貝二叉樹。w BTNode* copy(BTNode *T)w BTNode *T1;w if(T=nu

35、ll) T1=null;w else w T1=new BTNode; /申請結點申請結點w T1-data=T-data; w T1-lchild=copy(T-lchild);w T1-rchild=copy(T-rchild);ww return T1;w 二叉樹遍歷算法的應用(6)w 由順序存儲的由順序存儲的n個結點的完全二叉樹建立二叉鏈表存儲的二個結點的完全二叉樹建立二叉鏈表存儲的二叉樹。叉樹。w BTNode* creat(ElemType A,int i)w BTNode *T;w if(in) T=null;w else w T=new BTNode; /申請結點申請結點w T

36、-data=Ai; w T-lchild=creat(A,2*i);w T-rchild=creat(A,2*i+1);ww return T;w /初始調用：初始調用：p=creat(A,1);A AH HI IJ JD DE EB BF FG GC C1 2 3 4 5 6 7 8 9 10A B C D E F G H I J二叉樹遍歷算法的應用(7)w 設一棵二叉樹中各結點的值互不相同，其前序序列設一棵二叉樹中各結點的值互不相同，其前序序列和中序序列分別存于兩個一維數組和中序序列分別存于兩個一維數組pre1.n 和和in1.n 中，試遍寫算法建立該二叉樹的二叉鏈表。中，試遍寫算法建立該

37、二叉樹的二叉鏈表。 BTNode* PreInCreat(char pre,char in,int n)/根據二叉樹前序序列根據二叉樹前序序列pre和中序序列和中序序列in建立二叉樹。建立二叉樹。l1,h1,l2,h2是序列第一和最后元素下標。是序列第一和最后元素下標。 char *p; int k; if(ndata=*pre; 前序為：前序為：A B E C D F A B E C D F 中序為：中序為：B E A D F CB E A D F C 二叉樹遍歷算法的應用(7) for(p=in;plchild=PreInCreat (pre+1,in,k)； /遞歸建立左子樹遞歸建立左子

38、樹 root-rchild=PreInCreat (pre+k+1,p+1,n-k-1)； /遞歸建立遞歸建立 / 左子樹左子樹 return b;/結束結束PreInCreat 前序為：前序為：A B E C D F A B E C D F 中序為：中序為：B E A D F CB E A D F C線索二叉樹線索二叉樹 線索二叉樹的提出：線索二叉樹的提出： 1、遍歷的實質：非線性結構線性化（前驅、遍歷的實質：非線性結構線性化（前驅、后繼）后繼）; 2、前驅和后繼是在遍歷中得到的、前驅和后繼是在遍歷中得到的; 3、知道前驅和后繼，再遍歷時就不需要棧、知道前驅和后繼，再遍歷時就不需要棧; 4、

39、可以在二叉鏈表結構中增加前驅和后繼兩、可以在二叉鏈表結構中增加前驅和后繼兩個指針域個指針域; 5、n個結點的二叉樹有個結點的二叉樹有n1個空指針，可以利個空指針，可以利用。用。線索二叉樹線索二叉樹 n個結點的二叉鏈表中含有個結點的二叉鏈表中含有n+1個空指針域，可以利用這個空指針域，可以利用這些空指針域來存放結點的前驅和后繼的信息。這些附加的指些空指針域來存放結點的前驅和后繼的信息。這些附加的指針稱為針稱為“線索線索”，加上了線索的二叉鏈表稱為，加上了線索的二叉鏈表稱為線索鏈表線索鏈表，加，加上線索的二叉樹就是上線索的二叉樹就是線索二叉樹線索二叉樹（Threaded Binary Tree）。

40、）。將二叉樹變?yōu)榫€索二叉樹的過程稱為將二叉樹變?yōu)榫€索二叉樹的過程稱為線索化線索化。 lchildltagdata rtag rchild指向結點前驅指向結點的左孩子lchildlchild:1:0ltag= 指向結點后繼指向結點的右孩子rchildrchild:1:0rtag= 線索二叉樹線索二叉樹 線索化線索化只有空指針才能加線索只有空指針才能加線索線索化按某種遍歷順序進行線索化按某種遍歷順序進行前序前驅線索化前序前驅線索化w 前序前驅線索化前序前驅線索化ABECFGHIDABECFGHID中序（全）線索二中序（全）線索二叉樹叉樹NULLACFEDBNULLA 00E 11C 01D 11F

41、 11B 00NULLA 為方便起見，在線索鏈表中增加一個頭結點，令其為方便起見，在線索鏈表中增加一個頭結點，令其lchild域指向二叉樹的根結點，域指向二叉樹的根結點，rchild域指向訪問序列的最域指向訪問序列的最后一個結點，這樣，就建立了一個后一個結點，這樣，就建立了一個雙向線索鏈表雙向線索鏈表。Thrt01NULL后序（全）線索化后序（全）線索化AEDCBHGFAEDCBHGFnull類型定義typedef struct Node ElemTyte data; struct Node * *lchild, * *rchild; 左、右孩子指針左、右孩子指針 int ltag, rtag

42、; TBTNode; 前序線索化TBTNode *pre=null;/設置前驅設置前驅void PreOrderThread(TBTNode *T)if (T!=null) if (T-lchild=null) T-ltag=1; T-lchild=pre;/設置左線索設置左線索 if (T-rchild=null) T-rtag=1; /為建立右鏈作準備為建立右鏈作準備 if (pre!=null & pre-rtag=1) pre-rchild=T; /設置前驅的右線索；設置前驅的右線索； pre=T;/前驅后移前驅后移 if (T-ltag=0) PreOrderThread(T

43、-lchild); /左子樹前序線索化左子樹前序線索化 if (T-rtag=0) PreOrderThread(T-rchild); /右子樹前序線索化右子樹前序線索化 ACFDB中序線索化二叉樹TBTNode *pre=null;/設置前驅設置前驅void InOrderThread(TBTNode *T)if (T) InOrderThread(T-lchild); /左子樹中序線索化左子樹中序線索化 if (T-lchild=null) T-ltag=1; T-lchild=pre; /左線索為左線索為pre; if (T-rchild=null) T-rtag=1; /置右標記，為右

44、線索作準備置右標記，為右線索作準備 if (pre!=null & pre-rtag=1) pre-rchild=T; /給前驅加后繼線索給前驅加后繼線索 pre=T;/前驅指針后移前驅指針后移 InOrderThread(T-rchild); /右子樹中序線索化右子樹中序線索化 /結束結束InOrderThread ACFDB后序線索化二叉樹TBTNode *pre=null;/設置前驅設置前驅void PostOrderThread(TBTNode *T)if (T) PostOrderThread(T-lchild); /左子樹后序線索化左子樹后序線索化 PostOrderThr

45、ead(T-rchild); /右子樹后序線索化右子樹后序線索化 if (T-lchild=null) T-ltag=1; T-lchild=pre; /左線索為左線索為pre; if (T-rchild=null) T-rtag=1; /置右標記，為右線索作準備置右標記，為右線索作準備 if (pre!=null & pre-rtag=1) pre-rchild=T; /給前驅加后繼線索給前驅加后繼線索 pre=T;/前驅指針后移前驅指針后移 /結束結束PostOrderThread ACFDB線索二叉樹的中序遍歷w void InorderTraverseThr(TBTNode *

46、p)w while(p) 二叉樹非空二叉樹非空w while (p-ltag=0) p=p-lchild; 找中序序列的開始結點找中序序列的開始結點w coutdata;wwhile(p&p-rtag= =1) w p=p-rchild; coutdata;/找找P的中序后繼結點的中序后繼結點w if(p) p=p-rchild;w /whilew InorderTraverseThrACFEDB帶頭結點的線索二叉樹的中序遍歷w void InorderTraverseThr(TBTNode *thrt)w p=thrt-lchild;w while(p!=thrt) 二叉樹非空二叉樹

47、非空w while (p-ltag=0) p=p-lchild; 找中序序列的開始結點找中序序列的開始結點w coutdata;wwhile(p-rtag= =1 & p-rchild!=thrt)w p=p-rchild; coutdata;/找找P的中序后繼結點的中序后繼結點w p=p-rchild;w / while(p!=thrt) w InorderTraverseThr前序線索樹上找前驅和后繼找前驅：找前驅： 困難困難找后繼找后繼： 若結點有左子女，則左子女是后繼；否則，若結點有左子女，則左子女是后繼；否則，rchild指向后繼。指向后繼。A AB BE EC CF FG

48、GH HI ID D前序線索樹上找后繼TBTNode* PreorderNext(TBTNode *p) if (p-ltag= =0) 結點有左子女結點有左子女 return(p-lchild); 結點的左子女為其前序后繼結點的左子女為其前序后繼 else return(p-rchild) ; PreorderNext中序線索樹上找前驅和后繼 中序的前驅和后繼都往上指向祖先找前驅：找前驅： 若左標記為若左標記為1，則，則lchild指向其前驅；否則，其指向其前驅；否則，其前驅是其左子樹上按中序遍歷的最后一個結點。前驅是其左子樹上按中序遍歷的最后一個結點。找后繼找后繼： 若右標記為若右標記為1

49、，則，則rchild指向其后繼；否則，指向其后繼；否則，其后繼是其右子樹上按中序遍歷的第一個結點。其后繼是其右子樹上按中序遍歷的第一個結點。ACFEDB中序線索樹上找前驅TBTNode* InorderPre(TBTNode *p)TBTNode *q; if (p-ltag= =1) 結點的左子樹為空結點的左子樹為空 q=p-lchild; 結點的左指針域為左線索，指向其前驅結點的左指針域為左線索，指向其前驅 else q=p-lchild; p結點的中序前驅是左子樹中最右邊結點結點的中序前驅是左子樹中最右邊結點 while (q-rtag=0 ) q=q-rchild; if return

50、 (q); InorderPre中序線索樹上找后繼TBTNode* InorderNext(TBTNode *p)TBTNode *q; if (p-rtag= =1) 結點的右子樹為空結點的右子樹為空 q=p-rchild; 結點的右指針域為右線索，指向其后繼結點的右指針域為右線索，指向其后繼 else q=p-rchild; P結點的中序后繼是其右子樹中最左邊結點結點的中序后繼是其右子樹中最左邊結點 while (q-ltag=0 ) q=q-lchild; if return (q); InorderNext后序線索樹上找前驅和后繼找前驅：找前驅： 若結點有右子女，則右子女是其前驅；否若

51、結點有右子女，則右子女是其前驅；否則，則，lchild指向其前驅。指向其前驅。找后繼找后繼： 困難，需要知道其雙親。困難，需要知道其雙親。AEDCBHGFnull后序線索樹上找前驅TBTNode* PostorderPre(TBTNode *p) if (p-rtag= =0) 結點有右子女結點有右子女 return(p-rchild); 結點的右子女為其后序前驅結點的右子女為其后序前驅 else return(p-lchild) ; PreorderPre線索化二叉樹比較 中序線索二叉樹在遍歷、中序線索二叉樹在遍歷、求前驅、后繼上要優(yōu)于前序和求前驅、后繼上要優(yōu)于前序和后序，最有價值。后序，最

52、有價值。線索樹上結點的插入與刪除 線索二叉樹雖然在找前趨結點和后繼線索二叉樹雖然在找前趨結點和后繼結點時優(yōu)于非線索二叉樹，但一般情況下，結點時優(yōu)于非線索二叉樹，但一般情況下，在線索二叉樹上進行插入和刪除操作時，在線索二叉樹上進行插入和刪除操作時，都會破壞線索。這樣一來，都會破壞線索。這樣一來，除修改結點指除修改結點指針外，還需要修改線索。針外，還需要修改線索。與非線索二叉樹與非線索二叉樹相比，時間消耗大。相比，時間消耗大。中序線索二叉樹上插入結點 以中序線索二叉樹為例，僅討論一下插以中序線索二叉樹為例，僅討論一下插入結點的算法。入結點的算法。設一個結點設一個結點x ,x ,插入到線索二插入到線

53、索二叉樹的某一結點叉樹的某一結點y y與與y y的右孩子之間，作為的右孩子之間，作為y y的的右子樹的根結點。右子樹的根結點。 插入后在中序序列里插入后在中序序列里x x是是y y的后繼。的后繼。yyxxACFEDByyGxx中序線索二叉樹上插入結點存在兩種情況：存在兩種情況： 1 1、y y原來的右子樹為空，則原來的右子樹為空，則x x插入后，一定是插入后，一定是一個葉子結點。一個葉子結點。 2 2、y y原來的右子樹非空，則原來的右子樹作為原來的右子樹非空，則原來的右子樹作為x x的右子樹。的右子樹。 無論哪種情況，無論哪種情況，x x的左子樹均為空的左子樹均為空，它是作為，它是作為y y

54、的中序后繼結點插入的。如果的中序后繼結點插入的。如果y y不是中序序列的終端不是中序序列的終端結點，那么它原來應該有一個后繼結點結點，那么它原來應該有一個后繼結點n,n,插入結點插入結點x x 后，后，n n就變成了就變成了x x的后繼結點。的后繼結點。 中序線索二叉樹上插入結點1 1、y y原來的右子樹為空原來的右子樹為空yyxxRRN N1 1 插入前插入前yyxxRRN N1 1 插入后插入后x-ltag=1;x-rtag=1;x-lchild=y;x-rchild=y-rchild;y-rchild=x;y-rtag=0;中序線索二叉樹上插入結點2 2、y y原來的右子樹非空原來的右子

55、樹非空yyxx插入前插入前N Nk kNN1 1pp插入后插入后N Nk kNN1 1ppyyxxx-rchild=y-rchild;x-ltag=1;x-lchild=y;y-rchild=x;從從N1開始找以開始找以N1為根為根的子樹最左邊的結點的子樹最左邊的結點pif(p-ltag=1) p-lchild=x;樹的存儲結構w考慮存儲結構時，主要考慮邏輯結構：n數據元素n數據元素之間的關系w樹的存儲結構樹的存儲結構：n順序存儲結構n鏈式存儲結構樹的存儲結構ABECDFw雙親表示法雙親表示法 w孩子表示法孩子表示法 w孩子兄弟表示法孩子兄弟表示法 雙親表示法w 使用靜態(tài)數組（本質是靜態(tài)鏈表）

56、靜態(tài)數組（本質是靜態(tài)鏈表）；w 數組的每個數據元素，包括兩個域：一個域是數據元素數據元素；另一個域用游標指示該結點的雙親結點在數組中的相對位置位置；根結點的游標為-1。w 特點：n方便找結點的雙親雙親；n順序存儲結構；雙親表示法類型定義#define MAX_NODE 64typedef struct Ptnode ElemTyte data; 數據域 int parent; 雙親指示域 PTreeMAX_NODE;雙親表示示例FGHIABCED數組下標數組下標 0 1 2 3 4 5 6 7 8 data A B C D E F G H Iparent -1 0 0 0 1 1 1 3 3雙

57、親表示法表示的樹的深度w int Depth(PTree t)w int maxdepth=0;w for(i=0;i=0) / 求結點求結點i的深度的深度w temp+; f=tf.parent; w if(tempmaxdepth) maxdepth=temp; /最大深度更新最大深度更新w w return(maxdepth); /返回樹的深度返回樹的深度w /結束結束Depth孩子表示法w 任一數據元素，有任一數據元素，有0個或多個孩子；個或多個孩子；w 因此可以設計一個鏈式存儲結構，其結點除因此可以設計一個鏈式存儲結構，其結點除放置數據元素外，還放置若干指針，分別用放置數據元素外，還

58、放置若干指針，分別用來指示該結點的所有孩子結點在存儲空間中來指示該結點的所有孩子結點在存儲空間中的位置。的位置。孩子表示法w 方法方法1 1n根據結點的度，設置結點的指針個數，比如若根據結點的度，設置結點的指針個數，比如若結點的度為結點的度為d:d:datachild1child2childd問題問題：n不同的數據元素，結點構造不同；不同的數據元素，結點構造不同；n操作不方便操作不方便孩子表示法w 方法方法2 2n按照樹的度定義結點。若樹的度為按照樹的度定義結點。若樹的度為d,定義定義degree，表示該結點的度，表示該結點的度datachild1child2childddegree問題問題：

59、n因因degree為樹的度，是所有結點的最大的度，為樹的度，是所有結點的最大的度，因此樹中有相當部分的指針域為空，浪費空間。因此樹中有相當部分的指針域為空，浪費空間。n有有n個結點的樹的度為個結點的樹的度為k，空指針域有，空指針域有 n(k-1)+1個。個。孩子表示法w 有有n個結點的樹的度為個結點的樹的度為k，空指針域有，空指針域有n(k-1)+1個。個。w 證明：證明：nn個結點的樹，除根結點外，每個結點有一個指針個結點的樹，除根結點外，每個結點有一個指針指向，也就是樹中有指向，也就是樹中有n-1個有效鏈域（指針）個有效鏈域（指針）n而按該結點定義，而按該結點定義，n個結點總的指針域個結點

60、總的指針域有：有：nk個。個。n因此空鏈域：因此空鏈域：nk (n-1) = n ( k - 1 ) + 1w 一個靜態(tài)數組，存放所有的結點一個靜態(tài)數組，存放所有的結點w 數組的每個數據元素，包括兩部分：數數組的每個數據元素，包括兩部分：數據元素，指針；指針指向一個鏈表，鏈據元素，指針；指針指向一個鏈表，鏈表結點的數據域是一個整數，表示該結表結點的數據域是一個整數，表示該結點的孩子在數組中的相對位置；點的孩子在數組中的相對位置；w 特點：特點：n順序順序+鏈式存儲結構；鏈式存儲結構；n找孩子容易，找雙親難找孩子容易，找雙親難；孩子表示法孩子表示法孩子表示法0123456546ABCDEFG312ACFEDBG雙親孩子鏈表0123456546312GABCDE