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

1、1第五章 樹和二叉樹5.1 5.1 樹的有關概念樹的有關概念5.2 5.2 二叉樹二叉樹5.35.3 二叉樹的遍歷二叉樹的遍歷5.4 5.4 遍歷的應用遍歷的應用5.5 5.5 線索二叉樹線索二叉樹5.6 5.6 樹和森林樹和森林5.7 5.7 哈夫曼樹及應用哈夫曼樹及應用2第六章第六章 樹和二叉樹樹和二叉樹本章學習要點：本章學習要點： 熟練掌握熟練掌握二叉樹的結構特點，二叉樹的結構特點，了解了解相應的證明方法；相應的證明方法； 熟悉熟悉二叉樹的各種存儲結構的特點及使用范圍；二叉樹的各種存儲結構的特點及使用范圍； 熟練掌握熟練掌握各種序遍歷的遞歸和非遞歸算法，各種序遍歷的遞歸和非遞歸算法，了解

2、了解遍歷過程中遍歷過程中“棧?！?的狀態(tài)，并能的狀態(tài)，并能靈活運用靈活運用遍歷算法實現(xiàn)二叉樹的其它各種運算；遍歷算法實現(xiàn)二叉樹的其它各種運算； 了解了解線索化的實質是建立結點與其在相應序列中的前驅或后繼線索化的實質是建立結點與其在相應序列中的前驅或后繼之之 間的直接聯(lián)系，間的直接聯(lián)系，熟練掌握熟練掌握在中序線索化樹上找給定結點的前驅和在中序線索化樹上找給定結點的前驅和 后繼的方法；后繼的方法； 熟悉熟悉樹的各種存儲結構及其特點；樹的各種存儲結構及其特點； 學會編寫學會編寫實現(xiàn)樹的各種運算的算法；實現(xiàn)樹的各種運算的算法； 了解了解最優(yōu)樹的特性，最優(yōu)樹的特性，掌握掌握建立最優(yōu)樹和哈夫曼編碼的方法建

3、立最優(yōu)樹和哈夫曼編碼的方法36.1 樹的有關概念 5.15.1 樹的有關概念樹的有關概念1.1. 樹的概念樹的概念2. 2. 樹的應用樹的應用3.3. 樹的表示樹的表示樹的有關術語樹的有關術語5 樹的基本操作樹的基本操作45.1 樹的有關概念1樹的概念樹的概念 樹（樹（Tree）是）是n（n 0）個結點的有限集合，在任一棵非空樹）個結點的有限集合，在任一棵非空樹(n0)中：中：（1）有且僅有一個稱為根的結點。）有且僅有一個稱為根的結點。（2）其余結點可分為）其余結點可分為m（m 0）個互不相交的集合，而且這些集合）個互不相交的集合，而且這些集合中的每一集合都本身又是一棵樹，稱為根的子樹。中的每

4、一集合都本身又是一棵樹，稱為根的子樹。樹是遞歸結構，在樹的定義樹是遞歸結構，在樹的定義中又用到了樹的概念中又用到了樹的概念J JI IA AC CB BD DH HG GF FE EK KL LM M從邏輯結構看：從邏輯結構看：1）樹中只有根結點沒有前趨；）樹中只有根結點沒有前趨；2）除根外，其余結點都有且僅一個前趨；）除根外，其余結點都有且僅一個前趨；3）樹的結點，可以有零個或多個后繼；）樹的結點，可以有零個或多個后繼；4）除根外的其他結點，都存在唯一條從根到該結點）除根外的其他結點，都存在唯一條從根到該結點的路徑；的路徑；5）樹是一種分枝結構）樹是一種分枝結構 （除了一個稱為根的結點外（除

5、了一個稱為根的結點外）每個元素都有且僅有一個直接前趨，有且僅有零）每個元素都有且僅有一個直接前趨，有且僅有零個或多個直接后繼。個或多個直接后繼。55.1 樹的有關概念例：下面的圖是一棵樹例：下面的圖是一棵樹T=A, B, C, D, E, F, G, H, I, JT=A, B, C, D, E, F, G, H, I, J，K K，L L，MMA A是根，其余結點可以劃分為是根，其余結點可以劃分為3 3個個互不相交的集合：互不相交的集合： T T1 1=B, E, F=B, E, F，K K，L , TL , T2 2=C, G , T=C, G , T3 3=D, H, I, J=D, H

6、, I, J，MM這些集合中的每一集合都本身又是一棵樹，它們是這些集合中的每一集合都本身又是一棵樹，它們是A的子樹。的子樹。 例如例如 對于對于T T1 1，B B是根，其余結點可以劃分為是根，其余結點可以劃分為2 2個個互不相交的集合：互不相交的集合： T1111=E，K，L，T1212=F，T1111,T1212 是是B 的子樹。的子樹。J JI IA AC CB BD DH HG GF FE EK KL LM M65.1 5.1 樹的有關概念樹的有關概念2樹的應用樹的應用 1）樹可表示具有分枝結構關系的對象）樹可表示具有分枝結構關系的對象例例1家族族譜家族族譜 設某家庭有設某家庭有13個

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

8、文件系統(tǒng)還是window文件系統(tǒng)，所有的文件是用樹的形式來組織文件系統(tǒng)，所有的文件是用樹的形式來組織的。的。文件夾文件夾1 1 文件夾文件夾n n 文件文件1 1 文件文件2 2文件夾文件夾11 11 文件夾文件夾12 12 文件文件11 11 文件文件1212C C85.1 樹的有關概念3 樹的表示樹的表示 1）圖示表示）圖示表示 2）二元組表示）二元組表示 3）嵌套集合表示）嵌套集合表示 4）凹入表示法（類似書的目錄）凹入表示法（類似書的目錄） 5）廣義表表示）廣義表表示（A A（B B（E E（K,LK,L）,F,F）,C,C（G G）,D,D（H H（M M）,I,J,I,J）) )）

