數(shù)據(jù)結(jié)構(gòu)DS06-樹

1、第 章 樹 和 二 叉 樹 第 章 樹 和 二 叉 樹 樹特點樹特點：非線性結(jié)構(gòu)，一個直接前驅(qū)，但可能有多非線性結(jié)構(gòu)，一個直接前驅(qū)，但可能有多個直接后繼。個直接后繼。第 章 樹 和 二 叉 樹 圖6.1 注：注：樹的定義具有樹的定義具有遞歸性遞歸性，即，即“樹中還有樹樹中還有樹”。第 章 樹 和 二 叉 樹 第 章 樹 和 二 叉 樹 第 章 樹 和 二 叉 樹 第 章 樹 和 二 叉 樹 第 章 樹 和 二 叉 樹 樹的結(jié)點之間的邏輯關(guān)系主要有雙親樹的結(jié)點之間的邏輯關(guān)系主要有雙親- -孩子關(guān)系，孩子關(guān)系，兄弟關(guān)系。因為樹是一種非線性結(jié)構(gòu)，所以不能簡單兄弟關(guān)系。因為樹是一種非線性結(jié)構(gòu)，所以不能

2、簡單地用一維數(shù)組或單鏈表來存儲樹。為了存儲樹，必須地用一維數(shù)組或單鏈表來存儲樹。為了存儲樹，必須把樹中每個結(jié)點之間存在的關(guān)系反映在存儲結(jié)構(gòu)之中，把樹中每個結(jié)點之間存在的關(guān)系反映在存儲結(jié)構(gòu)之中，才能如實地表現(xiàn)一棵樹。因此，從結(jié)點之間的邏輯關(guān)才能如實地表現(xiàn)一棵樹。因此，從結(jié)點之間的邏輯關(guān)系分，樹的存儲結(jié)構(gòu)主要有：系分，樹的存儲結(jié)構(gòu)主要有：雙親表示法、孩子表示雙親表示法、孩子表示法、雙親孩子表示法和孩子兄弟表示法法、雙親孩子表示法和孩子兄弟表示法四種組合。四種組合。 第 章 樹 和 二 叉 樹 1、雙親表示法、雙親表示法 該表示法要求用一維數(shù)組來存儲樹的有關(guān)信息，該表示法要求用一維數(shù)組來存儲樹的有關(guān)

3、信息，每個結(jié)點對應(yīng)一個數(shù)組元素，它包括兩個域：一個是每個結(jié)點對應(yīng)一個數(shù)組元素，它包括兩個域：一個是數(shù)據(jù)域（數(shù)據(jù)域（datadata），用來存放該結(jié)點本身所包含的數(shù)據(jù)；），用來存放該結(jié)點本身所包含的數(shù)據(jù)；一個是指針域（一個是指針域（parentparent），用來指出該結(jié)點的父結(jié)點），用來指出該結(jié)點的父結(jié)點的位置。的位置。在這種表示法下，樹中結(jié)點的形式說明如下：在這種表示法下，樹中結(jié)點的形式說明如下：#define MAX_TREE_SIZE 100#define MAX_TREE_SIZE 100typedef structtypedef struct DataType DataType da

4、ta; data; int int parent; parent;Node;Node;Node treeMAX_TREE_SIZENode treeMAX_TREE_SIZE;第 章 樹 和 二 叉 樹 1 1、雙親表示法、雙親表示法 (a)(a)一棵樹一棵樹 （b)b)仿真指針的雙親表示法存儲結(jié)構(gòu)仿真指針的雙親表示法存儲結(jié)構(gòu) 圖圖 樹的雙親表示法存儲結(jié)構(gòu)樹的雙親表示法存儲結(jié)構(gòu) 尋找雙尋找雙親容易，親容易，找孩子找孩子難難ABDEFHICG4H2G1F1E1D0C0B-1AI4data parentdata parent0 01 12 23 35 56 67 78 89 9第 章 樹 和 二

5、叉 樹 2 2、孩子表示法、孩子表示法圖圖 樹的孩子法存儲結(jié)構(gòu)樹的孩子法存儲結(jié)構(gòu)rootBACDEFGHI 第 章 樹 和 二 叉 樹 4H2G1F1E1D0C0B-1AI4data parent headdata parent head0 01 12 23 34 45 56 67 78 8child nextchild next871234563 3、雙親孩子表示法、雙親孩子表示法第 章 樹 和 二 叉 樹 rootBCDEFGHIA4 4、孩子兄弟表示法孩子兄弟表示法ABDEFHICG第 章 樹 和 二 叉 樹 先研究最簡單、最有規(guī)律的樹，然先研究最簡單、最有規(guī)律的樹，然后設(shè)法把一般的樹轉(zhuǎn)

6、化為簡單樹。后設(shè)法把一般的樹轉(zhuǎn)化為簡單樹。解決思路：解決思路： 從上面看出，樹的操作實現(xiàn)比較復(fù)雜從上面看出，樹的操作實現(xiàn)比較復(fù)雜。第 章 樹 和 二 叉 樹 為何要重點研究每結(jié)點最多只有兩為何要重點研究每結(jié)點最多只有兩個個 “ “叉叉” ” 的樹？的樹？ 二叉樹的結(jié)構(gòu)最簡單，規(guī)律性最強；二叉樹的結(jié)構(gòu)最簡單，規(guī)律性最強； 可以證明，所有樹都能轉(zhuǎn)為唯一對應(yīng)可以證明，所有樹都能轉(zhuǎn)為唯一對應(yīng)的二叉樹，不失一般性。的二叉樹，不失一般性。第 章 樹 和 二 叉 樹 邏輯結(jié)構(gòu)：邏輯結(jié)構(gòu)： 一對二（一對二（1:21:2） 每個結(jié)點最多只有兩棵子樹（不每個結(jié)點最多只有兩棵子樹（不存在存在度大于度大于2 2的結(jié)點

