數(shù)據(jù)結構第6章樹和二叉樹

1、Chp6 樹和二叉樹6.1 樹的定義和基本概念6.2 二叉樹 6.2.1 樹的定義和基本術語 6.2.2 二叉樹的性質 6.2.3 二叉樹的存儲結構6.3 遍歷二叉樹 6.3.1 遍歷二叉樹 6.3.2 線索二叉樹 6.4 樹和森林 6.4.1 樹的存儲結構 6.4.2 森林與二叉樹的轉換6.4.3樹和森林的遍歷6.6 赫夫曼樹及其應用 6.6.1 最優(yōu)二叉樹（赫夫曼樹） 6.6.2 赫夫曼編碼 是一類重要的非線性結構。樹型結是一類重要的非線性結構。樹型結構是結點之間有分支，并且具有構是結點之間有分支，并且具有層次關系的結構層次關系的結構，它非常類似于自然界中的樹。樹結構在客觀世界它非常類似于

2、自然界中的樹。樹結構在客觀世界是大量存在的，例如家譜、行政組織機構都可用是大量存在的，例如家譜、行政組織機構都可用樹形象地表示。樹在計算機領域中也有著廣泛的樹形象地表示。樹在計算機領域中也有著廣泛的應用，例如在應用，例如在編譯程序編譯程序中，用樹來表示源程序的中，用樹來表示源程序的語法結構；在語法結構；在數(shù)據(jù)庫數(shù)據(jù)庫系統(tǒng)中，可用樹來組織信息；系統(tǒng)中，可用樹來組織信息；在分析在分析算法算法的行為時，可用樹來描述其執(zhí)行過程的行為時，可用樹來描述其執(zhí)行過程等等等等引引 言言6.1 樹的定義與基本概念樹的定義與基本概念1. 樹的定義樹的定義v定義：樹定義：樹(tree)是是n(n0)個結點的有限集個結

3、點的有限集T，其中：其中：l有且僅有一個特定的結點，稱為樹的有且僅有一個特定的結點，稱為樹的根根(root)l當當n1時，其余結點可分為時，其余結點可分為m(m0)個個互不相交互不相交的有限集的有限集T1,T2,Tm，其中每一個集合本身又是一棵樹，稱為根的其中每一個集合本身又是一棵樹，稱為根的子樹子樹(subtree)v特點：特點：l樹中至少有一個結點樹中至少有一個結點根根l樹中各子樹是互不相交的集合樹中各子樹是互不相交的集合A只有根結點的樹只有根結點的樹ABCDEFGHIJKLM有子樹的樹有子樹的樹根根子樹子樹從邏輯結構看：從邏輯結構看：1 1）樹中只有根結點沒有前趨；）樹中只有根結點沒有前

4、趨；2 2）除根外，其余結點都有且僅一個前趨；）除根外，其余結點都有且僅一個前趨；3 3）樹的結點，可以）樹的結點，可以有零個或多個有零個或多個后繼；后繼；4 4）除根外的其他結點，都存在唯一條從根到該結點的路徑；）除根外的其他結點，都存在唯一條從根到該結點的路徑；5 5）樹是一種分枝結構）樹是一種分枝結構，（除了一個稱為根的除了一個稱為根的結點外）每個元結點外）每個元素都素都有且僅有一個直接前趨，有且僅有一個直接前趨，有零個或多個直接后繼。有零個或多個直接后繼。J JI IA AC CB BD DH HG GF FE E2樹的應用樹的應用1）樹可表示具有分枝結構關系的對象）樹可表示具有分枝結

5、構關系的對象例例1 家族族譜家族族譜 設某家庭有設某家庭有13個成員個成員A、B、C、D、E、F、G、H、I、J、K、L、M他們之間的關系可用下圖所示的樹表示：他們之間的關系可用下圖所示的樹表示：J JI IA AC CB BD DH HG GF FE EK KL LM M2）樹是常用的數(shù)據(jù)組織形式）樹是常用的數(shù)據(jù)組織形式 有些應用中數(shù)據(jù)元素之間并不存在分支結構關系，但是為有些應用中數(shù)據(jù)元素之間并不存在分支結構關系，但是為了便于管理和使用數(shù)據(jù)，將它們用樹的形式來組織。了便于管理和使用數(shù)據(jù)，將它們用樹的形式來組織。例例2 計算機的文件系統(tǒng)計算機的文件系統(tǒng) 不論是不論是Linux文件系統(tǒng)還是文件系

6、統(tǒng)還是Windows文件系統(tǒng)，所有的文件文件系統(tǒng)，所有的文件是用樹的形式來組織的。是用樹的形式來組織的。文件夾文件夾1 1 文件夾文件夾n n 文件文件1 1 文件文件2 2文件夾文件夾11 11 文件夾文件夾12 12 文件文件11 11 文件文件1212/ /3樹的邏輯結構描述樹的邏輯結構描述 二元組描述為：二元組描述為：Tree =(D,R)D=Ki 1in;n0,Ki TElemtypeR=r 其中：其中：D是是n個具有個具有相同特性相同特性的數(shù)據(jù)元素的集合的數(shù)據(jù)元素的集合;n為樹中結為樹中結點個數(shù)，若點個數(shù)，若 n=0，則為一棵，則為一棵空樹空樹， n0時稱為一棵非空樹。時稱為一棵非