9、廣義表表示廣義表表示ABEKLFCGDHMJI凹凹入入表表示示法法AEDHJIKLMFGC嵌套集合表示嵌套集合表示B9 5.1 樹的有關概念樹的樹的 基本術語基本術語 樹的結點：包含一個數(shù)據(jù)元素及若干指樹的結點：包含一個數(shù)據(jù)元素及若干指向子樹的分支；向子樹的分支；孩子結點孩子結點(child)：結點的子樹的根稱為該結點：結點的子樹的根稱為該結點的孩子；的孩子；雙親結點雙親結點(parent)：B 結點是結點是A 結點的孩子，結點的孩子， 則則A結點是結點是B 結點的雙親；結點的雙親；兄弟結點兄弟結點(sibling)：同一雙親的孩子結點；：同一雙親的孩子結點；堂兄結點堂兄結點(cousin)：

10、其雙親在同一層上的結點；：其雙親在同一層上的結點；祖先結點祖先結點: 從根到該結點的所經(jīng)分支上的所有結點從根到該結點的所經(jīng)分支上的所有結點 子孫結點：以某結點為根的子樹中任一結點都稱為該結點的子孫子孫結點：以某結點為根的子樹中任一結點都稱為該結點的子孫J JI IA AC CB BD DH HG GF FE EK KL LM M10 5.1 樹的有關概念樹的樹的 基本術語基本術語結點層結點層：根結點的層定義為：根結點的層定義為1；根的孩子為第二層結點，依此類推；根的孩子為第二層結點，依此類推樹的深度樹的深度：樹中結點的最大層數(shù)，也稱為樹的高度：樹中結點的最大層數(shù)，也稱為樹的高度結點的度結點的度

11、：結點具有的子樹個數(shù)：結點具有的子樹個數(shù)樹的度樹的度： 樹中最大的結點度樹中最大的結點度葉子結點葉子結點：也叫終端結點，是度為：也叫終端結點，是度為 0 的結點的結點分枝結點分枝結點：也叫非終端結點，是度不為：也叫非終端結點，是度不為0的結點的結點有序樹有序樹：子樹有序的樹，如：家族樹；：子樹有序的樹，如：家族樹； 最左邊的子樹的根成為第一個孩子最左邊的子樹的根成為第一個孩子,最右邊的稱為最后一個孩子最右邊的稱為最后一個孩子無序樹無序樹：不考慮子樹的順序；：不考慮子樹的順序；森林森林；互不相交的樹的集合；森林和樹之間的聯(lián)系是：一棵樹去；互不相交的樹的集合；森林和樹之間的聯(lián)系是：一棵樹去 掉根，

12、其子樹構成一個森林；一個森林增加一個根結點成為樹。掉根，其子樹構成一個森林；一個森林增加一個根結點成為樹。J JI IA AC CB BD DH HG GF FE EK KL LM M115.1 樹的有關概念5 樹的基本操作樹的基本操作 樹的應用很廣，應用不同基本操作也不同。下面列舉了樹的一些基本操作：樹的應用很廣，應用不同基本操作也不同。下面列舉了樹的一些基本操作：1 1）initate (T)： T 樹的初始化，置樹的初始化，置T為空樹為空樹。包括建樹。包括建樹。2） root (T)： 求求T 樹的根。樹的根。3）parent (T , x ): 求求T 樹中樹中 x 結點的雙親結點。結

13、點的雙親結點。4）Child (T, x, i )： 求求 T 樹中樹中 x 結點的第結點的第 i 個孩子結點。個孩子結點。5）right_Sibling (T, x )： 求求T 樹中樹中 x 結點的右兄弟結點的右兄弟6）insert_Child (y, i, x )： 將根為將根為 x 的子樹置為的子樹置為 y 結點的第結點的第 i 個孩子個孩子7）del_child (x, i)： 刪除刪除 x 結點的第結點的第i 個孩子個孩子8）traverse (T)： 遍歷遍歷T樹。按某個次序依次訪問樹中每一個結點，并使每個結樹。按某個次序依次訪問樹中每一個結點，并使每個結 點都被訪問且只被訪問一

14、次。點都被訪問且只被訪問一次。9）clear (T)： 置置T為空樹為空樹 125. 2 二二 叉叉 樹樹 樹是一種分枝結構的對象，在樹的概念中，樹是一種分枝結構的對象，在樹的概念中，對每一個結點孩子的個數(shù)沒有限制，因此樹的對每一個結點孩子的個數(shù)沒有限制，因此樹的形態(tài)多種多樣，本章我們主要討論一種最簡單形態(tài)多種多樣，本章我們主要討論一種最簡單的樹的樹二叉樹。二叉樹。135.2 二 叉 樹 5.2 5.2 二叉樹二叉樹一一 二叉樹的概念二叉樹的概念二二 二叉樹的性質二叉樹的性質三三 二叉樹的存儲結構二叉樹的存儲結構145.2 二 叉 樹一一 二叉樹的概念二叉樹的概念1 1 二叉樹的定義二叉樹的定

15、義二叉樹：二叉樹： 或為空樹，或由根及兩顆不相交的左子樹、右子樹構成，并且或為空樹，或由根及兩顆不相交的左子樹、右子樹構成，并且左、右子樹本身也是二叉樹。左、右子樹本身也是二叉樹。說明說明1 1）二叉樹中每個結點最多有兩顆子樹；二叉樹每個結點度小于等于）二叉樹中每個結點最多有兩顆子樹；二叉樹每個結點度小于等于2;2;2 2）左、右子樹不能顛倒）左、右子樹不能顛倒有序樹有序樹; ;3 3）二叉樹是遞歸結構，在二叉樹的定義中又用到了二叉樹的概念）二叉樹是遞歸結構，在二叉樹的定義中又用到了二叉樹的概念; ; A A F F G G E E D D C C B B155.2 二 叉 樹 (a)(a)、