7、）；的結(jié)點）； 左子樹和右子樹左子樹和右子樹次序不能顛倒次序不能顛倒。第 章 樹 和 二 叉 樹 基本形態(tài)：基本形態(tài)：第 章 樹 和 二 叉 樹 第 章 樹 和 二 叉 樹 用歸納法證明此性質(zhì)：用歸納法證明此性質(zhì)： 當(dāng)當(dāng)i =1時，只有一個根結(jié)點，顯然時，只有一個根結(jié)點，顯然2i-1 = 21-1 = 20 =1； 現(xiàn)在假定對所有的現(xiàn)在假定對所有的j，1jleftChildroot)-leftChild=NULL;=NULL;( (* *root)-rightChildroot)-rightChild=NULL;=NULL; 第 章 樹 和 二 叉 樹 2.2.二叉樹中給某結(jié)點插入一個左結(jié)點的

8、操作二叉樹中給某結(jié)點插入一個左結(jié)點的操作 算法的基本思想算法的基本思想: : 若當(dāng)前結(jié)點若當(dāng)前結(jié)點( (假設(shè)為假設(shè)為currcurr）非空，在非空，在currcurr的左子的左子樹插入元素值為樹插入元素值為x x的新結(jié)點的新結(jié)點 ，原，原currcurr所指結(jié)點的左所指結(jié)點的左子樹成為新插入結(jié)點的左子樹。若插入成功返回新子樹成為新插入結(jié)點的左子樹。若插入成功返回新插入結(jié)點的指針，否則返回空指針。插入結(jié)點的指針，否則返回空指針。第 章 樹 和 二 叉 樹 程序?qū)崿F(xiàn)：程序?qū)崿F(xiàn)： BiTreeNode BiTreeNode * *InsertLeftNode(BiTreeNode InsertLef

9、tNode(BiTreeNode * *curr,DataType x) curr,DataType x) BiTreeNode BiTreeNode * *s, s, * *t;t; if(curr if(curr=NULL) return NULL;=NULL) return NULL;t=curr-leftChildt=curr-leftChild; ;s=(BiTreeNode s=(BiTreeNode * *)malloc(sizeof(BiTreeNode)malloc(sizeof(BiTreeNode);); s-data=x; s-data=x;s-leftChilds-l

10、eftChild=t;=t; s-rightChild s-rightChild=NULL;=NULL;curr-leftChildcurr-leftChild=s;=s;return curr-leftChildreturn curr-leftChild; ; 第 章 樹 和 二 叉 樹 3.3.刪除二叉樹中某結(jié)點的左子樹操作刪除二叉樹中某結(jié)點的左子樹操作算法的基本思想算法的基本思想: :若若currcurr非空，刪除非空，刪除currcurr所指結(jié)點的左子樹。若所指結(jié)點的左子樹。若刪除成功，返回刪除結(jié)點的雙親結(jié)點指針，否則返回空指針。刪除成功，返回刪除結(jié)點的雙親結(jié)點指針，否則返回空指針。程

11、序?qū)崿F(xiàn)：程序?qū)崿F(xiàn)：BiTreeNode BiTreeNode * *DeleteLeftTree(BiTreeNode DeleteLeftTree(BiTreeNode * *currcurr) ) if(curr=NULL|curr-leftChildif(curr=NULL|curr-leftChild=NULL)=NULL) return NULL; return NULL;Destroy(&curr-leftChildDestroy(&curr-leftChild););curr-leftChildcurr-leftChild=NULL;=NULL;return cu

12、rrreturn curr; ; 第 章 樹 和 二 叉 樹 例：例：編寫一個建立編寫一個建立圖圖7-7(b)7-7(b)所示的所示的帶頭結(jié)點的二帶頭結(jié)點的二叉鏈存儲結(jié)構(gòu)二叉樹的程序。叉鏈存儲結(jié)構(gòu)二叉樹的程序。設(shè)計：假設(shè)上述二叉樹結(jié)點結(jié)構(gòu)體定義和二叉樹設(shè)計：假設(shè)上述二叉樹結(jié)點結(jié)構(gòu)體定義和二叉樹操作實現(xiàn)函數(shù)存放在文件操作實現(xiàn)函數(shù)存放在文件“Bitree.hBitree.h”中中, ,程程序設(shè)計如下：序設(shè)計如下： #include stdlib.h#include #include stdio.h #include typedef char DataType typedef char DataTy

13、pe; ; #include Bitree.h #include Bitree.h 第 章 樹 和 二 叉 樹 void main(void)void main(void) BiTreeNode BiTreeNode * *root, root, * *p, p, * *pp;pp; Initiate(&root); Initiate(&root);p=InsertLeftNode(root,Ap=InsertLeftNode(root,A););p=InsertLeftNode(p,Bp=InsertLeftNode(p,B););p=InsertLeftNode(p,Dp=

14、InsertLeftNode(p,D););p=InsertRightNode(p,Gp=InsertRightNode(p,G););p=InsertRightNode(root-leftChild,Cp=InsertRightNode(root-leftChild,C););pp=p;pp=p;InsertLeftNode(p,EInsertLeftNode(p,E););InsertRightNode(pp,FInsertRightNode(pp,F);); rootABC DEFG第 章 樹 和 二 叉 樹 第 章 樹 和 二 叉 樹 第 章 樹 和 二 叉 樹 第 章 樹 和 二 叉