7、空樹。關系關系 r 應滿足下列條件：應滿足下列條件：（1）有且僅有一個結點沒有前驅有且僅有一個結點沒有前驅，稱該結點為樹根，稱該結點為樹根;（2）除根結點以外）除根結點以外,其余每個結點有且僅有一個直接前驅其余每個結點有且僅有一個直接前驅;（3）樹中每個結點可以）樹中每個結點可以有零個或多個直接后繼有零個或多個直接后繼(孩子結點孩子結點)。 基本術語v結點(node)表示樹中的元素，包括數(shù)據(jù)項及若干指向其子樹的分支v結點的度(degree)結點擁有的子樹數(shù)v葉子(leaf)度為0的結點v孩子(child)結點子樹的根稱為該結點的孩子v雙親(parents)孩子結點的上層結點叫該結點的v兄弟(s

8、ibling)同一雙親的孩子v堂兄結點同一層上結點v樹的度一棵樹中最大的結點度數(shù)v結點的層次(level)從根結點算起，根為第一層，它的孩子為第二層v深度(depth)樹中結點的最大層次數(shù)v森林(forest)m(m0)棵互不相交的樹的集合ABCDEFGHIJKLM結點結點A的度：的度：3結點結點B的度：的度：2結點結點M的度：的度：0葉子：葉子：K，L，F(xiàn)，G，M，I，J結點結點A的孩子：的孩子：B，C，D結點結點B的孩子：的孩子：E，F(xiàn)結點結點I的雙親：的雙親：D結點結點L的雙親：的雙親：E結點結點B，C，D為兄弟為兄弟結點結點K，L為兄弟為兄弟樹的度：樹的度：3結點結點A的層次：的層次：

9、1結點結點M的層次：的層次：4樹的深度：樹的深度：4結點結點F，G為堂兄弟為堂兄弟結點結點A是結點是結點F，G的祖先的祖先bacghdefijabdeijfcghijdfghabcea ( b ( d, e ( i, j ), c ( g, h ) ) )6.2 二叉樹二叉樹定義定義v定義：二叉樹是定義：二叉樹是n(nn(n 0)0)個結點的有限集，它或為空樹個結點的有限集，它或為空樹( (n=0)n=0)，或由一個根結點和兩棵分別稱為或由一個根結點和兩棵分別稱為左子樹左子樹和和右右子樹子樹的互不相交的二叉樹構成的互不相交的二叉樹構成v特點特點l每個結點至多有二棵子樹每個結點至多有二棵子樹(

10、(即不存在度大于即不存在度大于2 2的結點的結點) )l二叉樹的子樹有左、右之分，且其次序不能任意顛倒二叉樹的子樹有左、右之分，且其次序不能任意顛倒v基本形態(tài)基本形態(tài)A只有根結點只有根結點的二叉樹的二叉樹 空二叉樹空二叉樹AB右子樹為空右子樹為空AB左子樹為空左子樹為空ABC左、右子樹左、右子樹均非空均非空v性質性質1:1: 在二叉樹的第在二叉樹的第i層上至多有層上至多有2i-1個結點個結點(i1)。 證明：證明： 用數(shù)學歸納法。用數(shù)學歸納法。 1) 1) 當當i i=1=1時，整個二叉樹只有一根結點，此時時，整個二叉樹只有一根結點，此時2 2i-1i-1=2=20 0=1=1， 結論成立。結

11、論成立。 2) 2) 設設i=ki=k時結論成立，即第時結論成立，即第k k層上結點總數(shù)最多為層上結點總數(shù)最多為2 2k-1k-1個。個。 現(xiàn)證明當現(xiàn)證明當i=k+1i=k+1時，時， 結論成立：結論成立： 因為二叉樹中每個結點的度最大為因為二叉樹中每個結點的度最大為2 2，則第，則第k+1k+1層的結點層的結點 總數(shù)最多為第總數(shù)最多為第k k層上結點最大數(shù)的層上結點最大數(shù)的2 2倍，即倍，即2 22 2k-1k-1=2=2(k+1)-1(k+1)-1， 故結論成立。故結論成立。 推論：度為推論：度為m的樹中第的樹中第i層上至多有層上至多有mi-1個結點個結點, (i1)。二叉樹性質二叉樹性質

12、v性質性質2:2: 深度為深度為k的二叉樹至多有的二叉樹至多有2k-1個結點（個結點（k1）。）。 證明：因為深度為證明：因為深度為k k的二叉樹，其結點總數(shù)的最大值是將的二叉樹，其結點總數(shù)的最大值是將二叉樹每層上結點的最大值相加，所以深度為二叉樹每層上結點的最大值相加，所以深度為k k的二叉樹的結的二叉樹的結點總數(shù)至多為點總數(shù)至多為 kikikii111122層上的最大結點個數(shù)第推論：深度為推論：深度為k的的m叉樹至多有叉樹至多有 個結點個結點。11kmm101111.1kkikimmmmmmv 性質性質3:3: 對任意一棵二叉樹，若終端結點數(shù)為對任意一棵二叉樹，若終端結點數(shù)為n n0 0，

13、度為，度為2 2的結點數(shù)為的結點數(shù)為n n2 2，則，則n n0 0=n=n2 2+1+1。 證明：設二叉樹中結點總數(shù)為證明：設二叉樹中結點總數(shù)為n，n1為二叉樹中度為為二叉樹中度為1的結點總數(shù)，設二叉樹中分支數(shù)目為的結點總數(shù)，設二叉樹中分支數(shù)目為B 。 n=n0+n1+n2 除根結點外，每個結點均對應一個進入它的分支：除根結點外，每個結點均對應一個進入它的分支： n=B+1 二叉樹中的分支都是由度為二叉樹中的分支都是由度為1和度為和度為2的結點發(fā)出的結點發(fā)出 B=n1+2n2于是：由于是：由 可得可得：n0+n1+n2=n1+2n2+1n0=n2+1。幾種特殊形式的二叉樹幾種特殊形式的二叉樹

14、v滿二叉樹滿二叉樹l定義：一顆深度為定義：一顆深度為k k且有且有2 2k k-1-1個結點的二叉樹個結點的二叉樹l特點：每一層上的結點數(shù)都是特點：每一層上的結點數(shù)都是最大結點數(shù)最大結點數(shù)l滿二叉樹的順序表示，即從二叉樹的根開始，滿二叉樹的順序表示，即從二叉樹的根開始， 層層間從上到下，間從上到下， 層內從左到右，逐層進行編號（層內從左到右，逐層進行編號（1 1， 2 2， ， n n）。）。 A B C D E H I J K F G L M N O 1 2 3 4 5 6 7 8 9 10 15 11 12 13 14 滿二叉樹滿二叉樹 v完全二叉樹完全二叉樹l定義：深度為定義：深度為k，