16、(b)(b)是不同的二叉樹，是不同的二叉樹， (a)(a)的左子樹有四個結點的左子樹有四個結點，(b)(b)的左子樹有兩個結點，的左子樹有兩個結點， A A F F G G E E D D C C B B(a)(a) A A G G E E D D B B C C F F(b)(b)165.2 二 叉 樹 2 二叉樹的基本形態(tài)二叉樹的基本形態(tài)(a)(a)空樹空樹 (b)(b)僅有根僅有根(c) (c) 右子樹空右子樹空(e) (e) 左子樹空左子樹空(d) (d) 左、右子樹均在左、右子樹均在3個結點的樹具有個結點的樹具有2種基本形態(tài)種基本形態(tài)3個結點的二叉樹具有個結點的二叉樹具有5中基本形態(tài)

17、中基本形態(tài)175.2 二 叉 樹3應用舉例 可以用二叉樹表示表達式 a+b*(c-d)-e/f e e d d c c b b f f a a + + * * / / - - - -185.2 二 叉 樹二二 二叉樹性質二叉樹性質n性質性質1 1 二叉樹第二叉樹第i i層上至多層上至多2 2i-1i-1個結點（個結點（i=1)i=1) 證明：證明：( (采用數(shù)學歸納法采用數(shù)學歸納法) ) 當當i=1i=1時，只有時，只有1 1個根結點。顯然個根結點。顯然 2 21-11-1 =1 =1，命題成立。，命題成立。 假設對所有的假設對所有的j(1jj(1ji)i)命題成立，即第命題成立，即第j j層

18、上至多層上至多2 2j-1j-1個結點個結點; ; 現(xiàn)證明現(xiàn)證明j=ij=i時命題仍然成立。時命題仍然成立。 由歸納假設知，二叉樹的由歸納假設知，二叉樹的i-1i-1層至多有層至多有2 2i-2i-2個結點個結點又由二叉樹的定義知，二叉樹每個結點的度至多為又由二叉樹的定義知，二叉樹每個結點的度至多為2 2 第第i i層上的最大結點數(shù)目層上的最大結點數(shù)目=2=2* *第第i-1i-1層上的最大結點數(shù)目層上的最大結點數(shù)目=2=2* *2 2i-2i-2 = 2 = 2i-1i-1 故故j=ij=i時命題成立時命題成立 從而該命題成立。從而該命題成立。195.2 二 叉 樹n 性質性質2 2 深度為

19、深度為k k的二叉樹至多的二叉樹至多2 2k k-1-1個結點（個結點（k=1)k=1)證明：深度為證明：深度為k k的二叉樹的結點的最大數(shù)目的二叉樹的結點的最大數(shù)目 每層結點的最大數(shù)目之和每層結點的最大數(shù)目之和2 20 0+2+21 1+2 2k-1k-12 2k k-1-1206.2 二叉樹n 性質性質3 對任何一棵二叉樹對任何一棵二叉樹T，若其終端結點數(shù)目為，若其終端結點數(shù)目為n0,度為度為2的結點數(shù)目為的結點數(shù)目為n2，則，則n0=n2+1。證明：證明：設二叉樹設二叉樹T的總結點數(shù)目為的總結點數(shù)目為n,度為度為1的結點數(shù)目為的結點數(shù)目為n1， 則則 n=n0+ n1+ n2 (1) 又

20、由于二叉樹又由于二叉樹T中，除根結點以外，每個結點剛好有一個分支指向，中，除根結點以外，每個結點剛好有一個分支指向， 設設B為分支總數(shù)，則為分支總數(shù)，則 n=B+1 (2) 而二叉樹的這些分支是由度為而二叉樹的這些分支是由度為1和度為和度為2的結點產(chǎn)生，的結點產(chǎn)生， 則則 B=n1+ 2 n2 (3) 綜上三式，可知綜上三式，可知n0=n2+1成立。成立。思考思考 如果一棵樹有如果一棵樹有n1個度數(shù)為個度數(shù)為1的結點，的結點，n2個度數(shù)為個度數(shù)為2的結點，的結點， ，nm個度數(shù)為個度數(shù)為m的結點，則終端結點數(shù)的結點，則終端結點數(shù)n0= ？215.2 二 叉 樹兩種特殊的二叉樹兩種特殊的二叉樹滿

21、二叉樹滿二叉樹：如果深度為：如果深度為k k的二叉樹，有的二叉樹，有2 2k k-1-1個結點則稱為滿二叉樹；個結點則稱為滿二叉樹； A A G G F F E E D D C C B B A A C C B BK=3K=3的滿二叉樹的滿二叉樹K=2K=2的滿二叉樹的滿二叉樹225.2 二 叉 樹完全二叉樹完全二叉樹：如果一顆二叉樹只有最下一層結點數(shù)可能未達到最大，并如果一顆二叉樹只有最下一層結點數(shù)可能未達到最大，并且最下層結點都集中在該層的最左端，則稱為完全二叉樹；且最下層結點都集中在該層的最左端，則稱為完全二叉樹； G G A A E E D D C C B B(c)(c) A A E E