15、 樹 注意：注意：一個二叉樹的遍歷序列不能決定一棵二叉樹，但一個二叉樹的遍歷序列不能決定一棵二叉樹，但先序（或后序）和中序遍歷序列的組合先序（或后序）和中序遍歷序列的組合可以惟一確定可以惟一確定一棵二叉樹。而先序和后序遍歷則不能。一棵二叉樹。而先序和后序遍歷則不能。先根遍歷的結(jié)果是：先根遍歷的結(jié)果是：中根遍歷的結(jié)果是：中根遍歷的結(jié)果是：后根遍歷的結(jié)果是：后根遍歷的結(jié)果是： A B CD E第 章 樹 和 二 叉 樹 已知一棵二叉樹的中序序列和已知一棵二叉樹的中序序列和后序序列后序序列分別是分別是BDCEAFHG BDCEAFHG 和和 DECBHGFADECBHGFA，請畫出這棵二叉樹。，請畫

16、出這棵二叉樹。分析：分析：由后序遍歷特征，根結(jié)點必在后序序列尾部由后序遍歷特征，根結(jié)點必在后序序列尾部（即（即A A）；由中序遍歷特征，根結(jié)點必在其中間，而且其左部必由中序遍歷特征，根結(jié)點必在其中間，而且其左部必全部是左子樹的子孫全部是左子樹的子孫（即（即BDCEBDCE），），其右部必全部是右其右部必全部是右子樹的子孫子樹的子孫（即（即FHGFHG）；繼而，根據(jù)后序中的繼而，根據(jù)后序中的DECBDECB子樹可確定子樹可確定B B為為A A的左孩子，的左孩子，根據(jù)根據(jù)HGFHGF子串可確定子串可確定F F為為A A的右孩子；以此類推。的右孩子；以此類推。第 章 樹 和 二 叉 樹 已知中序遍歷

17、：已知中序遍歷：B D C E A F H G已知后序遍歷：已知后序遍歷：D E C B H G F A（B D C E）（ F H G） （D C E）BFGHCD EA第 章 樹 和 二 叉 樹 typedef structstruct Node Node datatype datatype data; data; struct Node struct Node * *LchildLchild; ; struct Node struct Node * *RchildRchild; ; BTnode,*Btree; 二叉樹結(jié)點的存儲類型二叉樹結(jié)點的存儲類型第 章 樹 和 二 叉 樹 先根遍歷

18、算法先根遍歷算法void preorder(Btree root) if(root!=NULL) Visit(root-data);/訪問根結(jié)點訪問根結(jié)點 preorder(root-Lchild);/遞歸訪問左子樹遞歸訪問左子樹 preorder(root-Rchild);/遞歸訪問右子樹遞歸訪問右子樹 第 章 樹 和 二 叉 樹 中根遍歷算法中根遍歷算法void inorder(Btree t) if(t!=NULL)inorder(t-Lchild);Visit(t-data);inorder(t-Rchild);第 章 樹 和 二 叉 樹 一棵二叉樹一棵二叉樹中根遍歷二叉樹的搜索路線中

19、根遍歷二叉樹的搜索路線第 章 樹 和 二 叉 樹 后根遍歷算法后根遍歷算法void PostOrder(Btree root)if(root!=NULL) PostOrder(root-Lchild); PostOrder(root-Rchild); Visit(root -data); 第 章 樹 和 二 叉 樹 中序遍歷二叉樹的非遞歸算法中序遍歷二叉樹的非遞歸算法這在遍歷的過程中要用棧來保存遍歷中經(jīng)過的路徑。這在遍歷的過程中要用棧來保存遍歷中經(jīng)過的路徑。void inorder(Btreevoid inorder(Btree root) root)BtreeBtree q; q; /工作指

20、針工作指針intint top top，bb; bb; /棧頂指針棧頂指針toptopBtnodeBtnode smax; smax;/數(shù)組的每個元素是鏈表結(jié)點，數(shù)組的每個元素是鏈表結(jié)點，s s當(dāng)做棧當(dāng)做棧top=0; top=0; /棧初始化棧初始化q=root; q=root; /工作指針賦初值工作指針賦初值bb=0; bb=0; /在操作過程中，當(dāng)在操作過程中，當(dāng)?？栈驐M時為棧空或棧滿時為1 1第 章 樹 和 二 叉 樹 While(bb!=1)While(bb!=1) if(q!=NULL)if(q!=NULL) top=top+1; top=top+1; if(topmax) if

21、(topmax) bb=1;printf(“ bb=1;printf(“棧滿了棧滿了”) )； else else /入棧入棧 stop=stop=* *q; q=q-Lchildq; q=q-Lchild; else else if(top=0) if(top=0) /當(dāng)當(dāng)toptop為為0 0時，說明這棵樹遍歷完了時，說明這棵樹遍歷完了 bb=1;bb=1; else else * *q q=stop=stop; ; /出棧，棧頂元素賦給出棧，棧頂元素賦給q q top=top-1; top=top-1; printf printf(“(“訪問訪問q-data”); q-data”); /

22、訪問出棧的根結(jié)點訪問出棧的根結(jié)點 q=q-Rchildq=q-Rchild; ; /搜索右子樹搜索右子樹 第 章 樹 和 二 叉 樹 第 章 樹 和 二 叉 樹 證明證明：用二叉鏈表存儲包含用二叉鏈表存儲包含n n個結(jié)點的二叉樹，結(jié)個結(jié)點的二叉樹，結(jié)點必有點必有2n個鏈域。個鏈域。除根結(jié)點外，二叉樹中每一個結(jié)點除根結(jié)點外，二叉樹中每一個結(jié)點有且僅有一個雙親有且僅有一個雙親，即每個結(jié)點地址占用了雙親的一個直接后繼，即每個結(jié)點地址占用了雙親的一個直接后繼，n n個結(jié)點地址共占用了個結(jié)點地址共占用了n-1n-1個雙親的指針域個雙親的指針域。也就是說，只會有也就是說，只會有n n1 1個結(jié)點的鏈域存放