15、有有n個結點的二叉樹當且僅當其每一個結點的二叉樹當且僅當其每一個結點都與深度為個結點都與深度為k的滿二叉樹中的滿二叉樹中編號編號從從1至至n的結點的結點一一對應一一對應時，稱為時，稱為l特點特點u葉子結點只可能在層次最大的兩層上出現(xiàn)葉子結點只可能在層次最大的兩層上出現(xiàn)u對任一結點，若其右子樹的最大層次為對任一結點，若其右子樹的最大層次為L，則其則其左左子樹子樹的最大層次必為的最大層次必為L 或或L+1（ 最下層的葉子最下層的葉子結點集中在樹的左部結點集中在樹的左部 ） A B C D E H I J K F G 1 2 3 4 5 6 7 8 9 10 11 完完 全全 二二 叉叉 樹樹 (b

16、)完全二叉樹完全二叉樹(c)非完全二叉樹非完全二叉樹( d)非完全二叉樹非完全二叉樹圖圖6.9 6.9 特殊形態(tài)的二叉樹特殊形態(tài)的二叉樹(a) 滿二叉樹滿二叉樹u性質性質4 4 具有具有 n (n (n n 0) 0) 個結點的完全二叉樹的深度個結點的完全二叉樹的深度為為 loglog2 2(n) (n) 1 1 證明：證明：設完全二叉樹的深度為設完全二叉樹的深度為 h，則根據(jù)性質，則根據(jù)性質2和完全二和完全二叉樹的定義有叉樹的定義有2h1 - 1 n 2h- 1或或 2h1 n 2h取對數(shù)取對數(shù) h1 1，則其雙親是則其雙親是 i/2 (2) 如果如果2in，則結點則結點i無左孩子；無左孩子

17、； 如果如果2i n，則其左孩子是則其左孩子是2i (3) 如果如果2i+1n，則結點則結點i無右孩子；無右孩子； 如果如果2i+1 n，則其右孩子是則其右孩子是2i+1621754389 10 11 12二叉樹的存儲結構二叉樹的存儲結構v順序存儲結構順序存儲結構l滿二叉樹或完全二叉樹滿二叉樹或完全二叉樹的順序存儲結構的順序存儲結構 對于完全二叉樹來說，除最下面一層外，各層都對于完全二叉樹來說，除最下面一層外，各層都被結點充滿。若對二叉樹被結點充滿。若對二叉樹按層排序按層排序，則從一個結點的，則從一個結點的編號就可推知其雙親、左右孩子等結點的編號。編號就可推知其雙親、左右孩子等結點的編號。 用

18、一維數(shù)組用一維數(shù)組btbt存放一棵完全二叉樹，將標號為存放一棵完全二叉樹，將標號為 i i 的結點的數(shù)據(jù)元素存放在分量的結點的數(shù)據(jù)元素存放在分量 btibti中，中，bt0bt0不存不存放元素放元素。 例例: bt5（i=5)的雙親結點標號是的雙親結點標號是k= i/2=2，雙親結點，雙親結點所對應的數(shù)組分量所對應的數(shù)組分量btk=bt2。 bt2（i=2)的右孩子結點標的右孩子結點標號是號是k= 2i+1=5，所對應的數(shù)組分量，所對應的數(shù)組分量btk=bt5。 ABCEFG1 12 23 34 45 56 6k0123456nbtkA AB BC CE EF FG G順序結構圖示順序結構圖示

19、: :二叉樹的存儲結構l非完全二叉樹非完全二叉樹的順序存儲結構的順序存儲結構 實現(xiàn)：實現(xiàn)：按完全二叉樹的形式按完全二叉樹的形式補齊二叉樹所缺少的那些結點補齊二叉樹所缺少的那些結點，對二叉樹結點再按層編號，將二叉樹原有的結點按編號存儲對二叉樹結點再按層編號，將二叉樹原有的結點按編號存儲到內存單元到內存單元“相應相應”的位置上。的位置上。 特點：特點：u結點間關系蘊含在其存儲位置中結點間關系蘊含在其存儲位置中u浪費空間，適于存滿二叉樹和完全二叉樹浪費空間，適于存滿二叉樹和完全二叉樹abcdefga b c d e 0 0 0 0 f g 1 2 3 4 5 6 7 8 9 10 116789123

20、451011補齊二叉樹所缺補齊二叉樹所缺少的那些結點少的那些結點ABCDEFG HIJKL 1 2 3 4 5 6 7 8 9 10 11 12完全二叉樹完全二叉樹abcdefghijkl結點編號結點編號1 2 3 4 5 6 7 8 9101112131415結點值結點值1 2 3 4 5 0 0 0 0 670000第第i i號結點的左右孩子一定保存在第號結點的左右孩子一定保存在第2i2i及及2i+12i+1號單元中。號單元中。缺點：對非完全二叉樹而言，浪費存儲空間缺點：對非完全二叉樹而言，浪費存儲空間#define MAX_TREE_SIZE 100typedef TElemType S

21、qBiTreeMAX_TREE_SIZE;SqBiTree bt;v鏈式存儲結構鏈式存儲結構l二叉鏈表二叉鏈表typedef struct node datatype data; struct node *lchild, *rchild;JD;lchild data rchild ABCDEFG在在n n個結點的二叉鏈表中，有個結點的二叉鏈表中，有n+1n+1個空指針域個空指針域 AB C D E F G空指針個數(shù)：空指針個數(shù)：2*n0+1*n1+0*n2=2n0+n1=n0+n1+n0=n0+n1+n2+1=n+1鏈表中每個結點由鏈表中每個結點由三個域三個域組成組成l三叉鏈表三叉鏈表type

22、def struct node datatype data; struct node *lchild, *rchild, *parent;JD;lchild data parent rchildABCDEFG A B C D E F G指向雙指向雙親親遍歷：按某種搜索路徑訪問二叉樹的每個結點，而且每個結點僅被訪問一遍歷：按某種搜索路徑訪問二叉樹的每個結點，而且每個結點僅被訪問一次。次。訪問：含義很廣，可以是對結點的各種處理，如修改結點數(shù)據(jù)、輸出結點訪問：含義很廣，可以是對結點的各種處理，如修改結點數(shù)據(jù)、輸出結點數(shù)據(jù)。數(shù)據(jù)。 遍歷是各種數(shù)據(jù)結構最基本的操作，許多其他的操作可以在遍歷基礎遍歷是各種