22、 D D C C B B(b)(b)、(b)(b)完全二叉樹(c) (c) 不是完全二叉樹 A A(a)(a) G G F F E E D D C C B B235.2 二 叉 樹下面是兩個關于完全二叉樹的性質下面是兩個關于完全二叉樹的性質 性質性質4 4 具有具有n n個結點的完全二叉樹的深度為：個結點的完全二叉樹的深度為：trunc(logtrunc(log2 2 n)+1n)+1， trunc(x)trunc(x)為取整函數(shù)。為取整函數(shù)。證明：假設完全二叉樹的深度為證明：假設完全二叉樹的深度為k,k,則由性質則由性質2 2和完和完全二叉樹的定義知：全二叉樹的定義知：2 2k-1 k-1

23、-1-1 n 2n 2k k -1-1 ，即，即2 2k-1k-1nn 2 2k k對上式取對數(shù)有：對上式取對數(shù)有：k-1logk-1log2 2n nk k由于由于k k是整數(shù)，故是整數(shù)，故k= trunck= trunc（2 2n n）+1+1245.2 二叉樹對完全二叉樹的結點編號：對完全二叉樹的結點編號：從上到下，每一層從左到右從上到下，每一層從左到右 性質性質5 5：在一棵有在一棵有n n個結點的完全二叉樹中個結點的完全二叉樹中, ,對于編號為對于編號為i(i(1 1in)的結點的結點: :1 1）當）當i=1i=1，結點，結點i i為根結點為根結點1 1）若有左孩子）若有左孩子(

24、(2i2in n) )，則左孩編號為，則左孩編號為2i2i2 2）若有右孩子）若有右孩子( (2i+12i+1n) )，則右孩子結點編號為，則右孩子結點編號為2i+12i+13 3）若有雙親，則雙親結點編號為）若有雙親，則雙親結點編號為trunc(i/2)trunc(i/2) A A F F E E D D C C B B1 12 23 34 45 56 6255.2二叉樹 1 1 二叉樹的順序結構二叉樹的順序結構 /-二叉樹的順序存儲表示二叉樹的順序存儲表示- int MAX_TREE_SIZE 100Object treeMAX_TREE_SIZE存儲方案存儲方案： 用順序存儲結構存儲一棵

25、二叉樹時，必須首先對該樹中每個用順序存儲結構存儲一棵二叉樹時，必須首先對該樹中每個結點進行結點進行編號編號，樹中各結點的編號應與等深度的滿二叉樹中對應，樹中各結點的編號應與等深度的滿二叉樹中對應位置上結點的編號相同。位置上結點的編號相同。用一組連續(xù)的內存單元，按結點的用一組連續(xù)的內存單元，按結點的編號編號順序依次存儲二叉樹的元素值。順序依次存儲二叉樹的元素值。 三二叉樹存貯結構三二叉樹存貯結構265.2 二 叉 樹例：例： 用一維數(shù)組用一維數(shù)組bt bt 存放一棵完全二叉樹，將標號為存放一棵完全二叉樹，將標號為 i i 的結點的的結點的數(shù)據(jù)元素存放在分量數(shù)據(jù)元素存放在分量 bti-1bti-1

26、中。存儲位置隱含了樹中的關系，樹中的中。存儲位置隱含了樹中的關系，樹中的關系是通過完全二叉樹的性質實現(xiàn)的。例如，關系是通過完全二叉樹的性質實現(xiàn)的。例如，bt5bt5（i=6)i=6)的雙親結點的雙親結點標號是標號是k=trunc(i/2)=3,k=trunc(i/2)=3,雙親結點所對應的數(shù)組分量雙親結點所對應的數(shù)組分量btk-1=bt2btk-1=bt2順序結構圖示順序結構圖示 A A F F E E D D C C B B1 12 23 34 45 56 6下標下標 0 1 2 3 4 5 6 7 m-10 1 2 3 4 5 6 7 m-1 A B C D E FA B C D E F編

27、號編號 1 2 3 4 5 6275.2 二 叉 樹非完全二叉樹的順序結構非完全二叉樹的順序結構 按完全二叉樹的形式補齊二叉樹所缺少的那些結點，對二叉樹結點編號按完全二叉樹的形式補齊二叉樹所缺少的那些結點，對二叉樹結點編號, ,將二叉樹原有的結點按編號存儲到內存單元將二叉樹原有的結點按編號存儲到內存單元“相應相應”的位置上。但這種方式的位置上。但這種方式對于畸形二叉樹，浪費較大空間。對于畸形二叉樹，浪費較大空間。 A A F F G G E E D D C C B B8 81 16 67 72 24 45 53 31010 A A F F G G E E D D C C B B9 90 1 2

28、 3 4 5 6 7 8 9 10 m-10 1 2 3 4 5 6 7 8 9 10 m-1A B C D E 0 F 0 0 GA B C D E 0 F 0 0 G28討論：討論： 對于對于完全二叉樹完全二叉樹來說，二叉樹中的結點的編號完全可以反映來說，二叉樹中的結點的編號完全可以反映出該二叉樹中結點之間的邏輯關系，可將此類二叉樹中結點的編出該二叉樹中結點之間的邏輯關系，可將此類二叉樹中結點的編號與數(shù)組下標建立一一對應關系，所以采用順序存儲結構較好。號與數(shù)組下標建立一一對應關系，所以采用順序存儲結構較好。 對于對于一般的二叉樹一般的二叉樹，則添加一些不存在的，則添加一些不存在的“空空”結

29、點，使之結點，使之成為一棵完全二叉樹。將其每個結點與完全二叉樹上的結點完全成為一棵完全二叉樹。將其每個結點與完全二叉樹上的結點完全對應，此時仍可用順序存儲結構表示這棵二叉樹?？赡茉斐煽臻g對應，此時仍可用順序存儲結構表示這棵二叉樹?？赡茉斐煽臻g浪費，最壞的情況是：深度為浪費，最壞的情況是：深度為k且只有且只有k個結點的單支樹，需要長個結點的單支樹，需要長為為2 2k k-1-1的數(shù)組空間。的數(shù)組空間。295.2 二 叉 樹2 2 二叉鏈表二叉鏈表 二叉鏈表中每個結點包含三個域：數(shù)據(jù)域、左指針域、右指針域二叉鏈表中每個結點包含三個域：數(shù)據(jù)域、左指針域、右指針域 A A F F E E D D C