23、指針。個結(jié)點的鏈域存放指針。所以，所以， 空指針數(shù)目空指針數(shù)目2n2n(n-1)=n+1(n-1)=n+1個。個。用二叉鏈表法（用二叉鏈表法（leftchild, rightchild）存儲包）存儲包含含n個結(jié)點個結(jié)點的二叉樹，結(jié)點的指針區(qū)域中會有多少個的二叉樹，結(jié)點的指針區(qū)域中會有多少個空空指針？指針？第 章 樹 和 二 叉 樹 思考：思考：二叉鏈表空間效率這么低，能否利用這些空二叉鏈表空間效率這么低，能否利用這些空閑區(qū)存放有用的信息或線索？閑區(qū)存放有用的信息或線索？我們可以用它來存放當(dāng)前結(jié)點的我們可以用它來存放當(dāng)前結(jié)點的直接前驅(qū)和后直接前驅(qū)和后繼繼等線索，以加快查找速度。等線索，以加快查找

24、速度。結(jié)論：用二叉鏈表法存儲包含結(jié)論：用二叉鏈表法存儲包含n n個結(jié)點的二叉樹，結(jié)個結(jié)點的二叉樹，結(jié)點的指針區(qū)域中會有點的指針區(qū)域中會有n+1n+1個空指針。個空指針。這就是這就是（Threaded Binary Tree）第 章 樹 和 二 叉 樹 第 章 樹 和 二 叉 樹 對二叉樹以某種次序進(jìn)行遍歷并且對二叉樹以某種次序進(jìn)行遍歷并且加上線索的過程叫做加上線索的過程叫做線索化。線索化。 線索化是將二叉鏈表中的空鏈域填線索化是將二叉鏈表中的空鏈域填上相應(yīng)結(jié)點在一定遍歷次序下的前驅(qū)或上相應(yīng)結(jié)點在一定遍歷次序下的前驅(qū)或后繼結(jié)點的地址。因此后繼結(jié)點的地址。因此線索化的過程就線索化的過程就是在遍歷過

25、程中修改空鏈域的過程是在遍歷過程中修改空鏈域的過程。 對二叉樹按照不同的遍歷次序進(jìn)行對二叉樹按照不同的遍歷次序進(jìn)行線索化，可以得到不同的線索二叉樹。線索化，可以得到不同的線索二叉樹。第 章 樹 和 二 叉 樹 0 Lchild0 Lchild指向結(jié)點的左孩子指向結(jié)點的左孩子 LtagLtag= = 1 Lchild1 Lchild指向該結(jié)點的前驅(qū)指向該結(jié)點的前驅(qū) 0 Rchild0 Rchild指向該結(jié)點的右孩子指向該結(jié)點的右孩子 RtagRtag= = 1 Rchild 1 Rchild指向該結(jié)點的后繼指向該結(jié)點的后繼左標(biāo)志的含義左標(biāo)志的含義右標(biāo)志的含義右標(biāo)志的含義第 章 樹 和 二 叉 樹

26、 typedeftypedef structstruct Node Node datatype datatype data; data; struct Node struct Node * *LchildLchild; ; struct Node struct Node * *RchildRchild; ; int Ltag, Rtag int Ltag, Rtag; ; ThreadTnode, ThreadTnode,* *ThreadTtreeThreadTtree; ;線索二叉樹的數(shù)據(jù)類型定義為：線索二叉樹的數(shù)據(jù)類型定義為：第 章 樹 和 二 叉 樹 中序線索二叉樹中序線索二叉樹中序線

27、索二叉樹示例中序線索二叉樹示例第 章 樹 和 二 叉 樹 ABCGEIDHFroot懸空？懸空？ NILNIL懸空？懸空？ NILNIL 對該二叉樹對該二叉樹中序中序遍歷的結(jié)果為遍歷的結(jié)果為: : H, D, I, B, E, A, F, C, G所以添加線索應(yīng)當(dāng)按如下路徑進(jìn)行：所以添加線索應(yīng)當(dāng)按如下路徑進(jìn)行：為避免懸空為避免懸空態(tài)，應(yīng)增設(shè)態(tài)，應(yīng)增設(shè)一個頭結(jié)點一個頭結(jié)點例例: :畫出以下二叉樹對應(yīng)的畫出以下二叉樹對應(yīng)的中序中序線索二叉樹。線索二叉樹。第 章 樹 和 二 叉 樹 例：例：給定如圖所示二叉樹給定如圖所示二叉樹T T，請畫出與其對應(yīng)的中，請畫出與其對應(yīng)的中序線索二叉樹。序線索二叉樹。