23、數(shù)據(jù)結構最基本的操作，許多其他的操作可以在遍歷基礎上實現(xiàn)。上實現(xiàn)。 對于線性結構由于每個結點只有一個直接后繼，遍歷是很容易的事對于線性結構由于每個結點只有一個直接后繼，遍歷是很容易的事 二叉樹是非線性結構，每個結點可能有兩個后繼，如何二叉樹是非線性結構，每個結點可能有兩個后繼，如何訪問二叉樹的每個結點，而且每個結點僅被訪問一次？訪問二叉樹的每個結點，而且每個結點僅被訪問一次？6.3 遍歷二叉樹v 二叉樹的遍歷方法二叉樹的遍歷方法 二叉樹由二叉樹由根根、左子樹左子樹、右子樹右子樹三部分組成三部分組成 二叉樹的遍歷可以分解為：訪問二叉樹的遍歷可以分解為：訪問根根，遍歷，遍歷左子樹左子樹和遍歷和遍歷

24、右子樹右子樹令：令：L：遍歷左子樹：遍歷左子樹 D：訪問根結點：訪問根結點 R：遍歷右子樹：遍歷右子樹 有六種遍歷方法：有六種遍歷方法： DLR，LDR，LRD， DRL，RDL，RLD 約定先左后右約定先左后右,有三種遍歷方法：有三種遍歷方法： DLR、LDR、LRD ，分別稱，分別稱為為 先序遍歷、中序遍歷、后序遍歷先序遍歷、中序遍歷、后序遍歷 A A F F G G E E D D C C B B二叉樹的遍歷二叉樹的遍歷v方法方法l先序遍歷先序遍歷：先訪問根結點：先訪問根結點,然后分別先序遍歷左子然后分別先序遍歷左子樹、右子樹樹、右子樹l中序遍歷中序遍歷：先中序遍歷左子樹，然后訪問根結點

25、，：先中序遍歷左子樹，然后訪問根結點，最后中序遍歷右子樹最后中序遍歷右子樹l后序遍歷后序遍歷：先后序遍歷左、右子樹，然后訪問根：先后序遍歷左、右子樹，然后訪問根結點結點l按層次遍歷：按層次遍歷：從上到下、從左到右訪問各結點從上到下、從左到右訪問各結點DLRLDR、LRD、DLRRDL、RLD、DRLADBCD L RAD L RD L RBDCD L R先序遍歷序列：先序遍歷序列：A B D C先序遍歷: 先訪問根結點先訪問根結點, ,然后分別先序遍歷左子樹、右子樹然后分別先序遍歷左子樹、右子樹ADBCL D RBL D RL D RADCL D R中序遍歷序列：中序遍歷序列：B D A C中

26、序遍歷： 先中序遍歷左子樹，然后訪問根結點，最后中序遍歷右子樹先中序遍歷左子樹，然后訪問根結點，最后中序遍歷右子樹ADBC L R DL R DL R DADCL R D后序遍歷序列：后序遍歷序列： D B C A后序遍歷: 先后序遍歷左、右子樹，然后訪問根結點先后序遍歷左、右子樹，然后訪問根結點B先序遍歷先序遍歷：中序遍歷：中序遍歷：后序遍歷：后序遍歷：- + a * b - c d / e f-+a*b-cd/ef-+a*b-c d/e f例：將如下表達式例：將如下表達式 a+b*(c-d)-e/ f存入一個樹結構。存入一個樹結構。葉子節(jié)點為操作數(shù)葉子節(jié)點為操作數(shù)中間節(jié)點為運算符中間節(jié)點為

27、運算符前綴表達式前綴表達式中綴表達式中綴表達式后綴表達式后綴表達式若二叉樹若二叉樹非空非空 （1 1）訪問根結點；）訪問根結點； （2 2）先序遍歷左子樹）先序遍歷左子樹 （3 3）先序遍歷右子樹；）先序遍歷右子樹；先序遍歷（先序遍歷（D L RD L R）的定義：）的定義：上面先序遍歷的定義等價于：上面先序遍歷的定義等價于： 若二叉樹為空，結束若二叉樹為空，結束 基本項基本項（也叫終止項）（也叫終止項） 若二叉樹非空若二叉樹非空 遞歸項遞歸項 （1 1）訪問根結點；）訪問根結點； （2 2）先序遍歷左子樹）先序遍歷左子樹 （3 3）先序遍歷右子樹；）先序遍歷右子樹；AFGEDCBv 遍歷的算

28、法遍歷的算法u先序遍歷的遞歸算法先序遍歷的遞歸算法void preorder(JD *bt) if(bt!=NULL) printf(%dt,bt-data); preorder(bt-lchild); preorder(bt-rchild); 主程序主程序Pre( T )返回返回返回返回pre(T R);返回返回返回返回pre(T R);ACBDTBprintf(B);pre(T L);BTAprintf(A);pre(T L);ATDprintf(D);pre(T L);DTCprintf(C);pre(T L);C返回返回T左是空返回左是空返回pre(T R);T左是空返回左是空返回T右

29、是空返回右是空返回T左是空返回左是空返回T右是空返回右是空返回pre(T R);先序序列：先序序列：A B D Cu先序遍歷的非遞歸算法先序遍歷的非遞歸算法遞歸算法邏輯清晰、易懂，但在實現(xiàn)時，由于函數(shù)調遞歸算法邏輯清晰、易懂，但在實現(xiàn)時，由于函數(shù)調用棧層層疊加，效率不高，故有時考慮非遞歸算法。用棧層層疊加，效率不高，故有時考慮非遞歸算法。遍歷時從根結點開始沿左子樹深入下去，當深入到最左遍歷時從根結點開始沿左子樹深入下去，當深入到最左端，無法再深入下去時，則返回，再逐一進入剛才深入時遇端，無法再深入下去時，則返回，再逐一進入剛才深入時遇到結點的右子樹，再進行如此的深入和返回，直到最后從根到結點的