30、C B Bclass Bnodeptint data; Bnodept lchild, rchlid;二叉鏈表圖示 D D A A B B C C E E F F rchilddatalchild二叉鏈表結點二叉鏈表結點306.2 二 叉 樹 A A F F E E D D C C B B3 3 三叉鏈表（便于找到結點的雙親）三叉鏈表（便于找到結點的雙親） 三叉鏈表中每個結點包含四個域：數(shù)據(jù)域、雙親指針域、左指針域、三叉鏈表中每個結點包含四個域：數(shù)據(jù)域、雙親指針域、左指針域、右指針域右指針域class Bnodept int data; Bnodept lchild, rchild, pare

31、nt;ABDFECparentrchilddatalchild三叉鏈表結點31 5.3 5.3 二叉樹的遍歷二叉樹的遍歷 一一. . 二叉樹的遍歷方法二叉樹的遍歷方法 二二. . 遍歷的遞歸算法遍歷的遞歸算法 三三. . 遍歷的非遞歸算法遍歷的非遞歸算法325.3 二叉樹的遍歷遍歷：遍歷：按某種搜索路徑訪問二叉樹的每個結點，而且每個結點僅被訪按某種搜索路徑訪問二叉樹的每個結點，而且每個結點僅被訪問一次。問一次。訪問訪問：含義很廣，可以是對結點的各種處理：含義很廣，可以是對結點的各種處理，如修改結點數(shù)據(jù)、輸出，如修改結點數(shù)據(jù)、輸出結點數(shù)據(jù)。結點數(shù)據(jù)。 遍歷是各種數(shù)據(jù)結構最基本的操作，許多其他的操

32、作可以在遍歷遍歷是各種數(shù)據(jù)結構最基本的操作，許多其他的操作可以在遍歷基礎上實現(xiàn)?；A上實現(xiàn)。 如何訪問二叉樹的每個結點，如何訪問二叉樹的每個結點， 而且每個結點僅被訪問一次？而且每個結點僅被訪問一次？335.3 二叉樹的遍歷二叉樹的遍歷方法二叉樹的遍歷方法 二叉樹由二叉樹由根根、左子樹、左子樹、右子樹右子樹三部分組成三部分組成 二叉樹的遍歷二叉樹的遍歷可以分解為：訪問可以分解為：訪問根根，遍歷，遍歷左子樹左子樹和和遍歷遍歷右子樹右子樹令：令：L L：遍歷左子樹：遍歷左子樹 T T：訪問根結點訪問根結點 R R：遍歷右子樹遍歷右子樹 約定先左后右約定先左后右, ,有三種遍歷方法：有三種遍歷方法：

33、 T T L L R R、L L T T R R、L L R R T T ，分別稱為分別稱為: : 先序遍歷、中序遍歷、后序遍歷先序遍歷、中序遍歷、后序遍歷 A A F F G G E E D D C C B B345.3 二叉樹的遍歷 先序遍歷（先序遍歷（T T L L R R） 若二叉樹非空若二叉樹非空 （1 1）訪問根結點；）訪問根結點； （2 2）先序遍歷左子樹；）先序遍歷左子樹； （3 3）先序遍歷右子樹）先序遍歷右子樹； 先序遍歷序列：先序遍歷序列：A,A,B,D,B,D,E E,G,G,C,FC,F A A F F G G E E D D C C B B例：先先序遍歷右圖所示的二

34、叉樹序遍歷右圖所示的二叉樹 （1 1）訪問根結點）訪問根結點A A （2 2）先序遍歷左子樹：）先序遍歷左子樹：即按即按 T T L L R R 的順序遍歷的順序遍歷左子樹左子樹 （3 3）先序遍歷右子樹：）先序遍歷右子樹：即按即按 T T L L R R 的順序遍歷的順序遍歷右子樹右子樹355.3 二叉樹的遍歷中序遍歷（中序遍歷（L L T T R R）若二叉樹非空若二叉樹非空（1 1）中序遍歷左子樹）中序遍歷左子樹（2 2）訪問根結點）訪問根結點（3 3）中序遍歷右子樹）中序遍歷右子樹 中序遍歷序列：中序遍歷序列： D,B,G,D,B,G,E E, ,A,A,C,FC,F A A F F

35、G G E E D D C C B B例：例：中序遍歷右圖所示的二叉樹中序遍歷右圖所示的二叉樹 （1 1）中序遍歷左子樹：即按）中序遍歷左子樹：即按 L L T T R R 的順序遍歷的順序遍歷左子樹左子樹 （2 2）訪問根結點）訪問根結點A A （3 3）中序遍歷右子樹：即按）中序遍歷右子樹：即按 L L T T R R 的順序遍歷的順序遍歷右子樹右子樹365.3 二叉樹的遍歷后序遍歷（后序遍歷（L L R R T T）若二叉樹非空若二叉樹非空（1 1）后序遍歷左子樹）后序遍歷左子樹（2 2）后序遍歷右子樹）后序遍歷右子樹（3 3）訪問根結點）訪問根結點 后序遍歷序列：后序遍歷序列： D,G