28、 因為中序遍歷序列是：因為中序遍歷序列是：5555 40 25 60 28 08 33 40 25 60 28 08 33 5454對應(yīng)線索樹應(yīng)當(dāng)按此規(guī)律連線，即在原二叉樹中添對應(yīng)線索樹應(yīng)當(dāng)按此規(guī)律連線，即在原二叉樹中添加虛線加虛線。2825405560330854NILNILNILNIL第 章 樹 和 二 叉 樹 中根遍歷線索化中根遍歷線索化( (給二叉樹穿線給二叉樹穿線) )的算法。的算法。ThreadTtreeThreadTtree pre=NULL; pre=NULL;Void Inthread (ThreadTtreeVoid Inthread (ThreadTtree root)

29、root)ThreadTtreeThreadTtree p; p; /p/p是工作指針是工作指針 if (root= = NULL) return; if (root= = NULL) return; p=root; p=root; /樹不空時樹不空時 Inthread(p-LchildInthread(p-Lchild); ); if (p-Lchild if (p-Lchild=NULL) =NULL) /左孩子空則穿線，修改左標(biāo)志左孩子空則穿線，修改左標(biāo)志 p-Ltag=1; p-Lchild p-Ltag=1; p-Lchild=pre; =pre; if (pre!=NULL&

30、; pre-Rchild if (pre!=NULL& pre-Rchild=NULL) =NULL) /建右線索建右線索 pre- Rchild=p; pre-Rtagpre- Rchild=p; pre-Rtag=1; =1; pre=p pre=p； / / prepre指向剛剛訪問過的結(jié)點，這樣下次再訪問新結(jié)點時，指向剛剛訪問過的結(jié)點，這樣下次再訪問新結(jié)點時，prepre為其前驅(qū)為其前驅(qū) Inthread(p-RchildInthread(p-Rchild); ); 建立一棵中序線建立一棵中序線索樹的遞歸算法索樹的遞歸算法第 章 樹 和 二 叉 樹 建立建立中序中序線索樹的線索

31、樹的非遞歸算法非遞歸算法(在建好的二叉鏈表結(jié)在建好的二叉鏈表結(jié)構(gòu)上穿線構(gòu)上穿線),就是在中序遍歷的算法中就是在中序遍歷的算法中,訪問根結(jié)點的同時訪問根結(jié)點的同時,將空鏈域逐個用線索代替將空鏈域逐個用線索代替。在穿線過程中要用棧來保存遍歷在穿線過程中要用棧來保存遍歷中經(jīng)過的路徑，才能訪問到二叉樹中的每一個結(jié)點中經(jīng)過的路徑，才能訪問到二叉樹中的每一個結(jié)點。ThreadTtreeThreadTtree tbtree(ThreadTtreeThreadTtree t) / t是二叉鏈表的表頭指針是二叉鏈表的表頭指針ThreadTtreeThreadTtree smax,p,pr; /s是指針數(shù)組，是棧

32、是指針數(shù)組，是棧 int top; /top是棧頂指針是棧頂指針 pr=Null; /初始化指針初始化指針pr, pr是是p的前驅(qū)指針的前驅(qū)指針 top=0; /初始化棧頂指針初始化棧頂指針top p=t; /p為工作指針，開始時指向根為工作指針，開始時指向根 第 章 樹 和 二 叉 樹 while(p!=Null|top!=0) while(p!=Null) top+;stop=p;p=p-Lchild;/p入棧并繼續(xù)搜索入棧并繼續(xù)搜索p的左子樹的左子樹if(top!=0) /棧不空，出棧并穿線索，包括左線索和右線索棧不空，出棧并穿線索，包括左線索和右線索 p=stop;top-;print

33、f(“%c”,p-data); /出棧出棧,放入放入p中，訪問中，訪問p結(jié)點結(jié)點 if(p-Lchild =Null) /p無左孩子，無左孩子，p是剛退棧的結(jié)點是剛退棧的結(jié)點 p-Ltag=1;p-Lchild=pr; /p的左孩子指向的左孩子指向p的前驅(qū)的前驅(qū) else p-Ltag=0; /p有左孩子，修改左標(biāo)志為有左孩子，修改左標(biāo)志為0。這時。這時p的左鏈已指向其左孩子的左鏈已指向其左孩子 if(pr!=NUll) /前驅(qū)前驅(qū)pr不為空不為空 if(pr-Rchild =Null)pr-Rchild =p; pr-Rtag=1; else pr-Rtag=0; /pr有右孩子時令有右孩子

34、時令p的前驅(qū)的前驅(qū)pr的右標(biāo)志為的右標(biāo)志為0 pr=p;p= p-Rchild; /修改修改pr，繼續(xù)搜索，繼續(xù)搜索p的右子樹的右子樹 pr-Rtag=1; /最后一個結(jié)點無后繼最后一個結(jié)點無后繼 可在此舉檢索結(jié)點的例子。可在此舉檢索結(jié)點的例子。abdcef第 章 樹 和 二 叉 樹 第 章 樹 和 二 叉 樹 Void paintnode (BtreeVoid paintnode (Btree root) root) if (root!=NULL) if (root!=NULL) printf printf (root -data); (root -data); paintnode (roo

35、t -Lchild paintnode (root -Lchild);); paintnode (root -Rchild paintnode (root -Rchild);); 第 章 樹 和 二 叉 樹 Void paintleaf (BtreeVoid paintleaf (Btree root) root) / root/ root是指向根結(jié)點的指針是指向根結(jié)點的指針 if (root!=NULL) if (root!=NULL) if(root-Lchild= =NULL & root-Rchildif(root-Lchild= =NULL & root-Rchild

36、= =NULL)= =NULL)printfprintf (root -data); (root -data);paintleaf (root -Lchildpaintleaf (root -Lchild););paintleaf (root -Rchildpaintleaf (root -Rchild);); 第 章 樹 和 二 叉 樹 Void leafcount(BtreeVoid leafcount(Btree root) root) if(root!=NULL)if(root!=NULL) leafcount(root-Lchildleafcount(root-Lchild););l