30、右子樹，再進行如此的深入和返回，直到最后從根結點的右子樹返回到根結點為止。結點的右子樹返回到根結點為止。先序遍歷是在深入時遇到先序遍歷是在深入時遇到結點就訪問結點就訪問。 在下面算法中，二叉樹以二叉鏈表存放，用一維數(shù)組在下面算法中，二叉樹以二叉鏈表存放，用一維數(shù)組stackMaxsize 實現(xiàn)棧，變量實現(xiàn)棧，變量top用來表示當前棧頂?shù)奈恢谩Ｓ脕肀硎井斍皸ｍ數(shù)奈恢谩?（1 1）令當前指針）令當前指針p p指向根結點；指向根結點；（2 2）當）當p p非空非空, ,訪問當前結點訪問當前結點p p，將，將p p壓入棧中，令當前指針壓入棧中，令當前指針 指向其左孩子，重復（指向其左孩子，重復（2 2

31、），直到），直到p p為為NULLNULL；（3 3）當）當p p為空時，從棧中彈出棧頂元素賦給變量為空時，從棧中彈出棧頂元素賦給變量p p，令當前，令當前 指針指向其右孩子；指針指向其右孩子；（4 4）若棧非空或當前指針非）若棧非空或當前指針非NULLNULL，執(zhí)行（，執(zhí)行（2 2）；當）；當p p為空且為空且 棧也為空時，遍歷結束。棧也為空時，遍歷結束。 先序遍歷（先序遍歷（D L R）的非遞歸算法思想）的非遞歸算法思想 先序遍歷的非遞歸算法先序遍歷的非遞歸算法d db be ea a* *- -/ /c c+ +void NRPreOrder(BTree bt)BTree stackMa

32、xsize,p;int top;if (bt!=NULL)top=-1;p=bt;while(p!=NULL|top-1)while(p!=NULL)printf(%d,p-data); top+; stacktop=p; p=p-lchild;if (top-1) p=stacktop; top-; p=p-rchild; /* 指針指向指針指向p的左孩子的左孩子 */* 訪問結點的數(shù)據(jù)域訪問結點的數(shù)據(jù)域 */* 將當前指針將當前指針p壓棧壓棧 */*從棧中彈出棧頂元素，指針指向從棧中彈出棧頂元素，指針指向p的右孩子結點的右孩子結點*/* 初始化初始化 */v中序中序遍歷的遞歸算法遍歷的遞歸

33、算法 void InOrderTraverse(BiTree T) if (T!=NULL) InOrderTraverse(T-lchild); printf(%c ,T-data); /*訪問根結點訪問根結點*/ InOrderTraverse(T-rchild); u中序遍歷的非遞歸算法中序遍歷的非遞歸算法遍歷時從根結點開始沿左子樹深入下去，當深入到最左遍歷時從根結點開始沿左子樹深入下去，當深入到最左端，無法再深入下去時，則返回，再逐一進入剛才深入時遇端，無法再深入下去時，則返回，再逐一進入剛才深入時遇到結點的右子樹，再進行如此的深入和返回，直到最后從根到結點的右子樹，再進行如此的深入和

34、返回，直到最后從根結點的右子樹返回到根結點為止。先序遍歷是在深入時遇到結點的右子樹返回到根結點為止。先序遍歷是在深入時遇到結點就訪問，結點就訪問，中序遍歷是在從左子樹返回時遇到結點訪問中序遍歷是在從左子樹返回時遇到結點訪問。 中序遍歷的非遞歸算法思想中序遍歷的非遞歸算法思想從二叉樹的根結點開始，令變量從二叉樹的根結點開始，令變量p為根結點，為根結點，若若p不為空，則令不為空，則令p沿左子樹根結點前進，在前進沿左子樹根結點前進，在前進過程中，把所經歷的結點逐個壓入棧中，當過程中，把所經歷的結點逐個壓入棧中，當p為空為空時，彈出棧頂元素給時，彈出棧頂元素給p，并訪問該結點并訪問該結點，再令，再令p

35、為為它當前結點的右子樹根結點。重復上述過程，當它當前結點的右子樹根結點。重復上述過程，當p為空且棧也為空時，遍歷結束。為空且棧也為空時，遍歷結束。在算法具體實現(xiàn)時，只需將先序遍歷的非遞歸在算法具體實現(xiàn)時，只需將先序遍歷的非遞歸算法中的算法中的Visit(p-data)移到移到p=stacktop;top-;和和p=p-rchild之間即可。之間即可。 u后序遍歷遞歸算法后序遍歷遞歸算法 a a + + * * / / d / d / - -btbt e e b b c c a a* *(b-c)+d/e(b-c)+d/evoid Postorder (BTree bt)if (bt!=NULL

36、) Postorder (bt-lchild);Postorder (bt-rchild);printf(“%c,”, bt-data); 后序序列為后序序列為 a b c * d e / +稱為后綴表達式稱為后綴表達式u后序遍歷的非遞歸算法后序遍歷的非遞歸算法遍歷從根結點開始沿左子樹深入下去，當深入到最左端，遍歷從根結點開始沿左子樹深入下去，當深入到最左端，無法再深入下去時，則返回，再逐一進入剛才深入時遇到結點無法再深入下去時，則返回，再逐一進入剛才深入時遇到結點的右子樹，再進行如此的深入和返回，直到最后從根結點的右的右子樹，再進行如此的深入和返回，直到最后從根結點的右子樹返回到根結點為止。