36、,D,G,E E,B,B,F,CF,C, ,A A例：后例：后序遍歷右圖所示的二叉樹序遍歷右圖所示的二叉樹 （1 1）后序遍歷左子樹：即按）后序遍歷左子樹：即按 L L R R T T 的順序遍歷的順序遍歷左子樹左子樹 （2 2）后序遍歷右子樹：即按）后序遍歷右子樹：即按 L L R R T T 的順序遍歷的順序遍歷右子樹右子樹 （3 3）訪問根結點）訪問根結點A A A A F F G G E E D D C C B B375.3 二叉樹的遍歷 - - e e d d c c b b f f a a + + * * / / - - 后序遍歷序列：后序遍歷序列：a,b,c,d,-,a,b,c,

37、d,-,* *,+,+,e,f,/,e,f,/,- - 中序遍歷序列：中序遍歷序列：a,+,b,a,+,b,* *,c,-,d,c,-,d,- -,e,/,f,e,/,f 先序遍歷序列：先序遍歷序列：- -, ,+,a,+,a,* *,b,-,c,d,b,-,c,d,/,e,f/,e,f例：先例：先序遍歷、中序遍歷、序遍歷、中序遍歷、后后序遍歷下圖所示的二叉樹序遍歷下圖所示的二叉樹385.3 二叉樹的遍歷 若二叉樹非空若二叉樹非空 （1 1）訪問根結點；）訪問根結點； （2 2）先序遍歷左子樹）先序遍歷左子樹 （3 3）先序遍歷右子樹；）先序遍歷右子樹；二二. . 遍歷的遞歸算法遍歷的遞歸算法

38、先序遍歷（T T L L R R）的定義：上面先序遍歷的定義等價于：上面先序遍歷的定義等價于：若二叉樹為空，結束若二叉樹為空，結束 基本項基本項（也叫終止項）（也叫終止項）若二叉樹非空若二叉樹非空 遞歸項遞歸項 （1 1）訪問根結點；）訪問根結點； （2 2）先序遍歷左子樹）先序遍歷左子樹 （3 3）先序遍歷右子樹；）先序遍歷右子樹；395.3 二叉樹的遍歷先序遍歷遞歸算法先序遍歷遞歸算法 void preorder (Bnodept root) if (root!=null) System.out.print(root.data)； preorder(root.lchild); preord

39、er(root.rchild); 先序序列為先序序列為 + * a b c / d e稱為前綴表達式稱為前綴表達式 a a + + * * / / / d d / - -rootroot e e b b c c a a* *(b-c)+d/e(b-c)+d/e405.3 二叉樹的遍歷2 中序遍歷遞歸算法中序遍歷遞歸算法 void inorder (Bnodept root) if (root!=null)inorder(root.lchild); System.out.printf( root.data)； inorder(root.rchild); 中序序列為中序序列為 a * b c+ d

40、 / e稱為中綴表達式稱為中綴表達式你能寫出后序遍歷遞歸算法了吧 a a + + * * / / / d d / - -rootroot e e b b c c a*(b-c)+d/e415.3 二叉樹的遍歷3 后序遍歷遞歸算法后序遍歷遞歸算法 void postorder (Bnodept root) if (root!=null)postorder(root.lchild); postorder(root.rchild); System.out.printf(root.data)； 后序序列為后序序列為 a b c * d e / + 稱為后綴表達式稱為后綴表達式 a a + + * *

41、/ / / d d / - -rootroot e e b b c c a a* *(b-c)+d/e(b-c)+d/e42二叉樹的層次遍歷 二叉樹層次遍歷：先訪問根節(jié)點，再依次訪問下層結點，二叉樹層次遍歷：先訪問根節(jié)點，再依次訪問下層結點，每層結點按從左至右的順序訪問，直至全部結點訪問完每層結點按從左至右的順序訪問，直至全部結點訪問完畢。畢。 其實現(xiàn)可以其實現(xiàn)可以借助隊列借助隊列來完成，算法如下：來完成，算法如下： 1.把根節(jié)點壓入隊列；把根節(jié)點壓入隊列； 2.如果隊列非空，循環(huán)執(zhí)行以下操作：如果隊列非空，循環(huán)執(zhí)行以下操作： 1.從隊列中取出隊頭結點，訪問該結點；從隊列中取出隊頭結點，訪問該

42、結點； 2.若該結點的左孩子結點非空，則將該結點的左孩子結點入隊列；若該結點的左孩子結點非空，則將該結點的左孩子結點入隊列； 3.若該結點的右孩子結點非空，則將該結點的右孩子結點入隊列；若該結點的右孩子結點非空，則將該結點的右孩子結點入隊列； 3.結束結束435.3 二叉樹的遍歷對二叉樹的先序遍歷對二叉樹的先序遍歷：先訪問根結點，然后沿其左鏈一：先訪問根結點，然后沿其左鏈一直訪問下來，直到左鏈為空，最后再從左子樹返回到根直訪問下來，直到左鏈為空，最后再從左子樹返回到根結點，最后訪問其右子樹。結點，最后訪問其右子樹。故需要借助于棧，將根結點進棧保存起來，將遍歷其左故需要借助于棧，將根結點進棧保存

43、起來，將遍歷其左子樹的根結點進棧，。當左子樹遍歷完畢后，再子樹的根結點進棧，。當左子樹遍歷完畢后，再從棧中取回根結點，再對其右子樹進行遍歷進棧操作。從棧中取回根結點，再對其右子樹進行遍歷進棧操作。三三. . 二叉樹遍歷的非遞歸算法二叉樹遍歷的非遞歸算法遞歸算法邏輯清晰、易懂，但在實現(xiàn)時，由于函數(shù)調用棧層層疊加，遞歸算法邏輯清晰、易懂，但在實現(xiàn)時，由于函數(shù)調用棧層層疊加，效率不高，故有時考慮非遞歸算法。效率不高，故有時考慮非遞歸算法。 1 1 先序遍歷（先序遍歷（T L RT L R）的非遞歸算法。）的非遞歸算法。44先序遍歷非遞歸算法步驟先序遍歷非遞歸算法步驟: （1）初始化一個空棧）初始化一