37、eafcount(root-Rchildleafcount(root-Rchild););if (root-Lchild= =NULL & root-Rchildif (root-Lchild= =NULL & root-Rchild= =NULL)= =NULL)count+;count+; 第 章 樹 和 二 叉 樹 第 章 樹 和 二 叉 樹 void CreateBtree(Btree btvoid CreateBtree(Btree bt) ) /先根遍歷先根遍歷 char chchar ch; ; ch=getchar ch=getchar();(); if(ch

38、if(ch= =.) = =.) bt bt=NULL; =NULL; /生成空子樹生成空子樹 elseelse bt=(Btree)malloc(sizeof(BTnode bt=(Btree)malloc(sizeof(BTnode); ); /申請結(jié)點申請結(jié)點 bt-data= chbt-data= ch; ; /為結(jié)點的數(shù)據(jù)域賦值為結(jié)點的數(shù)據(jù)域賦值 CreateBiTree( bt-LchildCreateBiTree( bt-Lchild ); ); /生左子樹生左子樹 CreateBiTree( bt-RchildCreateBiTree( bt-Rchild ); ); /生右子

39、樹生右子樹 第 章 樹 和 二 叉 樹 第 章 樹 和 二 叉 樹 int TreeDepth(Btree btint TreeDepth(Btree bt) ) int int hl,hr,max; hl,hr,max; if(bt if(bt!=NULL)!=NULL) hl=TreeDepth(bt-Lchild hl=TreeDepth(bt-Lchild););/左子樹的高度左子樹的高度 hr=TreeDepth(bt-Rchildhr=TreeDepth(bt-Rchild););/右子樹的高度右子樹的高度 max = (hl max = (hl，hr); hr); /取左、右子樹

40、高度的最大者取左、右子樹高度的最大者 return(max+1);return(max+1); else return(0); else return(0); 第 章 樹 和 二 叉 樹 第 章 樹 和 二 叉 樹 ThreadTnodeThreadTnode * *pre; /ppre; /p的前驅(qū)的前驅(qū)ThreadTnode Previ (ThreadTnodeThreadTnode Previ (ThreadTnode * * p) p) ThreadTnode ThreadTnode * *q;q; if(p-Ltag if(p-Ltag= =1) = =1) /p/p無左孩子無左孩子

41、 pre = p-Lchildpre = p-Lchild; ; else else /p/p有左孩子有左孩子 for( for(q = p-Lchildq = p-Lchild; ; q-Rtag q-Rtag= =0;= =0; q =q-Rchild q =q-Rchild);); pre=q; pre=q; 第 章 樹 和 二 叉 樹 ThreadTnode Previ(ThreadTnodeThreadTnode Previ(ThreadTnode * * p) p) ThreadTnode ThreadTnode * *q;q; if(p-Ltag if(p-Ltag= =1)=

42、=1) return(p-Lchild return(p-Lchild); ); q = p-Lchild q = p-Lchild; ; while(q-Rtag while(q-Rtag= =0)= =0) q = p-Rchild q = p-Rchild; ; return(q); return(q); 第 章 樹 和 二 叉 樹 第 章 樹 和 二 叉 樹 ThreadTnode Succedent(ThreadTnodeThreadTnode Succedent(ThreadTnode * *p)p) ThreadTnode ThreadTnode * *q;q; if (p-Rt

43、ag if (p-Rtag = =1) = =1) return(p-Rchild return(p-Rchild);); else else for(q = p-RChild for(q = p-RChild; ; q-Ltag q-Ltag = =0 ; = =0 ; q =q-LChild q =q-LChild ); ); return(q); return(q); q q的算法的算法第 章 樹 和 二 叉 樹 void Btree (ThreadTnodevoid Btree (ThreadTnode * * t) t) ThreadTnode ThreadTnode * *p;p;

44、 if(t= =NULL)return; if(t= =NULL)return; p=t; p=t; while(p-Ltag=0) p = p-Lchild while(p-Ltag=0) p = p-Lchild; ; doprintf doprintf( “( “輸出輸出 p-data” );p-data” ); p=Succedent(p);while(p p=Succedent(p);while(p!=Null);!=Null); 遍歷線索二樹遍歷線索二樹第 章 樹 和 二 叉 樹 在在中序中序線索樹插入結(jié)點作為雙親結(jié)點的右孩子（右線索樹插入結(jié)點作為雙親結(jié)點的右孩子（右子樹）的子樹）

45、的算法。算法。 設(shè)插入結(jié)點為設(shè)插入結(jié)點為r，插入后作為，插入后作為p結(jié)點的右子樹的根結(jié)點的右子樹的根 分兩種情況：分兩種情況：1、原結(jié)點、原結(jié)點p沒有右子樹沒有右子樹第 章 樹 和 二 叉 樹 2、原結(jié)點、原結(jié)點p有右子樹有右子樹第 章 樹 和 二 叉 樹 ThreadTtreeThreadTtree tbtree(ThreadTtreeThreadTtree p) / p是二叉鏈表中的一個結(jié)點指針，插入一個結(jié)點是二叉鏈表中的一個結(jié)點指針，插入一個結(jié)點r作為結(jié)點作為結(jié)點p右子樹的根右子樹的根ThreadTtreeThreadTtree r,q; /q是結(jié)點是結(jié)點p的前驅(qū)結(jié)點的指針的前驅(qū)結(jié)點的指

46、針 r=(r=(ThreadTtreeThreadTtree)malloc(sizeof()malloc(sizeof(ThreadTnodeThreadTnode);); r-data =*; r-Rchild = p-Rchild ; r-Rtag= p-Rtag; r-Lchild =p; /r的左孩子指向前驅(qū)的左孩子指向前驅(qū) r-Ltag= 1; 第 章 樹 和 二 叉 樹 if(p- Rtag=0) /說明說明p有右孩子有右孩子 q= p-Rchild; /工作指針工作指針q指向指向p的右孩子的右孩子 while(q-Ltag=0) /找找q的最左下的結(jié)點的最左下的結(jié)點 q= q-L

47、child; q-Lchild = r ; /修改修改q的左線索為的左線索為r p-Rchild=r; p-Rtag=0; 舉檢索結(jié)點的例子舉檢索結(jié)點的例子第 章 樹 和 二 叉 樹 第 章 樹 和 二 叉 樹 #define Maxsize 50#define Maxsize 50typedeftypedef struct Nodestruct Node DataType DataType data; data;/ /* *數(shù)據(jù)域數(shù)據(jù)域* */ / int int parent; parent; / /* *雙親域雙親域* */ / Tnode;Tnode; Tnode Tnode ptre

48、eMaxsizeptreeMaxsize; 第 章 樹 和 二 叉 樹 abcdefhgiacdefghib112235551601234578dataparent如何找孩子結(jié)點如何找孩子結(jié)點ptreeptree數(shù)組數(shù)組第 章 樹 和 二 叉 樹 v 孩子結(jié)點 #define Maxsize#define Maxsize 50 50typedeftypedef struct ChildNodestruct ChildNode intint Child; Child;struct ChildNodestruct ChildNode * * next; next; ChildNodeChildNo

49、de; ;v表頭結(jié)點typedeftypedef structstruct DataType DataType data; data; ChildNode ChildNode * * ChildHead ChildHead ; ; DataNodeDataNode; ;v 孩子鏈表的表頭數(shù)據(jù)組 DataNodeDataNode CtreeMaxsizeCtreeMaxsize ; ; 第 章 樹 和 二 叉 樹 第 章 樹 和 二 叉 樹 FirstChildFirstChilddatadataNextsiblingNextsiblingtypedeftypedef struct CSNode

50、struct CSNode DataType DataType data; data; Struct CSNode Struct CSNode * *FirstChild, FirstChild, * *Nextsibling;Nextsibling; * * CSTree CSTree; ;第 章 樹 和 二 叉 樹 將此圖所示的樹向左下方旋轉(zhuǎn)將此圖所示的樹向左下方旋轉(zhuǎn)45度，就會得到一棵二叉樹度，就會得到一棵二叉樹第 章 樹 和 二 叉 樹 對應(yīng)對應(yīng)第 章 樹 和 二 叉 樹 轉(zhuǎn)換步驟：轉(zhuǎn)換步驟：step1: step1: 將樹中同一結(jié)點的兄弟相連將樹中同一結(jié)點的兄弟相連; ;加線加線抹線

51、抹線旋轉(zhuǎn)旋轉(zhuǎn)樹如何轉(zhuǎn)為二叉樹？樹如何轉(zhuǎn)為二叉樹？孩子孩子兄弟兄弟表示法表示法step2: step2: 保留結(jié)點的最左孩子連線，保留結(jié)點的最左孩子連線， 刪除其它孩子連線；刪除其它孩子連線；step3: step3: 將同一孩子的連線繞左孩子將同一孩子的連線繞左孩子旋轉(zhuǎn)旋轉(zhuǎn)4545度角。度角。第 章 樹 和 二 叉 樹 ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI樹轉(zhuǎn)換成的二叉樹其右子樹一定為空樹轉(zhuǎn)換成的二叉樹其右子樹一定為空v加線：在樹中所有相鄰的兄弟之間加一連線；加線：在樹中所有相鄰的兄弟之間加一連線；v抹線：對樹中每個結(jié)點，除了其左孩子外抹去

52、該結(jié)點與其余抹線：對樹中每個結(jié)點，除了其左孩子外抹去該結(jié)點與其余 孩子之間的連線。孩子之間的連線。v 整理：以樹的根結(jié)點為軸心，將整樹順時針轉(zhuǎn)整理：以樹的根結(jié)點為軸心，將整樹順時針轉(zhuǎn)4545。 第 章 樹 和 二 叉 樹 ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ第 章 樹 和 二 叉 樹 ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI第 章 樹 和 二 叉 樹 ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ第 章 樹 和 二 叉 樹 先根遍歷先根遍歷 若樹非空，則遍歷方法為：若

53、樹非空，則遍歷方法為： a.a.訪問根結(jié)點。訪問根結(jié)點。 b.b.從左到右，依次先根遍歷根結(jié)點的從左到右，依次先根遍歷根結(jié)點的每一棵子樹。每一棵子樹。第 章 樹 和 二 叉 樹 若樹非空，則遍歷方法為：若樹非空，則遍歷方法為：a.a.從左到右，依次后根遍歷根結(jié)點的每一從左到右，依次后根遍歷根結(jié)點的每一棵子樹?？米訕?。b.b.訪問根結(jié)點。訪問根結(jié)點。樹的后根遍歷樹的后根遍歷第 章 樹 和 二 叉 樹 若樹非空，則遍歷方法為：若樹非空，則遍歷方法為： 先訪問第一層上的結(jié)點，然后依次先訪問第一層上的結(jié)點，然后依次遍歷第二層，遍歷第二層，第第n n層的結(jié)層的結(jié)點。點。 樹的按層次遍歷樹的按層次遍歷第

54、章 樹 和 二 叉 樹 ABCDEFGHIJKLMNO先根遍歷：后根遍歷：層次遍歷：ABE F I GCDHJ KL NOME I F G B C J K N O L M H D AAB C DE F GH I J KL MNO第 章 樹 和 二 叉 樹 若森林非空，則遍歷方法為：若森林非空，則遍歷方法為： a. a. 訪問森林中第一棵樹的根結(jié)點。訪問森林中第一棵樹的根結(jié)點。 b.b.先根遍歷第一棵樹的根結(jié)點的子樹森林。先根遍歷第一棵樹的根結(jié)點的子樹森林。 c.c.先根遍歷除去第一棵樹之后剩余的樹構(gòu)成的先根遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。森林。第 章 樹 和 二 叉 樹 若森林非空，則

55、遍歷方法為：若森林非空，則遍歷方法為： a. 中根遍歷森林中第一棵樹的根結(jié)點的子樹中根遍歷森林中第一棵樹的根結(jié)點的子樹森林。森林。 b. 訪問第一棵樹的根結(jié)點。訪問第一棵樹的根結(jié)點。 c. 中根遍歷除去第一棵樹之后剩余的樹構(gòu)成中根遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。的森林。第 章 樹 和 二 叉 樹 若森林非空，則遍歷方法為：若森林非空，則遍歷方法為： a. 后根遍歷森林中第一棵樹的根結(jié)點的子樹森林。后根遍歷森林中第一棵樹的根結(jié)點的子樹森林。 b. 后根遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。后根遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。 c. 訪問第一棵樹的根結(jié)點。訪問第一棵樹的根結(jié)點。

56、第 章 樹 和 二 叉 樹 先根遍歷：A B C D E F G H I J中根遍歷：B C D A F E H J I G后根遍歷：D C B F J I H G E A第 章 樹 和 二 叉 樹 1234567后序遍歷如下森林后序遍歷如下森林所得序列為：所得序列為： DECBJIH7654321GA第 章 樹 和 二 叉 樹 從一個結(jié)點到另一個結(jié)點之間的分支序列。從一個結(jié)點到另一個結(jié)點之間的分支序列。從一個結(jié)點到另一個結(jié)點所經(jīng)過的分支數(shù)目。從一個結(jié)點到另一個結(jié)點所經(jīng)過的分支數(shù)目。在實際的應(yīng)用中，人們常常給樹的每個結(jié)點賦予在實際的應(yīng)用中，人們常常給樹的每個結(jié)點賦予一個具有某種一個具有某種，我

57、們稱該數(shù)值為這個結(jié)點的權(quán)。，我們稱該數(shù)值為這個結(jié)點的權(quán)。從樹根到某一結(jié)點的路徑長度與該結(jié)從樹根到某一結(jié)點的路徑長度與該結(jié)點的權(quán)的乘積，叫做該結(jié)點的帶權(quán)路徑長度。點的權(quán)的乘積，叫做該結(jié)點的帶權(quán)路徑長度。樹的帶權(quán)路徑長度是指樹中所有樹的帶權(quán)路徑長度是指樹中所有結(jié)點的帶權(quán)路徑長度結(jié)點的帶權(quán)路徑長度之之第 章 樹 和 二 叉 樹 是由是由n n個帶權(quán)葉子結(jié)點構(gòu)成的所有二叉樹中個帶權(quán)葉子結(jié)點構(gòu)成的所有二叉樹中帶權(quán)路徑帶權(quán)路徑長度長度WPLWPL最小的二叉樹最小的二叉樹。哈夫曼樹又叫。哈夫曼樹又叫最佳判定樹最佳判定樹。 結(jié)點到根的路徑長度權(quán)值其中：記作：kknkkklwlwwpl1第 章 樹 和 二 叉

58、樹 abcd7524WPL=7*2+5*2+2*2+4*2=36dcab2475WPL=7*3+5*3+2*1+4*2=46abcd7524WPL=7*1+5*2+2*3+4*3=35nkKKLWWPL1此為哈夫曼樹此為哈夫曼樹第 章 樹 和 二 叉 樹 構(gòu)造構(gòu)造Huffman樹的基本思想：樹的基本思想：設(shè)有設(shè)有4 4個字符個字符d,i,a,nd,i,a,n，出現(xiàn)的頻度分別為，出現(xiàn)的頻度分別為7,5,2,47,5,2,4， 怎樣編碼才能使它們組成的報文在網(wǎng)絡(luò)中傳得最快？怎樣編碼才能使它們組成的報文在網(wǎng)絡(luò)中傳得最快？法法1 1：等長編碼等長編碼（如二進(jìn)制編碼）（如二進(jìn)制編碼）令令d=d=0000

59、，i=i=0101，a=a=1010，n=n=1111，則：，則：WPL1WPL12bit2bit(7(75 52 24 4）3636法法2 2：不等長編碼不等長編碼（如（如HuffmanHuffman編碼）編碼）令令d=d=0 0;i=;i=10,10,a=a=110110,n=,n=111111，則：，則：明確：要實現(xiàn)明確：要實現(xiàn)HuffmanHuffman編碼，就要先構(gòu)造編碼，就要先構(gòu)造HuffmanHuffman樹樹討論：討論：HuffmanHuffman樹有什么用？樹有什么用？權(quán)值大的結(jié)點用短路徑，權(quán)值小的結(jié)點用長路徑。權(quán)值大的結(jié)點用短路徑，權(quán)值小的結(jié)點用長路徑。WPLWPL最小的樹

60、最小的樹頻度高的信息頻度高的信息用短碼，反之用短碼，反之用長碼，傳輸用長碼，傳輸效率肯定高！效率肯定高！WPL2=1bitWPL2=1bit7 72bit2bit5+5+3bit3bit(2+4)=(2+4)=3535最小冗余編碼、信息高效傳輸最小冗余編碼、信息高效傳輸?shù)?章 樹 和 二 叉 樹 根據(jù)給定的根據(jù)給定的n n個權(quán)值個權(quán)值 w w1 1,w,w2 2, ,w wn n ，構(gòu)造，構(gòu)造n n棵只有根結(jié)棵只有根結(jié)點的二叉樹點的二叉樹森林森林，令其權(quán)值為，令其權(quán)值為w wj j 在森林中選取兩棵根結(jié)點權(quán)值最小的樹作左右子樹，構(gòu)在森林中選取兩棵根結(jié)點權(quán)值最小的樹作左右子樹，構(gòu)造一棵新的二叉樹，置新二叉樹根結(jié)點權(quán)值為其左右子造一棵新的二叉樹，置新二叉樹根結(jié)點權(quán)值為