大學數(shù)據(jù)結構課件樹和二叉樹課件

1、大學數(shù)據(jù)結構課件樹和二叉樹前面講的線性表主要表現(xiàn)的是數(shù)據(jù)元素之間的前前面講的線性表主要表現(xiàn)的是數(shù)據(jù)元素之間的前后次序關系，是一種線性結構。后次序關系，是一種線性結構。樹型結構是以分支關系定義的層次結構。樹形結樹型結構是以分支關系定義的層次結構。樹形結構在客觀世界中廣泛存在，如人類的家庭族譜及各種構在客觀世界中廣泛存在，如人類的家庭族譜及各種社會組織機構。又如計算機文件管理和信息組織也用社會組織機構。又如計算機文件管理和信息組織也用到樹形結構。本章討論樹的基本概念，重點討論二叉到樹形結構。本章討論樹的基本概念，重點討論二叉樹的有關概念、性質、存儲結構和各種運算。樹的有關概念、性質、存儲結構和各種

2、運算。大學數(shù)據(jù)結構課件樹和二叉樹樹樹(tree)是由是由n(n0)個結點組成的有限集合個結點組成的有限集合T。n=0的的樹稱為空樹；對樹稱為空樹；對n0的樹，有的樹，有:(1)僅有僅有一個特殊的結點稱為根一個特殊的結點稱為根(root)結點結點，根結點沒，根結點沒有前驅結點；有前驅結點；(2)當當n1時，除根結點外其余的結點分為時，除根結點外其余的結點分為m(m0)個個互互不相交不相交的有限集合的有限集合T1,T2，Tm，其中每個集合，其中每個集合Ti本身又本身又是一棵樹，稱之為根的子樹（是一棵樹，稱之為根的子樹（ subtree）。）。注：注：樹的定義具有樹的定義具有遞歸性遞歸性，即，即“樹

3、中還有樹樹中還有樹”。 僅有一個根結點的樹是最小樹，僅有一個根結點的樹是最小樹，大學數(shù)據(jù)結構課件樹和二叉樹分支結點：分支結點：度不為度不為0 0的結點，除葉結點之外的其余結點。的結點，除葉結點之外的其余結點。ABCGEIDHFJMLK結點（結點（nodenode）：）：由數(shù)據(jù)元素由數(shù)據(jù)元素和構造數(shù)據(jù)元素之間關系的和構造數(shù)據(jù)元素之間關系的指針組成指針組成結點的度：結點的度：結點所擁有結點所擁有的子樹的個數(shù)的子樹的個數(shù)樹的度：樹的度：樹中所有結點的度的最大值樹中所有結點的度的最大值葉結點：葉結點：度為度為0 0的結點，也稱作的結點，也稱作終端結點終端結點結點的層次：結點的層次：從根結點到樹中某結點

4、所經(jīng)路徑上的分支數(shù)從根結點到樹中某結點所經(jīng)路徑上的分支數(shù)樹的深度：樹的深度：樹中所有結點的層次的最大值樹中所有結點的層次的最大值 森林：森林：m m（m m00）棵樹的集合）棵樹的集合 大學數(shù)據(jù)結構課件樹和二叉樹孩子孩子(child)(child)結點結點：樹中一個結點的子樹的根結點樹中一個結點的子樹的根結點雙親雙親(parent)(parent)結點：結點：若樹中某結點有孩子結點，則這個若樹中某結點有孩子結點，則這個結點就稱作它的孩子結點的雙親結點結點就稱作它的孩子結點的雙親結點 兄弟兄弟(sibling)(sibling)結點：結點：具有相同的雙親結點的結點具有相同的雙親結點的結點 ABC

5、GEIDHFJMLK大學數(shù)據(jù)結構課件樹和二叉樹無序樹：無序樹：樹中任意一個結點的各孩子結點之間的樹中任意一個結點的各孩子結點之間的次序構成次序構成 無關緊要無關緊要的樹的樹有序樹：有序樹：樹中任意一個結點的各孩子結點有嚴格排列次序的樹樹中任意一個結點的各孩子結點有嚴格排列次序的樹BEFLKBFELK大學數(shù)據(jù)結構課件樹和二叉樹(1)(1)倒懸樹法倒懸樹法( (直觀表示直觀表示) ) (2)(2)集合包含關系圖法集合包含關系圖法 (3)(3)凹入表示法凹入表示法 ABCGEIDHFJMLK FEKLCGBI IJ JMDHABCDEFGHIJKLM大學數(shù)據(jù)結構課件樹和二叉樹數(shù)據(jù)集合數(shù)據(jù)集合: 樹的