44、個空棧 （2）當前指針指向根結點。將根結點指針進棧）當前指針指向根結點。將根結點指針進棧 （3）打印當前結點，當前指針指向其左孩子并進）打印當前結點，當前指針指向其左孩子并進棧，重復（棧，重復（3），直到左孩子為），直到左孩子為null （4）依次退棧，將當前指針指向其右孩子）依次退棧，將當前指針指向其右孩子 （5）若棧非空或當前指針非）若棧非空或當前指針非null，執(zhí)行（，執(zhí)行（3） （6）結束。）結束。455.3二叉樹的遍歷 d d b b a a * * - - / / c c + + e erootrootp pnode node 6 65 54 43 32 21 10 0toptop

45、System.out.print( root.data);+ +nodetop=p;top+;toptopp=p.lchild;p pSystem.out.print( root.data);* *nodetop=p;top+;toptopp=p.lchild;p pSystem.out.print( root.data) ;a anodetop=p;top+;toptopp=p.lchild;p pif (top0)top - -;toptopp=nodetop;p pp=p.rch;p ptoptopp pp pSystem.out.print( root.data) ;- -nodeto

46、p=p;top+;toptopp=p.lchild;p pb btoptopp ptop - -; p=nodetop; p=p.rch;toptopp ptoptopp pp pp pc cSystem.out.print( root.data)nodetop=p;top+;toptopp=p.lchild;p ptop - -;toptopp=nodetop;p pp=p.rchtoptopp pp p/ /toptopd dSystem.out. print(root.data);nodetop=p;top+; p=p.lchild;465.3 二叉樹的遍歷先序遍歷的非遞歸算法先序遍歷的

47、非遞歸算法void preorder2 (Bnodept root) Bnodept p, nodeMAX; int top=0; p=root; do while( p!=null) System.out.printf(p.data) ; nodetop=p;top+; p=p.lchild; if (top0) top - -; p=nodetop; p=p.rchild; while(top0|p!=null); d d b b e e a a * * - - / / c c + +475.4 遍歷的應用 遍歷是二叉樹的基本操作：二叉樹許多操作遍歷是二叉樹的基本操作：二叉樹許多操作可在遍

48、歷過程中完成，本節(jié)再例子舉幾個二叉可在遍歷過程中完成，本節(jié)再例子舉幾個二叉樹遍歷應用實例。樹遍歷應用實例。485.4 遍歷的應用例例1 編寫編寫 求二叉樹的葉子結點個數(shù)的算法求二叉樹的葉子結點個數(shù)的算法輸入：輸入：二叉樹的二叉鏈表二叉樹的二叉鏈表結果：結果：二叉樹的葉子結點個數(shù)二叉樹的葉子結點個數(shù) F F D D A A B B C C E E rootrootint leaf(Bnodept root) /采用二叉鏈表存貯二叉樹，采用二叉鏈表存貯二叉樹，n為全局變量，用于累加二叉樹的葉子結點為全局變量，用于累加二叉樹的葉子結點 /的個數(shù)。的個數(shù)。本算法在先序遍歷二叉樹的過程中，統(tǒng)計葉子結點的