37、先序遍歷是在深入時遇到結點就訪問子樹返回到根結點為止。先序遍歷是在深入時遇到結點就訪問，中序遍歷是在從左子樹返回時遇到結點訪問，中序遍歷是在從左子樹返回時遇到結點訪問，后序遍歷是在后序遍歷是在從右子樹返回時遇到結點訪問。從右子樹返回時遇到結點訪問。 后序遍歷的非遞歸算法思想：后序遍歷的非遞歸算法思想： 后序遍歷要求在遍歷完左右子樹后，再訪問根。后序遍歷要求在遍歷完左右子樹后，再訪問根。需要判斷根結點的左右子樹是否均遍歷過需要判斷根結點的左右子樹是否均遍歷過。 可采用標記法，結點入棧時，配一個標志可采用標記法，結點入棧時，配一個標志tagtag一同入棧一同入棧(1(1：遍歷左子樹前的現(xiàn)場保護，：

38、遍歷左子樹前的現(xiàn)場保護，2 2：遍歷：遍歷右子樹前的現(xiàn)場保護右子樹前的現(xiàn)場保護) )。 首先將首先將T T和和tag(tag(為為1)1)入棧，遍歷左子樹；返回入棧，遍歷左子樹；返回后，修改棧頂后，修改棧頂tagtag為為2 2，遍歷右子樹；最后訪問根，遍歷右子樹；最后訪問根結點。結點。typedef struct BTree data; int tag;stacknode;void NRPostOrder(BTree T) InitStack(S); while ( T!=NULL | !StackEmpty(S) ) while ( T != NULL ) Push(S,T,1); T =

39、 T-lchild; while ( ! EmptyStack (S) & GetTopTag(S)=2) Pop(S, x); Visit(x-data); if ( ! EmptyStack (S) ) SetTopTag(S, 2); / 設置棧頂標記設置棧頂標記 T = GetTopPointer(S); / 取棧頂保存的指針取棧頂保存的指針 T = T-rchild; else break; u層序遍歷算法層序遍歷算法遍歷方法：遍歷方法：從上而下，從左到右依從上而下，從左到右依次訪問樹中每個結點。次訪問樹中每個結點。層序遍歷二叉樹算法思想層序遍歷二叉樹算法思想: : 若二叉樹

40、不為空，則根結點入隊；若二叉樹不為空，則根結點入隊； 如隊列不空，循環(huán)：如隊列不空，循環(huán)：u做出隊操作，隊首元素作為當前做出隊操作，隊首元素作為當前結點，訪問當前結點；結點，訪問當前結點；u將當前結點的左右孩子入隊；將當前結點的左右孩子入隊； 最后，出隊序列就是層序遍歷序最后，出隊序列就是層序遍歷序列列AFGEDCB遍歷結果遍歷結果 ABCDEFG例例1 1：為二叉樹建立二叉鏈表：為二叉樹建立二叉鏈表( (遞歸算法遞歸算法) )以遞歸方式建立二叉樹以遞歸方式建立二叉樹 輸入：二叉樹的先序序列輸入：二叉樹的先序序列 結果：二叉樹的二叉鏈表結果：二叉樹的二叉鏈表遍歷操作訪問二叉樹的每個結點，而且每

41、個結點僅被訪問一遍歷操作訪問二叉樹的每個結點，而且每個結點僅被訪問一次。是否可在利用遍歷，建立二叉鏈表的所有結點并完成次。是否可在利用遍歷，建立二叉鏈表的所有結點并完成相應結點的鏈接？相應結點的鏈接？基本思想：輸入（基本思想：輸入（在空子樹處添加在空子樹處添加* *的二叉樹的）先序序列的二叉樹的）先序序列（設（設每個元素是一個字符）按先序遍歷的順序，建立二叉鏈表的所每個元素是一個字符）按先序遍歷的順序，建立二叉鏈表的所有結點并完成相應結點的鏈接有結點并完成相應結點的鏈接v遍歷算法應用遍歷算法應用應用應用1 1：按先序遍歷序列建立二叉樹的二叉鏈表按先序遍歷序列建立二叉樹的二叉鏈表 D D A A

42、 BB C C EE FFT T 先序序列：先序序列：A B D F C EA B D F C E（在空子樹處添加（在空子樹處添加* *的二叉樹的）先序序列：的二叉樹的）先序序列：A B D A B D * * F F * * * * * * C E C E * * * * * * A A F F E E D D C C B B* A A F F E E D D C C B B使得原二叉樹中每使得原二叉樹中每個結點，（包括葉個結點，（包括葉子結點）都有左右子結點）都有左右孩子孩子Status CreateBiTree(BiTree &T) /輸入（輸入（在空子樹處添加在空子樹處添加*