6、結點集合，每個結點由數(shù)據(jù)元素和構造數(shù)樹的結點集合，每個結點由數(shù)據(jù)元素和構造數(shù) 據(jù)元素之間關系的指針組成。據(jù)元素之間關系的指針組成。操作集合操作集合: （1 1）創(chuàng)建）創(chuàng)建MakeTree(T) MakeTree(T) （2 2）撤消）撤消DestroyTree(T)DestroyTree(T)（3 3）雙親結點）雙親結點Parent(T, curr) Parent(T, curr) （4 4）左孩子結點）左孩子結點LeftChild(T, curr) LeftChild(T, curr) （5 5）右兄弟結點）右兄弟結點RightSibling(T, curr) RightSibling(T,

7、 curr) （6 6）遍歷樹）遍歷樹Traverse(T, Visit()Traverse(T, Visit()大學數(shù)據(jù)結構課件樹和二叉樹 樹的結點之間的邏輯關系主要有雙親樹的結點之間的邏輯關系主要有雙親- -孩子孩子關系，兄弟關系。因此，從結點之間的邏輯關系關系，兄弟關系。因此，從結點之間的邏輯關系分，樹的存儲結構主要有：分，樹的存儲結構主要有：雙親表示法、孩子表雙親表示法、孩子表示法、雙親孩子表示法和孩子兄弟表示法示法、雙親孩子表示法和孩子兄弟表示法四種組四種組合。合。 指針有指針有常規(guī)指針常規(guī)指針和和仿真指針仿真指針大學數(shù)據(jù)結構課件樹和二叉樹4H2G1F1E1D0C0B-1AI4dat

8、a parentdata parent0 01 12 23 34 45 56 67 78 8(1)(1)雙親表示法雙親表示法(a)一棵樹一棵樹（b)仿真指針的雙親表示法存儲結構仿真指針的雙親表示法存儲結構樹及其使用仿真指針的雙親表示法樹及其使用仿真指針的雙親表示法ABCFGEIHD大學數(shù)據(jù)結構課件樹和二叉樹(2)(2)孩子表示法孩子表示法常規(guī)指針的孩子表示法常規(guī)指針的孩子表示法BCrootAD EF GIH ABCFGEIHD大學數(shù)據(jù)結構課件樹和二叉樹雙親孩子表示法雙親孩子表示法(3)(3)雙親孩子表示法雙親孩子表示法4H2G1F1E1D0C0B-1AI4data parent headdat

9、a parent head012345678child nextchild next87123456ABCFGEIHD大學數(shù)據(jù)結構課件樹和二叉樹(4)(4)孩子兄弟表示法孩子兄弟表示法常規(guī)指針的孩子兄弟表示法常規(guī)指針的孩子兄弟表示法rootBCDEFGHIAABCFGEIHD大學數(shù)據(jù)結構課件樹和二叉樹二叉樹二叉樹(binary tree)：是是n(n0)個結點的有限集合。個結點的有限集合。n=0的樹稱為空二叉樹；的樹稱為空二叉樹；n0的二叉樹由一個根結點以的二叉樹由一個根結點以及兩棵互不相交的、分別稱為及兩棵互不相交的、分別稱為左子樹和右子樹左子樹和右子樹的的二叉樹組成二叉樹組成 。其。其邏輯

10、結構：邏輯結構： 一對二（一對二（1:2）左、右子樹也是二叉樹，所以子樹也可以為空樹。下圖左、右子樹也是二叉樹，所以子樹也可以為空樹。下圖展現(xiàn)了五種不同形態(tài)的二叉樹。展現(xiàn)了五種不同形態(tài)的二叉樹。n=0n=0n=1n=1n1n1n1n1n1n1大學數(shù)據(jù)結構課件樹和二叉樹基本特征基本特征: 每個結點最多只有兩棵子樹（不存在度大于每個結點最多只有兩棵子樹（不存在度大于2的結點）；的結點）； 左子樹和右子樹左子樹和右子樹次序不能顛倒次序不能顛倒。所以下面是兩棵不同的樹。所以下面是兩棵不同的樹BACEDFGBACEDFG大學數(shù)據(jù)結構課件樹和二叉樹滿二叉樹：滿二叉樹：在一棵二叉樹中，如果所有分支結點都存在

11、左在一棵二叉樹中，如果所有分支結點都存在左子樹和右子樹，并且所有葉子結點都在同一層上，這樣子樹和右子樹，并且所有葉子結點都在同一層上，這樣的二叉樹稱為滿二叉樹。的二叉樹稱為滿二叉樹。BACEDFGHIJKLMNO大學數(shù)據(jù)結構課件樹和二叉樹完全二叉樹：完全二叉樹：如果一棵深度為如果一棵深度為k k，有，有n n個結點的二叉樹中各個結點的二叉樹中各 結點能夠與深度為結點能夠與深度為k k的順序編號的滿二叉樹從的順序編號的滿二叉樹從1 1到到n n標號的標號的 結點相對應的二叉樹稱為完全二叉樹。如下圖所示結點相對應的二叉樹稱為完全二叉樹。如下圖所示BACEDFGHIJBACEDFGHIJKLMNO(

12、a)滿二叉樹滿二叉樹 (b)完全二叉樹完全二叉樹 大學數(shù)據(jù)結構課件樹和二叉樹數(shù)據(jù)集合：數(shù)據(jù)集合：二叉樹的結點集合，每個結點由數(shù)據(jù)元素和構造數(shù)二叉樹的結點集合，每個結點由數(shù)據(jù)元素和構造數(shù)據(jù)元素之間關系的指針組成。據(jù)元素之間關系的指針組成。操作集合：操作集合：（1 1）創(chuàng)建）創(chuàng)建MakeTree(T) MakeTree(T) （2 2）撤消）撤消DestroyTree(T)DestroyTree(T)（3 3）左插入結點）左插入結點InsertLeftNode(curr, x) InsertLeftNode(curr, x) （4 4）右插入結點）右插入結點InsertRightNode(curr

13、, x) InsertRightNode(curr, x) （5 5）左刪除子樹）左刪除子樹DeleteLeftTree(curr) DeleteLeftTree(curr) （6 6）右刪除子樹）右刪除子樹DeleteRightTree(curr) DeleteRightTree(curr) （7 7）遍歷二叉樹）遍歷二叉樹Traverse(T, Visit()Traverse(T, Visit()大學數(shù)據(jù)結構課件樹和二叉樹k=ik=i2 2i -1-1性質性質1 1:i=1i=1 2 21-11-1=2=20 0=1=1i=2i=22 22-12-1=2=21 1=2=2i=3i=32 2

14、3-13-1=2=22 2=4=4BACEDFGHIJKLMNOi=4i=42 24-14-1=2=23 3=8=8k=ik=i大學數(shù)據(jù)結構課件樹和二叉樹性質性質2:2: k3 2 1k3 2 1 0 00 0 0 00 0 1 1 2 20 0 0 00 0 00 1 1 0 2 0 21 1 0 0 0 01 1 0 0 2 0 0 22 2 + + 0 0 1 10 0 0 20 0 0 2k-1k-1 0 11 1 1 2 0 11 1 1 2k k-1-1 =2=21 1=2=22 2=2=23 3=2=2k-1k-1=2=2k k=2=20 01 00 0 01 00 0 0+ +

15、 1 1k kBACEDFGHIJKLM NOk=ik=i2 2i -1-1qqaSnn1)1 (1n=kn=ka a1 1=1=1q=2q=2大學數(shù)據(jù)結構課件樹和二叉樹性質性質3 3 對于一棵非空的二叉樹，如果葉結點個數(shù)為對于一棵非空的二叉樹，如果葉結點個數(shù)為n n0 0，度為度為2 2的結點數(shù)為的結點數(shù)為n n2 2，則有，則有n n0 0= n= n2 2+1+1。BACEDFGHIJn0 = n2+1。證明：設證明：設n n為二叉樹的結點總數(shù)，為二叉樹的結點總數(shù)，n n1 1為二叉樹為二叉樹中度為中度為1 1的結點個數(shù)，則有：的結點個數(shù)，則有：n = nn = n0 0 + n + n

16、1 1 + n + n2 2 (1)(1)由于二叉樹中除根結點外，由于二叉樹中除根結點外，每個結點都有一條與其父每個結點都有一條與其父結點相連的邊。所以，有結點相連的邊。所以，有n n個結點的二叉樹總共有個結點的二叉樹總共有 n-1n-1條邊。于是有：條邊。于是有：n-1=0n-1=0n n0 0 + 1 + 1n n1 1 + 2 + 2n n2 2 (2)(2)再把再把(1)(1)代入代入(2)(2)，得：，得：n n0 0 + + n n1 1 + n + n2 2 -1= n -1= n1 1 + 2 + 2n n2 2則可以得到則可以得到: :大學數(shù)據(jù)結構課件樹和二叉樹+1 k-1-

17、1 = BACEDFGHIJ證明：根據(jù)性質證明：根據(jù)性質2 2，對于有對于有n n個結個結點的深度為點的深度為k k的完全二叉樹有的完全二叉樹有: : 因為該不等式各項均為整數(shù)，當對兩端各加因為該不等式各項均為整數(shù)，當對兩端各加1 1時不時不等式發(fā)生變化得：等式發(fā)生變化得：對不等式求對數(shù)，有對不等式求對數(shù)，有因為因為k必須是整數(shù)，所以對必須是整數(shù)，所以對log2(n) 取整，即取整，即顯顯然得到：然得到：即即: k= 大學數(shù)據(jù)結構課件樹和二叉樹對于一棵有對于一棵有n個結點的完全二叉樹，按照從上至下個結點的完全二叉樹，按照從上至下和從左至右的順序對所有結點從和從左至右的順序對所有結點從1開始順序

18、編號。開始順序編號。BACEDFGHIJ1 12 23 34 45 56 67 78 89 91010n=10n=10當當i=1i=1時，該結點為根結點，時，該結點為根結點，它無雙親結點；它無雙親結點；則對于序號為則對于序號為 i i 的結點的結點(1in),(1in),有：有：當當i1i1時，其雙親是結點時，其雙親是結點i/2 i/2 (“/”(“/”表示整除）；表示整除）；若若2in2in，則第，則第i i個結點有編號為個結點有編號為2i2i的左孩子；的左孩子；若若2i+1n2i+1n，則第，則第i i 個結點有編號為個結點有編號為2i+12i+1的右孩子的右孩子大學數(shù)據(jù)結構課件樹和二叉樹

19、 完全二叉樹的結點可按從上到下和從左至右的次完全二叉樹的結點可按從上到下和從左至右的次序存儲在一維數(shù)組中，其結點之間的關系可由公式計序存儲在一維數(shù)組中，其結點之間的關系可由公式計算得到，這就是二叉樹的順序存儲結構。下面兩棵樹算得到，這就是二叉樹的順序存儲結構。下面兩棵樹在數(shù)組中的存儲結構分別為：在數(shù)組中的存儲結構分別為：二叉樹的存儲結構有多種，最常用的有兩種：二叉樹的存儲結構有多種，最常用的有兩種：順序存儲結構和鏈表存儲結構順序存儲結構和鏈表存儲結構1. 1. 二叉樹的順序存儲結構二叉樹的順序存儲結構大學數(shù)據(jù)結構課件樹和二叉樹BACEDFGHIJKLMNO1204357611810912 13

20、 14 15DA BCONMLKJIHGFE1 12 23 34 45 56 67 78 89 9 1010n=15n=1511111212131314141515滿二叉樹：滿二叉樹：結點：結點：i=5i=5父結點：父結點：i/2=5/2=2i/2=5/2=2左孩子：左孩子：2i=22i=2* *5=105=10右孩子：右孩子：2i+1=22i+1=2* *5+1=115+1=11大學數(shù)據(jù)結構課件樹和二叉樹完全二叉樹：完全二叉樹：BACEDFGHIJ1 12 23 34 45 56 67 78 89 9 1010n=10n=10120435768910A BCDJIHGFE大學數(shù)據(jù)結構課件樹和

21、二叉樹對于一般的非完全二叉樹對于一般的非完全二叉樹BACEGDFA BCGFED1204357611810912數(shù)組數(shù)組下標下標13 必須首先在非完全二叉樹中增添一些并不存在的空結點使之必須首先在非完全二叉樹中增添一些并不存在的空結點使之變成完全二叉樹的形態(tài)。變成完全二叉樹的形態(tài)。 然后再用順序存儲結構存儲在一維數(shù)組中。然后再用順序存儲結構存儲在一維數(shù)組中。 顯然不能直接使用二叉樹的順序存儲結構。顯然不能直接使用二叉樹的順序存儲結構。所以，順序存儲結構僅適于滿二叉樹或完全二叉樹，一般二叉樹所以，順序存儲結構僅適于滿二叉樹或完全二叉樹，一般二叉樹更適宜用鏈表存儲結構更適宜用鏈表存儲結構大學數(shù)據(jù)結

22、構課件樹和二叉樹二叉樹的鏈式存儲結構是用指針建立二叉樹中結點之間的關系。二叉樹的鏈式存儲結構是用指針建立二叉樹中結點之間的關系。二叉二叉樹最常用的的鏈式表儲結構是二叉鏈和三叉鏈。樹最常用的的鏈式表儲結構是二叉鏈和三叉鏈。二叉鏈存儲結構的每二叉鏈存儲結構的每個結點包含三個域，分別是數(shù)據(jù)域個結點包含三個域，分別是數(shù)據(jù)域data、左孩子指針域、左孩子指針域leftChild和右和右孩子指針域孩子指針域rightChild。二叉鏈存儲結構中每個結點的圖示結構為：。二叉鏈存儲結構中每個結點的圖示結構為：rightChilddataleftChild 三叉鏈表的結點比前者多三叉鏈表的結點比前者多了一個指向

23、雙親的指針域。了一個指向雙親的指針域。2. 2. 二叉樹的鏈式存儲結構二叉樹的鏈式存儲結構結點結構描為：結點結構描為：typedef struct node ElemType data; struct node *lch,*rch; Bnode;typedef struct node ElemType data; struct node *lch,*par,*rch; /*par是雙親指針域是雙親指針域*/ Bnode3;parrchdatalch結點結構描為：結點結構描為：大學數(shù)據(jù)結構課件樹和二叉樹A BCD F J K ABCDFJK BACDJFK二叉鏈表二叉鏈表三叉鏈表三叉鏈表二叉樹二

24、叉樹大學數(shù)據(jù)結構課件樹和二叉樹二叉樹的仿真指針存儲二叉樹的仿真指針存儲結構結構是用數(shù)組存儲二叉樹中的結點，是用數(shù)組存儲二叉樹中的結點，數(shù)組中每個結點除數(shù)據(jù)元素域外，再增加仿真指針域用于仿數(shù)組中每個結點除數(shù)據(jù)元素域外，再增加仿真指針域用于仿真常規(guī)指針建立二叉樹中結點之間的關系。真常規(guī)指針建立二叉樹中結點之間的關系。二叉樹的仿真二叉鏈存儲結構二叉樹的仿真二叉鏈存儲結構BACDGEF二叉樹的仿真指針二叉樹的仿真指針大學數(shù)據(jù)結構課件樹和二叉樹6.2.5 二叉樹二叉鏈表的一個生成算法二叉樹二叉鏈表的一個生成算法 創(chuàng)建二叉樹的方法有多種，并且算法都比較復雜，這里我們創(chuàng)建二叉樹的方法有多種，并且算法都比較復

25、雜，這里我們運用二叉樹的性質運用二叉樹的性質5 5，學習一種較簡單的生成算法。，學習一種較簡單的生成算法。 對任意二叉樹，首先按滿二叉樹的結構對其結點進行編號。對任意二叉樹，首先按滿二叉樹的結構對其結點進行編號。1211131416151 12 23 34 45 56 67 78 89 9i123469x111213141516 此樹并非完全二叉樹，此樹并非完全二叉樹，因此結點編號不連續(xù)。算因此結點編號不連續(xù)。算法中用一個輔助向量法中用一個輔助向量s s存存放樹結點的指針。該向量放樹結點的指針。該向量的類型為：的類型為：Bnode *sMAXSIZE大學數(shù)據(jù)結構課件樹和二叉樹Bnode *cr

26、eat() Bnode *t=NULL; printf(“n i,x=”);scanf(“%d%d”,&i,&x); while(i!=0&x!=0) q=(Bnode *)malloc(sizeof(Bnode); q-data=x;q-lch=NULL;q-rch=NULL; si=q; /* Bnode *s20 */ if(i=1)t=q; /* t為樹根結點為樹根結點 */ else j=i/2; /* j為雙親結點編號為雙親結點編號 */ if(i%2)=0)sj-lch=q;else sj-rch=q; printf(“n i,x=”); scanf(“%d%d”,&i,&x);

27、 return t; /* creat end */typedef struct node ElemType data; struct node *lch,*rch; Bnode;012345678910 11 12 13 14 15 16 17 18 19* *s s1211131416151 12 23 34 46 69 9ti的父結點：的父結點：ti/2 左孩子：左孩子：t2i 右孩子：右孩子：t2i+1大學數(shù)據(jù)結構課件樹和二叉樹6.3 6.3 二叉樹遍歷二叉樹遍歷 遍歷二叉樹是指以一定的次序訪問二叉樹中的每個遍歷二叉樹是指以一定的次序訪問二叉樹中的每個結點，并且每個結點僅訪問一次。所謂

28、訪問結點是指對結點，并且每個結點僅訪問一次。所謂訪問結點是指對結點進行各種操作的簡稱。結點進行各種操作的簡稱。 遍歷二叉樹的過程實質上是把二叉樹的結點進行線遍歷二叉樹的過程實質上是把二叉樹的結點進行線性排列的過程。假如訪問結點的操作是輸出結點數(shù)據(jù)域性排列的過程。假如訪問結點的操作是輸出結點數(shù)據(jù)域的值，那么遍歷的結果就會得到一個線性序列。的值，那么遍歷的結果就會得到一個線性序列。 由于二叉樹有左、右子樹，因此遍歷的次序不同，由于二叉樹有左、右子樹，因此遍歷的次序不同，得到的結果也就不同。得到的結果也就不同。大學數(shù)據(jù)結構課件樹和二叉樹 從二叉樹的定義知，一棵二叉樹由三部分組成：根從二叉樹的定義知，

29、一棵二叉樹由三部分組成：根結點、左子樹和右子樹。結點、左子樹和右子樹。則有三種不同的遍歷次序：則有三種不同的遍歷次序： TLR-前序遍歷（先根遍歷）前序遍歷（先根遍歷） LTR-中序遍歷（中根遍歷）中序遍歷（中根遍歷） LRT-后序遍歷后序遍歷（后根遍歷）（后根遍歷）若規(guī)定：若規(guī)定： T-代表訪問根結點代表訪問根結點 L-代表遍歷根結點的左子樹代表遍歷根結點的左子樹 R-代表遍歷根結點的右子樹代表遍歷根結點的右子樹T TL LR RT TL LR大學數(shù)據(jù)結構課件樹和二叉樹ABCDDD遍歷搜索示意圖遍歷搜索示意圖圖中二叉樹有四個結點圖中二叉樹有四個結點ABCDABCD，為了便于理解遍歷的思想，為

30、每個沒有子樹的，為了便于理解遍歷的思想，為每個沒有子樹的結點補上相應的空子樹。結點補上相應的空子樹。設想有一條搜索路線設想有一條搜索路線.，它從根結點的左側開始，自上而下，自左至右搜索，它從根結點的左側開始，自上而下，自左至右搜索，最后從根結點的右側向上出去。恰好搜索線途經(jīng)每個有效樹結點都是三次最后從根結點的右側向上出去。恰好搜索線途經(jīng)每個有效樹結點都是三次搜索線第一次經(jīng)過就訪問的結點序列搜索線第一次經(jīng)過就訪問的結點序列ABCDABCD，稱先根遍歷；搜索線第二次經(jīng)過才，稱先根遍歷；搜索線第二次經(jīng)過才訪問的結點序列訪問的結點序列BADCBADC，稱中根遍歷；搜索線第三次經(jīng)過才訪問的序列，稱中根遍

31、歷；搜索線第三次經(jīng)過才訪問的序列BDCA,BDCA,稱稱后根遍歷后根遍歷A,B,C,D A,B,C,D 先根（前序）遍歷先根（前序）遍歷B,A,D,C B,A,D,C 中根（序）遍歷中根（序）遍歷B,D,C,A B,D,C,A 后根（序）遍歷后根（序）遍歷大學數(shù)據(jù)結構課件樹和二叉樹二叉樹選擇不同的存儲結構，遍歷算法的程序代碼會二叉樹選擇不同的存儲結構，遍歷算法的程序代碼會有所不同。這里確定用二叉鏈表作為存儲結構，樹中有所不同。這里確定用二叉鏈表作為存儲結構，樹中結點的結構定義為：結點的結構定義為：typedef struct node ElemType data; struct node *l

32、ch,*rch; Bnode;大學數(shù)據(jù)結構課件樹和二叉樹若根為空則結束；否則：若根為空則結束；否則：（1 1）訪問根結點；）訪問根結點；（2 2）按先根次序遍歷左子樹；）按先根次序遍歷左子樹；（3 3）按先根次序遍歷右子樹。）按先根次序遍歷右子樹。6.3.1 先根遍歷先根遍歷（先根遍歷（TLRTLR）遞歸算法為：）遞歸算法為：Void preorder(Bnode *p) if(p!=NULL) printf(“%6c”,p-data); preorder(p-lch); preorder(p-rch); /* preorder */此處假設此處假設ElemTypeElemType為為char

33、char型型大學數(shù)據(jù)結構課件樹和二叉樹ABCDA B C D p p訪問訪問A遍歷左子樹遍歷左子樹遍歷右子樹遍歷右子樹返回返回訪問訪問B遍歷左子樹遍歷左子樹遍歷右子樹遍歷右子樹返回返回訪問訪問C遍歷左子樹遍歷左子樹遍歷右子樹遍歷右子樹返回返回訪問訪問D遍歷左子樹遍歷左子樹遍歷右子樹遍歷右子樹返回返回根為根為NULLNULL返回返回根為根為NULLNULL返回返回根為根為NULLNULL返回返回根為根為NULLNULL返回返回根為根為NULLNULL返回返回大學數(shù)據(jù)結構課件樹和二叉樹若根為空則結束；否則：若根為空則結束；否則：（1 1）按中根次序遍歷左子樹；）按中根次序遍歷左子樹；（2 2）訪問

34、根結點；）訪問根結點；（3 3）按中根次序遍歷右子樹。）按中根次序遍歷右子樹。6.3.2 中根遍歷中根遍歷（中根遍歷（LTRLTR）與先根遍歷相似，只是在根不空時將算法的第一）與先根遍歷相似，只是在根不空時將算法的第一步與第二步次序對換而已，即：步與第二步次序對換而已，即：Void inorder(Bnode *p) if(p!=NULL) inorder(p-lch); printf(“%6c”,p-data); inorder(p-rch); /* inorder */此處假設此處假設ElemTypeElemType為為charchar型型實現(xiàn)算法的代碼也是在先根實現(xiàn)算法的代碼也是在先根算

35、法基礎上稍做改動，即：算法基礎上稍做改動，即：遞歸算法簡練但執(zhí)行效率較低，遞歸算法簡練但執(zhí)行效率較低，而且有些高級也不支持遞歸調而且有些高級也不支持遞歸調用，作為程序設計能力的訓練，用，作為程序設計能力的訓練，有必要學習非遞歸算法。有必要學習非遞歸算法。大學數(shù)據(jù)結構課件樹和二叉樹s s01234中根遍歷的非遞歸算法如下：中根遍歷的非遞歸算法如下：voide inorderz(Bnode *p) /* 棧棧s是是Bnode *s10 */ q=p; top =0; /*棧頂指針棧頂指針*/ bool =1; /* bool=1表示棧不空表示棧不空*/ printf(“n 中根遍歷：中根遍歷：n”

36、); do while(q!=NULL) top+; stop=q; q=q-lch; if(top=0) bool = 0; else q=stop; top-; printf(“%6c”,q-data); /*訪問根結點訪問根結點*/ q=q-rch; while(bool); printf(“n”); /* inorderz */ABCDA B C D p ptopC AB Dtoptop大學數(shù)據(jù)結構課件樹和二叉樹6.3.3 后根遍歷若根為空則結束；否則：若根為空則結束；否則：（1 1）按后根次序遍歷左子樹；）按后根次序遍歷左子樹；（2 2）按后根次序遍歷右子樹；）按后根次序遍歷右子樹；

37、（3 3）訪問根結點。）訪問根結點。Void postorder(Bnode *p) if(p!=NULL) postorder(p-lch); postorder(p-rch); printf(“%6c”,p-data); /* postorder */ 后根遍歷的非遞歸算法較為復雜，它需要兩個棧，第一個棧后根遍歷的非遞歸算法較為復雜，它需要兩個棧，第一個棧的用途與中根遍歷相同，第二個棧用來經(jīng)過某根結點的次數(shù)。兩的用途與中根遍歷相同，第二個棧用來經(jīng)過某根結點的次數(shù)。兩個棧的數(shù)據(jù)類型為：個棧的數(shù)據(jù)類型為：Bnode Bnode * *s10;int s220;s10;int s220; 具體算

38、法程序留給同學們課外閱讀。（具體算法程序留給同學們課外閱讀。（P111P111）大學數(shù)據(jù)結構課件樹和二叉樹void levelorder(Bnode *p) Bnode *q20; front =0; rear=0; if(p!=NULL)rear+;qrear=p; /*根結點不空，進隊根結點不空，進隊*/ while(front!=rear) front+; p=qfront; printf(“%6c”,p-data); /* 出隊并訪問出隊并訪問*/ if(p-lch!=NULL) rear+; qrear=p-lch; /*若左孩子不空，進隊若左孩子不空，進隊*/ if(p-rch!=

39、NULL) rear+; qrear=p-rch;/*若左孩子不空，進隊若左孩子不空，進隊*/ /* levelorder */6.3.4 按層遍歷二叉樹AB C D FJ K BACDJFKpFR109876543210qRRRRRRRFFFFFFFabcdfjkpppppp大學數(shù)據(jù)結構課件樹和二叉樹（1 1）初始化設置一個隊列；）初始化設置一個隊列；（2 2）把根結點指針入隊列；）把根結點指針入隊列；（3 3）當隊列非空時，循環(huán)執(zhí)行步驟）當隊列非空時，循環(huán)執(zhí)行步驟（3.a）到步驟到步驟（3.c）（3.a3.a）出隊列取得一個結點指針，訪問該結點；）出隊列取得一個結點指針，訪問該結點；（3.

40、b3.b）若該結點的左子樹非空，則將該結點的左子樹指）若該結點的左子樹非空，則將該結點的左子樹指針入隊列；針入隊列；（3.c3.c）若該結點的右子樹非空，則將該結點的右子樹指）若該結點的右子樹非空，則將該結點的右子樹指針入隊列；針入隊列；（4 4）結束。）結束。按層遍歷二叉樹的算法可以用語言描述如下：大學數(shù)據(jù)結構課件樹和二叉樹 按層遍歷二叉樹被稱為按層遍歷二叉樹被稱為層序遍歷層序遍歷。層序遍歷的要求是：。層序遍歷的要求是：按二叉樹的層序次序（即按二叉樹的層序次序（即從根結點層至葉結點層從根結點層至葉結點層），同一），同一層中按層中按先左子樹再右子樹先左子樹再右子樹的次序遍歷二叉樹。的次序遍歷二

41、叉樹?？梢越柚犃袑崿F(xiàn)二叉樹的層序遍歷可以借助隊列實現(xiàn)二叉樹的層序遍歷。 它的特點是，在所有未被訪問結點的集合中，排列它的特點是，在所有未被訪問結點的集合中，排列在已訪問結點集合中最前面結點的左孩子將最先被訪問，在已訪問結點集合中最前面結點的左孩子將最先被訪問，然后是該結點的右孩子。這樣，如果把已訪問的結點放然后是該結點的右孩子。這樣，如果把已訪問的結點放在一個隊列中，那么，所有未被訪問結點的訪問次序就在一個隊列中，那么，所有未被訪問結點的訪問次序就可以由存放在隊列中的已訪問結點的出隊列次序決定?？梢杂纱娣旁陉犃兄械囊言L問結點的出隊列次序決定。因此因此大學數(shù)據(jù)結構課件樹和二叉樹把二叉樹逆時針旋

42、轉把二叉樹逆時針旋轉900C，按照二叉樹的凹入表示法打印按照二叉樹的凹入表示法打印二叉樹?？砂汛撕瘮?shù)設計成遞二叉樹?？砂汛撕瘮?shù)設計成遞歸函數(shù)。由于把二叉樹逆時針歸函數(shù)。由于把二叉樹逆時針旋轉旋轉900C后，在屏幕上方的首后，在屏幕上方的首先是右子樹，然后是根結點，先是右子樹，然后是根結點，最后是左子樹，所以最后是左子樹，所以打印二叉打印二叉樹算法是一種特殊的中序遍歷樹算法是一種特殊的中序遍歷算法。算法。6.3.5 二叉樹遍歷的應用1 1 打印二叉樹打印二叉樹void PrintBiTree(Bnode *bt, int n) int i; if(bt = NULL) return; Print

43、BiTree(bt-rightChild, n+1); for(i = 0; i 0) printf(-); printf(%cn, bt-data); PrintBiTree(bt-leftChild, n+1);大學數(shù)據(jù)結構課件樹和二叉樹在二叉樹中查找數(shù)據(jù)元素操作在二叉樹中查找數(shù)據(jù)元素操作的要求是：在的要求是：在bt為根結點指針的二為根結點指針的二叉樹中查找數(shù)據(jù)元素叉樹中查找數(shù)據(jù)元素x，若查找到，若查找到數(shù)據(jù)元素數(shù)據(jù)元素x時返回該結點的指針；時返回該結點的指針；若查找不到數(shù)據(jù)元素若查找不到數(shù)據(jù)元素x時返回空指時返回空指針。針。在二叉樹在二叉樹bt中查找數(shù)據(jù)元素中查找數(shù)據(jù)元素x算法可設計成先

44、序遍歷算法，此時算法可設計成先序遍歷算法，此時查找結點的次序是：首先在根結點查找結點的次序是：首先在根結點查找，然后在左子樹查找，最后在查找，然后在左子樹查找，最后在右子樹查找。但是，和常規(guī)遞歸算右子樹查找。但是，和常規(guī)遞歸算法不同的是，此算法當一個分支上法不同的是，此算法當一個分支上的結點比較完仍未查找到數(shù)據(jù)元素的結點比較完仍未查找到數(shù)據(jù)元素x時，要返回到該結點的雙親結點時，要返回到該結點的雙親結點處繼續(xù)查找。因此，此算法是一個處繼續(xù)查找。因此，此算法是一個回溯算法回溯算法 。2 2 查找數(shù)據(jù)元素查找數(shù)據(jù)元素BiTreeNode *Search(Bnode *bt, ElemType x)

45、BiTreeNode *p; if(bt = NULL) return NULL; if(bt-data = x) return bt; if(bt-leftChild != NULL) p = Search(bt-leftChild, x); if(p != NULL) return p; if(bt-rightChild != NULL) p = Search(bt-rightChild, x); if(p != NULL) return p; return NULL;大學數(shù)據(jù)結構課件樹和二叉樹6.4 線索二叉樹 線索二叉樹是另一種分步遍歷二叉樹的方法。它線索二叉樹是另一種分步遍歷二叉樹的方法。它既可以從前向后既可以從前向后分步遍歷二叉樹，分步遍歷二叉樹，又可以從后向前又可以從后向前分步遍歷二叉樹。分步遍歷二叉樹。 當按某種規(guī)則遍歷二叉樹時，保存遍歷時得到的結點的后繼結點當按某種規(guī)則遍歷二叉樹時，保存遍歷時得到的結點的后繼結點信息和前驅結點信息的最常用的方法是建立線索二叉樹。信息和前驅結點信息的最常用的方法是建立線索二叉樹。 對二叉鏈表存儲結構的二叉樹分析可知，在有對二叉鏈表存儲結構的二叉樹分析可知，在