49、個數(shù)本算法在先序遍歷二叉樹的過程中，統(tǒng)計葉子結點的個數(shù) if(root=null) return 0;/空樹時，空樹時，n=0 else if(root.lchild= =null&root.rch= =null) return 1; /若若root所指點為葉子所指點為葉子, 則返回則返回1 return(leaf(root.lchild)+leaf(root.rchild); 與與先序遍歷算法先序遍歷算法比較一下比較一下！495.4 遍歷的應用 例例2 建立二叉鏈表建立二叉鏈表 輸入：輸入：二叉樹的先序序列二叉樹的先序序列 結果：結果：二叉樹的二叉鏈表二叉樹的二叉鏈表 遍歷操作訪問二叉樹的每

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

51、 * * C E C E * * * * * *505.4 遍歷的應用 輸入輸入（在空子樹處添加空格字符的二叉樹的）在空子樹處添加空格字符的二叉樹的）先序序列先序序列（設每個元素是（設每個元素是一個字一個字 符）符）按先序遍歷的順序，建立二叉鏈表按先序遍歷的順序，建立二叉鏈表，并將該二叉鏈表根結，并將該二叉鏈表根結點指針賦給點指針賦給root Bnodept create_tree(Bnodept root) char ch; Scanner sc=new Scanner(System.in); ch=(sc.nextLine().charAt(0); if (ch= = *) root=nu

52、ll; / 若若ch= = * 則則root=null返回返回 else / 若若ch! = * root=new Bnodept() root.date = ch; / 建立（根）結點建立（根）結點 root.lchild=create_tree(root.lchild); /構造左子樹鏈表，并將左子樹根結點指針構造左子樹鏈表，并將左子樹根結點指針 賦給（根）結點賦給（根）結點 的左孩子域的左孩子域 root.rchild=create_tree(root.rchild); /構造右子樹鏈表，并將右子樹根結點指針構造右子樹鏈表，并將右子樹根結點指針 賦給（根）結點賦給（根）結點 的右孩子域的

53、右孩子域 return (root); 515.4 遍歷的應用 D D A A B B C C E E F F T T 先序序列：先序序列：A B D F C EA B D F C E（在空子樹處添加（在空子樹處添加* *的二叉樹的）先序序列：的二叉樹的）先序序列： A B D F C E A B D F 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 B52 兩點說明兩點說明：1. 按先序次序輸入二叉樹中結點的值，用按先序次序輸入二叉樹中結點的值，用*表示空樹，對每一表示空樹，對每一個結點應當確定其左右子樹的值（為空時必須用特定的空字符占個

54、結點應當確定其左右子樹的值（為空時必須用特定的空字符占位），故執(zhí)行此程序時，最好先在紙上畫出你想建立的二叉樹，每位），故執(zhí)行此程序時，最好先在紙上畫出你想建立的二叉樹，每個結點的左右子樹必須確定，若為空，則用特定字符標出，然后再個結點的左右子樹必須確定，若為空，則用特定字符標出，然后再按先序輸入這棵二叉樹的字符序列；按先序輸入這棵二叉樹的字符序列；2. 為了簡化程序的書寫量，以及程序的清晰性，對結點的訪問為了簡化程序的書寫量，以及程序的清晰性，對結點的訪問以一條輸出語句表示，若有更復雜的或多種訪問，可以將結點的訪以一條輸出語句表示，若有更復雜的或多種訪問，可以將結點的訪問編寫成函數(shù)，然后通過函

55、數(shù)的調用。讀者若有興趣，可自行編寫。問編寫成函數(shù)，然后通過函數(shù)的調用。讀者若有興趣，可自行編寫。5.4 遍歷的應用53 二叉排序樹二叉排序樹 或者為一棵空樹，或為滿足如下條件的二叉樹或者為一棵空樹，或為滿足如下條件的二叉樹 （1）若左子樹非空，則左子樹上所有結點的值均小于它）若左子樹非空，則左子樹上所有結點的值均小于它的根結點的值；的根結點的值； （2）若右子樹非空，則右子樹上所有結點的值均大于它）若右子樹非空，則右子樹上所有結點的值均大于它的根結點的值；的根結點的值； （3）它的左右子樹也分別為二叉排序樹。）它的左右子樹也分別為二叉排序樹。 建立過程示例建立過程示例v二叉樹的建立二叉樹的建立

56、2（建立二叉排序樹（建立二叉排序樹,P206）5.4 遍歷的應用54輸入序列輸入序列45，12，37，3，53，100，24451253337100245.4 遍歷的應用算法思想：算法思想： 設二叉排序樹為設二叉排序樹為b，新申請的結點為，新申請的結點為s。則則（1）若）若b是空樹，將是空樹，將s結點作為根結點；結點作為根結點；（2）若）若s.data等于等于b的根結點的數(shù)據(jù)域，的根結點的數(shù)據(jù)域，不作任何操作；不作任何操作；（3）若）若s.data小于小于b的根結點的數(shù)據(jù)域，的根結點的數(shù)據(jù)域，則將則將s插入到左子樹中；插入到左子樹中；（4）若）若s.data大于大于b的根結點的數(shù)據(jù)域，的根結點

57、的數(shù)據(jù)域，則將則將s插入到右子樹中。插入到右子樹中。55 void insert(Bnodept T,int x) if (T=null|T.data=x) return; /如果結點不存在或數(shù)據(jù)已存在如果結點不存在或數(shù)據(jù)已存在,返回返回 else if(xT.data) /將數(shù)據(jù)結點添加到左子樹將數(shù)據(jù)結點添加到左子樹 if (T.lchild=null) /左子樹為空則創(chuàng)建左子樹為空則創(chuàng)建Bnodept temp=new Bnodept();temp.data=x;temp.lchild=temp.rchild=null;T.lchild=temp;else insert(T.lchild,

58、x); /否則遞歸調用否則遞歸調用 else /數(shù)據(jù)結點添加到右子樹數(shù)據(jù)結點添加到右子樹 if (T.rchild=null) /右子樹為空則創(chuàng)建右子樹為空則創(chuàng)建 Bnodept temp=new Bnodept();temp.data=x;temp.lchild=temp.rchild=null;T.rchild=temp;else insert(T.rchild,x); /否則遞歸調用否則遞歸調用 建立一棵二叉排序樹建立一棵二叉排序樹5.4 遍歷的應用56 void CreateBiTree(Bnodept root) int x;Scanner sc=new Scanner(System

59、.in)x=sc.nextInt(); while (x!=-1)if(root=null) /如果根節(jié)點為空則創(chuàng)建根節(jié)點如果根節(jié)點為空則創(chuàng)建根節(jié)點 root =new Bnodept(); root.data=x; root.lchild=root.rchild=null;else insert(root,x); /否則插入排序數(shù)中否則插入排序數(shù)中 x=sc.nextInt(); 5.4 遍歷的應用57小 結 1 1 二叉樹：二叉樹： 或為空樹，或由根及兩顆不相交的左子或為空樹，或由根及兩顆不相交的左子樹、右子樹構成，并且左、右子樹本身也是二叉樹；樹、右子樹構成，并且左、右子樹本身也是二叉樹

60、； 2 2 二叉樹即可以用順序結構存儲，也可用鏈式結構二叉樹即可以用順序結構存儲，也可用鏈式結構存儲；存儲；3 3 遍歷：按某種搜索路徑訪問二叉樹的每個結點，每遍歷：按某種搜索路徑訪問二叉樹的每個結點，每個結點僅被訪問一次。個結點僅被訪問一次。 二叉樹的遍歷可以分解為：訪二叉樹的遍歷可以分解為：訪問根，遍歷問根，遍歷左子樹和左子樹和遍歷遍歷右子樹，本課程介紹了三種右子樹，本課程介紹了三種遍歷算法：遍歷算法：先序遍歷、中序遍歷、后序遍歷；先序遍歷、中序遍歷、后序遍歷；58第五章 樹和二叉樹 5.5 5.5 線索二叉樹線索二叉樹 一.分析與設計分析與設計 二、線索二叉樹上如何尋找結點的前驅和后繼二