43、*的二叉樹的）先序序列（設每個元素是的二叉樹的）先序序列（設每個元素是一個字一個字/ 符）按先序遍歷的順序，建立二叉鏈表，并將該二叉鏈表根結點指針符）按先序遍歷的順序，建立二叉鏈表，并將該二叉鏈表根結點指針/賦給賦給T scanf (&ch); if (ch= = * ) T=NULL; / 若若ch= = * 則則T=NULL返回返回 else / 若若ch! = * if (! (T=(BiTNode * )malloc(sizeof(BiTNode) exit(OVERFLOW); T-date = ch; / 建立（根）結點建立（根）結點 CreateBiTree(T-lchi

44、ld); /構造左子樹鏈表，并將左子樹根結點指針構造左子樹鏈表，并將左子樹根結點指針 /賦賦 給（根）結點給（根）結點 的左孩子域的左孩子域 CreateBiTree(T-rchild); /構造右子樹鏈表，并將右子樹根結點指針構造右子樹鏈表，并將右子樹根結點指針 /賦給（根）結點賦給（根）結點 的右孩子域的右孩子域 return OK;/CreateBiTree如果輸入字符不是如果輸入字符不是“*”，則建立一個新結點，然后建立其左子樹和右子樹，則建立一個新結點，然后建立其左子樹和右子樹；如果是如果是“*”則返回，繼續(xù)進行下一次操作。則返回，繼續(xù)進行下一次操作。A B C D A BCD上頁算

45、法執(zhí)行過程舉例如下：ATBCD應用應用2 2：統(tǒng)計二叉樹中結點總數(shù)統(tǒng)計二叉樹中結點總數(shù)m m，葉子結點，葉子結點個數(shù)個數(shù)n0n0分析：每當訪問一個結點時，在原訪問語句分析：每當訪問一個結點時，在原訪問語句printfprintf后邊，加上后邊，加上一條計數(shù)器語句一條計數(shù)器語句m+m+和一個判斷該結點是否葉子的語句，便可解和一個判斷該結點是否葉子的語句，便可解決問題決問題假設用中根遍歷方法統(tǒng)計葉子結點個數(shù)，算法如下：假設用中根遍歷方法統(tǒng)計葉子結點個數(shù)，算法如下：算法算法1：Void injishu ( Bnode *t) if (t!=NULL) injishu (t-lch)； /*統(tǒng)計左子樹

46、結點數(shù)統(tǒng)計左子樹結點數(shù)*/ printf(%6c，t-data)； /*訪問根結點訪問根結點*/ m+; /*結點記數(shù)結點記數(shù)*/ if(t-lch=NULL)&(t-rch=NULL) n0+；/*葉結點記數(shù)葉結點記數(shù)*/ injishu (t-rch)； /*統(tǒng)計右子樹節(jié)點數(shù)統(tǒng)計右子樹節(jié)點數(shù)*/ /* injishu */ 算法算法2：void CountLeaf (BiTree T, int* count)/ 求葉子節(jié)點的個數(shù)，求葉子節(jié)點的個數(shù)，T為根節(jié)點的指針為根節(jié)點的指針 if (T) if (!T-lchild)& (!T-rchild) *count+; / 對葉

47、子結點計數(shù)對葉子結點計數(shù) CountLeaf( T-lchild, count); CountLeaf( T-rchild, count); / if / CountLeafint Height ( Bitree T ) /Height of a tree if ( T = NULL ) return 0; elseint m = Height ( T-lchild );int n = Height ( T-rchild ); return (m n) ? m+1 : n+1; 應用應用3 3：求二叉樹高度求二叉樹高度( (遞歸算法遞歸算法) )輸入輸入：二叉樹的二叉鏈表：二叉樹的二叉鏈表結果

48、結果：二叉樹的高度：二叉樹的高度分析如下：分析如下：（1 1）若二叉樹為空，則其高度為）若二叉樹為空，則其高度為0 0，求解結束，求解結束（2 2）若二叉樹不為空，則其高度為左右子樹高度最）若二叉樹不為空，則其高度為左右子樹高度最大值加大值加1 1 對于一個完全二叉樹來說，利用先序序列、中序序列對于一個完全二叉樹來說，利用先序序列、中序序列和后序序列可以確定此樹。然而，對于一個一般的二叉樹，和后序序列可以確定此樹。然而，對于一個一般的二叉樹，僅知二叉樹的先序序列僅知二叉樹的先序序列“abcdefg” 不能唯一確定一棵二叉不能唯一確定一棵二叉樹樹。 如果同時已知二叉樹的中序序列如果同時已知二叉樹

49、的中序序列“cbdaegf”，則會如何？，則會如何？ 應用應用4：由二叉樹的先序和中序序列建樹由二叉樹的先序和中序序列建樹 二叉樹的先序序列二叉樹的先序序列二叉樹的中序序列二叉樹的中序序列左子樹左子樹左子樹左子樹右子樹右子樹右子樹右子樹根根根根P154,例例6-5a b c d e f gc b d a e g f例如例如: :aab bccddeeffggabcdefg先序序列先序序列中序序列中序序列例例1. 已知樹的前序序列為已知樹的前序序列為 abdcegf 中序序列為中序序列為 bdaegcf 則樹為？則樹為？abdcfeg例例2. 已知樹的后序序列為已知樹的后序序列為 dbgefca

50、 中序序列為中序序列為 bdaegcf 則樹為？則樹為？我們可以利用我們可以利用前序序列和中序序列前序序列和中序序列、后序序列和中后序序列和中序序列序序列 來確定一棵二叉樹來確定一棵二叉樹。注意：若只是知道注意：若只是知道前序和后序前序和后序的序列就不能唯一的確定的序列就不能唯一的確定一個二叉樹。一個二叉樹。問題的提出遍歷是二叉樹最基本最常用的操作。遍歷是二叉樹最基本最常用的操作。1 1）對二叉樹所有結點做某種處理可在遍歷過程中實現(xiàn)；）對二叉樹所有結點做某種處理可在遍歷過程中實現(xiàn)；2 2）檢索（查找）二叉樹某個結點，可通過遍歷實現(xiàn)；）檢索（查找）二叉樹某個結點，可通過遍歷實現(xiàn)；遍歷的過程就是將

51、非線性序列轉化為一個線性序列，使得遍歷的過程就是將非線性序列轉化為一個線性序列，使得每個每個結點只有一個直接前驅和一個直接后繼結點只有一個直接前驅和一個直接后繼。 那么當我們采用二叉鏈表作為存儲結構時，只能那么當我們采用二叉鏈表作為存儲結構時，只能找到結點的左、右孩子，不能直接得到它的前驅和找到結點的左、右孩子，不能直接得到它的前驅和后繼，那么我們后繼，那么我們如何來保存在某種遍歷過程中得到如何來保存在某種遍歷過程中得到的前驅和后繼信息呢？的前驅和后繼信息呢？為了保留結點在某種遍歷序列中直接為了保留結點在某種遍歷序列中直接“前驅前驅”和直和直接接“后繼后繼”的位置信息，可以的位置信息，可以利用

52、利用二叉樹的二叉鏈二叉樹的二叉鏈表存儲結構中的那些表存儲結構中的那些空指針域空指針域來指示來指示二叉鏈表的2n個孩子指針域中只用到了n-1個域，還有另外n+1個指針域為空，被閑置現(xiàn)設法將這些空閑的指針域利用起來。當某結點無左孩子時，令左指針指向它的前趨結點；當該結點無右孩子時，令右指針指向它的后繼結點。為了嚴格區(qū)分結點的孩子指針域究竟指向孩子結點還是指向前趨或后繼結點，需在原結點結構中增加兩個標志域。解決辦法v定義：定義：l前驅與后繼：在二叉樹的先序、中序或后序遍歷序列中兩個相鄰前驅與后繼：在二叉樹的先序、中序或后序遍歷序列中兩個相鄰的結點互稱為的結點互稱為 l線索：指向前驅或后繼結點的指針稱

53、為線索：指向前驅或后繼結點的指針稱為 l線索二叉樹：加上線索的二叉樹叫線索二叉樹：加上線索的二叉樹叫 l線索化：對二叉樹按某種遍歷次序使其變?yōu)榫€索二叉樹的過程叫線索化：對二叉樹按某種遍歷次序使其變?yōu)榫€索二叉樹的過程叫 v實現(xiàn)實現(xiàn)l在有在有n個結點的二叉鏈表中必定有個結點的二叉鏈表中必定有n+1個個空鏈域空鏈域l在線索二叉樹的結點中增加兩個在線索二叉樹的結點中增加兩個標志域標志域ultag :若若 ltag =0, lc 域指向左孩子；若域指向左孩子；若 ltag=1, lc域指向其前域指向其前驅驅urtag :若若 rtag =0, rc 域指向右孩子；若域指向右孩子；若 rtag=1, rc

54、域指向其后域指向其后繼繼l結點定義：結點定義：typedef struct node int data; int ltag, rtag; struct node *lc, *rc;JD; lc ltag data rtag rc6.4 線索二叉樹ABCDE A B D C ET先序序列：先序序列：ABCDE00001111 11先序線索二叉樹先序線索二叉樹ABCDE A B D C ET中序序列：中序序列：BCAED0000111111 A B D C ET后序序列：后序序列：CBEDA0000111111ABCDE中序線索二叉樹中序線索二叉樹后序線索二叉樹后序線索二叉樹為簡化線索鏈表的遍歷算

55、法，仿照線性鏈表，為線索鏈表加上為簡化線索鏈表的遍歷算法，仿照線性鏈表，為線索鏈表加上一頭結點一頭結點約定：約定：頭結點頭結點的的lclc域：存放線索鏈表的根結點指針；域：存放線索鏈表的根結點指針；頭結點頭結點的的rcrc域域: : 中序序列最后一個結點的指針；中序序列最后一個結點的指針；中序序列中序序列第一結點第一結點lclc域：指向頭結點域：指向頭結點; ;中序序列中序序列最后一個結點最后一個結點的的rcrc域域: :指向頭結點指向頭結點; ;F F1 11 1E E0 01 1G G1 11 1D D1 11 1A A0 00 0B B0 00 0H H1 11 1C C0 00 00

56、01 1頭結點頭結點如圖標出的中序二叉樹結點的順序，可看出如圖標出的中序二叉樹結點的順序，可看出1 1）中序序列的第一結點，是二叉樹的最左下結點；）中序序列的第一結點，是二叉樹的最左下結點；2 2）若）若p p所指結點的右孩子域為線索，則所指結點的右孩子域為線索，則p p的右孩子結點即為后繼結的右孩子結點即為后繼結點；點；3 3）若）若p p所指結點的右孩子域為孩子指針，則所指結點的右孩子域為孩子指針，則p p的的后繼結點為其右子后繼結點為其右子樹的最左下結點；樹的最左下結點；F F1 11 1E E0 01 1G G1 11 1D D1 11 1A A0 00 0B B0 00 0H H1

57、11 1C C0 00 00 01 1頭結點頭結點中序遍歷序列：D,B,H,E,A,F,C,GABCDE 0 A 0 1 B 0 0 D 1 1 C 1 1 E 1 T中序序列：中序序列：BCAED帶頭結點的中序線索二叉樹帶頭結點的中序線索二叉樹 0 1頭結點：頭結點：ltag=0, lc指向根結點指向根結點rtag=1, rc指向指向中序中序序列中最后一個結點序列中最后一個結點中序中序遍歷序列中第一個結點的遍歷序列中第一個結點的lc域和最后域和最后一個結點的一個結點的rc域都指向頭結點域都指向頭結點 A B D C ET中序序列：中序序列：BCAED中序線索二叉樹中序線索二叉樹0000111

58、1113線索二叉樹的遍歷線索二叉樹的遍歷在二叉樹上加上結點前趨、后繼線索后，可利用線索對二叉在二叉樹上加上結點前趨、后繼線索后，可利用線索對二叉樹進行遍歷。樹進行遍歷。下面是下面是P134P134線索鏈表的遍歷算法線索鏈表的遍歷算法6.56.5。在中序線索二叉樹上遍歷二叉樹，其基本步驟：在中序線索二叉樹上遍歷二叉樹，其基本步驟：1 1） p=T-lchild; pp=T-lchild; p指向線索鏈表的根結點；指向線索鏈表的根結點；2 2）若線索鏈表非空，循環(huán)：）若線索鏈表非空，循環(huán)： （a a）循環(huán)，順著）循環(huán)，順著p p左孩子指針找到最左下結點；訪問之；左孩子指針找到最左下結點；訪問之；

59、（b b）若）若p p所指結點的右孩子域為線索，所指結點的右孩子域為線索， p p的右孩子結點即為的右孩子結點即為后繼結點循環(huán)：后繼結點循環(huán)： p=p-rchildp=p-rchild； 并訪問并訪問p p所指結點；（在此所指結點；（在此循環(huán)中，順著后繼線索訪問二叉樹中的結點）循環(huán)中，順著后繼線索訪問二叉樹中的結點） （c c） 一旦線索一旦線索“中斷中斷”，p p所指結點的右孩子域為右孩子所指結點的右孩子域為右孩子指針，指針，p=p-rchildp=p-rchild，使，使 p p指向右孩子結點；指向右孩子結點；3 3）返回）返回OKOK；結束；結束線索鏈表的遍歷算法線索鏈表的遍歷算法Voi

60、d InOrderTraverse_Thr(BiThrTree T, Status (* Visit) (TE1emType e) / T指向頭結點，頭結點的左鏈指向頭結點，頭結點的左鏈lchildlchild指向根結點，指向根結點， / 中序遍歷二叉線索樹中序遍歷二叉線索樹T T算法，對每個數(shù)據(jù)元素調用函數(shù)算法，對每個數(shù)據(jù)元素調用函數(shù)VisitVisit。 P=T-lchild; /p指向根結點指向根結點 While(p!=T) / 空樹或遍歷結束時，空樹或遍歷結束時，p= =Tp= =T While(p-Ltag= =0) p= p-lchild; /找到最左下結點；訪問之找到最左下結點；訪問之 if(!Visit(p-data)