數(shù)據(jù)結(jié)構(gòu)案例教程（CC++版）第2版 課件 第6章 樹和二叉樹

第6章樹和二叉樹請設計一種存儲方法，能便捷地找到每個文件所在的存儲路徑。即要求輸入某個文件名稱后，顯示該文件在U盤中的存儲路徑，若U盤中無該文件，則顯示“文件未找到”。導學問題1：查找U盤中文件的存儲路徑已知算術(shù)表達式6+(7-3)/2對應的表達式樹如圖所示：請求出該表達式的值。導學問題2：表達式樹中的算術(shù)表達式求值(a)一棵樹結(jié)構(gòu)(b)一個非樹結(jié)構(gòu)(c)一個非樹結(jié)構(gòu)ACBGFEDHIACBGFDACBGFDE6.1知識學習6.1.1樹樹的定義樹：n（n≥0）個結(jié)點的有限集合。當n＝0時，稱為空樹；任意一棵非空樹滿足以下條件：⑴有且僅有一個特定的稱為根的結(jié)點；⑵當n＞1時，除根結(jié)點之外的其余結(jié)點被分成m（m>0）個互不相交的有限集合T1,T2,…,Tm，其中每個集合又是一棵樹，并稱為這個根結(jié)點的子樹。樹的定義是采用遞歸方法6.1.1樹樹的基本術(shù)語結(jié)點的度：結(jié)點所擁有的子樹的個數(shù)。葉子結(jié)點：度為0的結(jié)點，也稱為終端結(jié)點。分支結(jié)點：度不為0的結(jié)點，也稱為非終端結(jié)點。樹的度：樹中各結(jié)點度的最大值。6.1.1樹樹的基本術(shù)語孩子、雙親：樹中某結(jié)點子樹的根結(jié)點稱為這個結(jié)點的孩子結(jié)點，這個結(jié)點稱為它孩子結(jié)點的雙親結(jié)點；兄弟：具有同一個雙親的孩子結(jié)點互稱為兄弟。

6.1.1樹樹的基本術(shù)語路徑：如果樹的結(jié)點序列n1,n2,…,nk有如下關(guān)系：結(jié)點ni是ni+1的雙親（1<=i<k），則把n1,n2,…,nk稱為一條由n1至nk的路徑；路徑上經(jīng)過的邊的個數(shù)稱為路徑長度。6.1.1樹樹的基本術(shù)語祖先、子孫：在樹中，如果有一條路徑從結(jié)點x到結(jié)點y，那么x就稱為y的祖先，而y稱為x的子孫。6.1.1樹樹的基本術(shù)語結(jié)點所在層數(shù)：根結(jié)點的層數(shù)為1；對其余任何結(jié)點，若某結(jié)點在第i層，則其孩子結(jié)點在第i+1層。樹的深度：樹中所有結(jié)點的最大層數(shù)，也稱高度。6.1.1樹樹的基本術(shù)語有序樹、無序樹：如果一棵樹中結(jié)點的各子樹從左到右是有次序的，稱這棵樹為有序樹；反之，稱為無序樹。數(shù)據(jù)結(jié)構(gòu)中討論的一般都是有序樹6.1.1樹樹的基本術(shù)語森林：m(m≥0)棵互不相交的樹的集合。6.1.1樹樹結(jié)構(gòu)和線性結(jié)構(gòu)的比較線性結(jié)構(gòu)樹結(jié)構(gòu)第一個數(shù)據(jù)元素根結(jié)點（只有一個）無前驅(qū)無雙親最后一個數(shù)據(jù)元素葉子結(jié)點(可以有多個)無后繼無孩子其它數(shù)據(jù)元素其它結(jié)點一個前驅(qū),一個后繼一個雙親,多個孩子一對一一對多6.1.1樹樹的存儲結(jié)構(gòu)實現(xiàn)樹的存儲結(jié)構(gòu)，關(guān)鍵是什么?如何表示樹中結(jié)點之間的邏輯關(guān)系。存儲問題的出發(fā)點如何表示結(jié)點的雙親和孩子6.1.1樹1）多叉鏈表表示法二叉樹的二叉鏈表結(jié)構(gòu)采用兩個指針域存儲結(jié)點可能有的孩子指針。樹的多叉鏈表表示法延伸了這種結(jié)構(gòu)設計：若樹的度為K，則在結(jié)點結(jié)構(gòu)中設置K個孩子指針域，使所有結(jié)點同構(gòu)。

6.1.1樹2）雙親表示法以一組連續(xù)空間存儲樹的結(jié)點，在每個結(jié)點中設一個指示器指示雙親結(jié)點的位置。6.1.1樹3）孩子鏈表表示法每個結(jié)點的孩子以單鏈表的形式存儲，n個結(jié)點有n個孩子鏈表，n個頭指針又組成一個線性表，并以順序存儲結(jié)構(gòu)存儲。6.1.1樹4）孩子兄弟表示法以二叉鏈表作為樹的存儲結(jié)構(gòu)，鏈表中的結(jié)點的兩個指針分別指向該結(jié)點的第一個孩子結(jié)點和下一個兄弟結(jié)點。研究二叉樹的意義？二叉樹的結(jié)構(gòu)相對簡單，其運算也自然簡單，便于初學者入門。由于多叉樹可以借助一定的規(guī)則轉(zhuǎn)換為二叉樹，因此二叉樹結(jié)構(gòu)在應用中具有非常重要的地位。

6.1.2二叉樹二叉樹的定義二叉樹是n（n≥0）個結(jié)點的有限集合，該集合或者為空集（稱為空二叉樹），或者由一個根結(jié)點和兩棵互不相交的、分別稱為根結(jié)點的左子樹和右子樹的二叉樹組成。6.1.2二叉樹二叉樹的特點每個結(jié)點的度只可能是0，1，2；二叉樹是有序樹，即使某結(jié)點只有一棵子樹，也要區(qū)分該子樹是左子樹還是右子樹。

6.1.2二叉樹二叉樹的5種基本形態(tài)7.2二叉樹的概念和性質(zhì)例：畫出具有3個結(jié)點的樹和具有3個結(jié)點的二叉樹的形態(tài)二叉樹和樹是兩種樹結(jié)構(gòu)。6.1.2二叉樹性質(zhì)1

：二叉樹的第i層上最多有2i-1個結(jié)點（i≥1）。推廣：深度為h的k叉樹中，第i層上最多具有ki－1個結(jié)點。6.1.2二叉樹性質(zhì)2：一棵深度為k的二叉樹中，最多有2k-1個結(jié)點，最少有k個結(jié)點。深度為k且具有2k-1個結(jié)點的二叉樹一定是滿二叉樹，深度為k且具有k個結(jié)點的二叉樹不一定是斜樹。

6.1.2二叉樹性質(zhì)3：在一棵二叉樹中，如果葉子結(jié)點數(shù)為n0，度為2的結(jié)點數(shù)為n2，則有:n0＝n2＋1。

證明:抓住結(jié)點總數(shù)=結(jié)點總度數(shù)+1

n0+n1+n2=n1+2*n2+1n0=n2+1推廣：已知一棵樹度為m的樹中有n1個度為1的結(jié)點，n2個度為2的結(jié)點，…nm個度為m的結(jié)點，問該樹中有多少片葉子？證明：根據(jù)結(jié)點總數(shù)=結(jié)點總度數(shù)+1n0+n1+n2+…+nm=n1+2*n2+…+m*nm+1=>n0=1+n2+…+(m-1)nm6.1.2二叉樹特殊的二叉樹滿二叉樹在一棵二叉樹中，如果所有分支結(jié)點都存在左子樹和右子樹，并且所有葉子都在同一層上。滿二叉樹的特點：葉子只能出現(xiàn)在最下一層；只有度為0和度為2的結(jié)點。6.1.2二叉樹不是滿二叉樹，雖然所有分支結(jié)點都有左右子樹，但葉子不在同一層上。滿二叉樹在同樣深度的二叉樹中結(jié)點個數(shù)最多滿二叉樹在同樣深度的二叉樹中葉子結(jié)點個數(shù)最多A1523467BCDEFGLM89特殊的二叉樹完全二叉樹對一棵具有n個結(jié)點的二叉樹按層序編號，如果編號為i（1≤i≤n）的結(jié)點與同樣深度的滿二叉樹中編號為i的結(jié)點在二叉樹中的位置完全相同。6.1.2二叉樹在滿二叉樹中，從最后一個結(jié)點開始，連續(xù)去掉任意個結(jié)點，即是一棵完全二叉樹。A1523467910BCDEFGHIJK11L12M13N14O158CDEFGHIJ不是完全二叉樹，結(jié)點10與滿二叉樹中的結(jié)點10不是同一個結(jié)點完全二叉樹的特點1.葉子結(jié)點只能出現(xiàn)在最下兩層，且最下層的葉子結(jié)點都集中在二叉樹的左部；2.完全二叉樹中如果有度為1的結(jié)點，只可能有一個，且該結(jié)點只有左孩子。3.深度為k的完全二叉樹在k-1層上一定是滿二叉樹。CDEFGHIJ例：在有n個結(jié)點的滿二叉樹中，有多少個葉子結(jié)點？因為在滿二叉樹中沒有度為1的結(jié)點，只有度為0的葉子結(jié)點和度為2的分支結(jié)點，所以，n＝n0+n2

n0＝n2+1

即葉子結(jié)點n0＝(n+1)/26.1.2二叉樹任一個有n個結(jié)點的二叉樹，有m個葉子結(jié)點，則非葉子結(jié)點數(shù)（度為2）有多少個？因為n0＝n2+1

n2＝n0–1

n2＝m-16.1.2二叉樹證明：假設具有n個結(jié)點的完全二叉樹的深度為k，根據(jù)完全二叉樹的定義和性質(zhì)2，有下式成立

2k-1≤n＜2k

2k-1-1…2k-12k-1———第k-1層———第k層…最少結(jié)點數(shù)最多結(jié)點數(shù)6.1.2二叉樹性質(zhì)4具有n個結(jié)點的完全二叉樹的深度為log2n+1。

log2n+1[log2n]log2n[log2n]+1k所在區(qū)間證明：假設具有n個結(jié)點的完全二叉樹的深度為k，根據(jù)完全二叉樹的定義和性質(zhì)2，有下式成立

2k-1≤n＜2k性質(zhì)4具有n個結(jié)點的完全二叉樹的深度為log2n+1。

對不等式取對數(shù)，有：

k-1≤log2n＜k即：

log2n＜k≤log2n+1由于k是整數(shù)，故必有k＝log2n+1。6.1.2二叉樹性質(zhì)5對一棵具有n個結(jié)點的完全二叉樹中從1開始按層序編號，則對于任意的序號為i（1≤i≤n）的結(jié)點（簡稱為結(jié)點i），有：(1)如果i＞1，則結(jié)點i的雙親結(jié)點的序號為

i/2；如果i＝1，則結(jié)點i是根結(jié)點，無雙親結(jié)點。(2)如果2i≤n，則結(jié)點i的左孩子的序號為2i；

如果2i＞n，則結(jié)點i無左孩子。(3)如果2i＋1≤n，則結(jié)點i的右孩子的序號為2i＋1

如果2i＋1＞n，則結(jié)點i無右孩子。

6.1.2二叉一棵具有n個結(jié)點的完全二叉樹中從1開始按層序編號，則結(jié)點i的雙親結(jié)點為

i/2；結(jié)點i的左孩子為2i；結(jié)點i的右孩子為2i＋1。

性質(zhì)5表明，在完全二叉樹中，結(jié)點的層序編號反映了結(jié)點之間的邏輯關(guān)系。6.1.2二叉樹6.1.2二叉樹二叉樹的順序存儲結(jié)構(gòu)就是用一維數(shù)組存儲二叉樹中的結(jié)點，并且結(jié)點的存儲位置（下標）應能體現(xiàn)結(jié)點之間的邏輯關(guān)系——父子關(guān)系。如何利用數(shù)組下標來反映結(jié)點之間的邏輯關(guān)系?二叉樹的性質(zhì)5為二叉樹的順序存儲指明了存儲規(guī)則：依照完全二叉樹的結(jié)點編號次序，依次存放各個結(jié)點。注意：C/C++中數(shù)組的起始地址為0，編號為i的結(jié)點存儲在下標為i

1的單元內(nèi)。完全二叉樹和滿二叉樹中結(jié)點的序號可以唯一地反映出結(jié)點之間的邏輯關(guān)系。6.1.2二叉樹6.1.2二叉樹采用順序存儲結(jié)構(gòu)，可以直接存取二叉樹中的任意數(shù)據(jù)元素。由于每個數(shù)據(jù)元素的存儲位置暗藏彼此之間的關(guān)系，可以根據(jù)結(jié)點的編號，直接計算出它的父結(jié)點、左/右孩子結(jié)點的位置。類似地，結(jié)點的查找、統(tǒng)計，結(jié)點路徑的識別，都能非常便捷地計算出來。對于滿二叉樹、完全二叉樹來說，順序存儲結(jié)構(gòu)的存儲效率極高，所有的空間僅僅用來存儲數(shù)據(jù)元素的值，結(jié)點之間關(guān)系的存儲未占用任何空間。6.1.2二叉樹對于一般二叉樹而言，如何利用完全二叉樹的編碼規(guī)則來存儲數(shù)據(jù)呢？方法是補足不存在的結(jié)點，用特殊數(shù)據(jù)標識這些替補結(jié)點，使整棵樹在形式上滿足完全二叉樹的定義。

ABC∧DE∧∧∧F∧∧G數(shù)組下標12345678910111213ABCDEGF以編號為下標ABCDEGF123561013按照完全二叉樹編號6.1.2二叉樹一棵斜樹的順序存儲會怎樣呢？深度為k的右斜樹，k個結(jié)點需分配2k－1個存儲單元。

一棵二叉樹改造后成完全二叉樹形態(tài)，需增加很多空結(jié)點，造成存儲空間的浪費。二叉樹的順序存儲結(jié)構(gòu)一般僅存儲完全二叉樹ABC137D156.1.2二叉樹6.1.2二叉樹鏈式存儲基本思想：令二叉樹的每個結(jié)點對應一個鏈表結(jié)點，鏈表結(jié)點除了存放與二叉樹結(jié)點有關(guān)的數(shù)據(jù)信息外，還要設置指示左右孩子的指針。結(jié)點結(jié)構(gòu)：

lchild

data

rchild其中，data：數(shù)據(jù)域，存放該結(jié)點的數(shù)據(jù)信息；lchild：左指針域，存放指向左孩子的指針；rchild：右指針域，存放指向右孩子的指針。

typedefstructBiTNode{ ElemTypedata; structBiTNode*lchild,*rchild;}*BiTree;lchild

datarchild左孩子結(jié)點右孩子結(jié)點二叉鏈表結(jié)構(gòu)定義GFEDBAABCDEFG∧∧∧∧∧∧∧∧C具有n個結(jié)點的二叉鏈表中，有多少個空指針？6.1.2二叉樹GFEDBAABCDEFG∧∧∧∧∧∧∧∧C具有n個結(jié)點的二叉鏈表中，有n+1個空指針。6.1.2二叉樹6.1.2二叉樹二叉樹的遍歷是指從根結(jié)點出發(fā)，按照某種次序訪問二叉樹中的所有結(jié)點，使得每個結(jié)點被訪問一次且僅被訪問一次。二叉樹遍歷操作的結(jié)果？非線性結(jié)構(gòu)線性化抽象操作，可以是對結(jié)點進行的各種處理，這里簡化為輸出結(jié)點的數(shù)據(jù)。先序遍歷中序遍歷后序遍歷層序遍歷

如果限定先左后右，則二叉樹遍歷方式有三種：先序：DLR中序：LDR后序：LRD層序遍歷：按二叉樹的層序編號的次序訪問各結(jié)點。

考慮二叉樹的組成：根結(jié)點D左子樹L右子樹R二叉樹6.1.2二叉樹先序遍歷的概念①若二叉樹為空，則空操作返回；（否則）②訪問根結(jié)點；③先序遍歷根結(jié)點的左子樹；④先序遍歷根結(jié)點的右子樹。先序遍歷序列：ABDGCEFABCDEFG6.1.2二叉樹先序遍歷——遞歸算法voidPreorder(BiTreeT){if(T)

{

cout<<T->data<<"";Preorder(T->lchild);Preorder(T->rchild);}}中序遍歷的概念①若二叉樹為空，則空操作返回；（否則）②中序遍歷根結(jié)點的左子樹；③訪問根結(jié)點；④中序遍歷根結(jié)點的右子樹。

中序遍歷序列：DGBAECFABCDEFG6.1.2二叉樹中序遍歷——遞歸算法voidInorder(BiTreeT){if(T)

{Inorder(T->lchild);

cout<<T->data<<"";Inorder(T->rchild);}}后序遍歷的概念①若二叉樹為空，則空操作返回；（否則）②后序遍歷根結(jié)點的左子樹；③后序遍歷根結(jié)點的右子樹。④訪問根結(jié)點；后序遍歷序列：GDBEFCAABCDEFG6.1.2二叉樹后序遍歷——遞歸算法voidPostorder(BiTreeT){if(T)

{Postorder(T->lchild);Postorder(T->rchild);

cout<<T->data<<"";}}--/+*abcdef二叉樹遍歷操作練習先序遍歷結(jié)果：-+a*b-cd/ef中序遍歷結(jié)果：a+b*c-d-e/f后序遍歷結(jié)果：abcd-*+ef/-6.1.2二叉樹二叉樹的建立遍歷是二叉樹各種操作的基礎，可以在遍歷的過程中進行各種操作，例如建立一棵二叉樹。如何由一種遍歷序列生成該二叉樹？為了建立一棵二叉樹，將二叉樹中每個結(jié)點的空指針引出一個虛結(jié)點，其值為一特定值如“#”，以標識其為空，把這樣處理后的二叉樹稱為原二叉樹的擴展二叉樹。擴展二叉樹的先序遍歷序列：AB#

D##

C##DBAC*DBAC****先序遍歷①若二叉樹為空，則空操作返回；（否則）②訪問根結(jié)點；③先序遍歷根結(jié)點的左子樹；④先序遍歷根結(jié)點的右子樹。DBAC先序創(chuàng)建①若輸入為#(空)，則root=NULL（否則）②創(chuàng)建根結(jié)點；③先序創(chuàng)建根結(jié)點的左子樹；④先序創(chuàng)建根結(jié)點的右子樹。由帶空指針標記的先序序列構(gòu)造二叉樹的算法

voidCreateBiTree(BiTree&T){charch;cin>>ch;if(ch=='#')T=NULL;else{T=newBiTNode;T->data=ch;CreateBiTree(T->lchild);CreateBiTree(T->rchild);}}6.1.3樹、森林與二叉樹的轉(zhuǎn)換樹與二叉樹的轉(zhuǎn)換樹轉(zhuǎn)換成二叉樹二叉樹轉(zhuǎn)換成樹森林與二叉樹的轉(zhuǎn)換森林轉(zhuǎn)換成二叉樹二叉樹轉(zhuǎn)換成森林6.2知識應用導學問題1的實現(xiàn)該問題可轉(zhuǎn)換為在二叉樹中已知葉子結(jié)點，求其雙親結(jié)點，即求從根節(jié)點到該結(jié)點的路徑。將圖6-1中的文件夾和文件抽象成一個結(jié)點，則圖6-7所示的就是其相應的邏輯結(jié)構(gòu)和雙親表示法存儲結(jié)構(gòu)。6.2知識應用導學問題2的實現(xiàn)為簡化討論，假設表達式中僅有四種雙目操作符：+、-、*、/。顯然，圖6-2所示的表達式樹是一棵二叉樹，其中葉子結(jié)點是操作數(shù)，非葉子結(jié)點是操作符。對該表達式樹進行先序、中序和后序遍歷，便可得到表達式相應的前綴、中綴和后綴表示?；诒磉_式樹的求值過程實際上是一個后序遍歷的過程。6.3知識拓展二叉樹的其他操作計算二叉樹的結(jié)點數(shù)。計算二叉樹的結(jié)點總數(shù)等于其左、右子樹結(jié)點樹加上1（根結(jié)點），因此可利用后序遍歷框架，將對整個二叉樹結(jié)點進行技術(shù)的目標分解成對左、右子樹的計數(shù)。6.3知識拓展二叉樹的其他操作計算二叉樹的高度。二叉樹中任一結(jié)點的高度是其左、右子樹高度的最大值加1，而根結(jié)點的高度就是整棵二叉樹的高度。因此，要計算根結(jié)點的高度，必須要先求得左、右子樹的高度，這可以利用后序遍歷實現(xiàn)。層次遍歷的概念二叉樹的層次遍歷是指從二叉樹的第一層（即根結(jié)點）開始，從上至下逐層遍歷，在同一層中，則按從左到右的順序?qū)Y(jié)點逐個訪問。

層序遍歷序列：ABCDEFGABCDEFG6.3知識拓展層次遍歷ABCDEFG遍歷序列：AABCBDCEFGDEFG6.3知識拓展①若二叉樹為空，遍歷結(jié)束。②將根指針加入指針隊列。③若指針隊列不空，執(zhí)行步驟④；若指針隊列為空，則遍歷結(jié)束。④隊首元素出隊，記作p，p所指的結(jié)點稱為當前結(jié)點，訪問當前結(jié)點。⑤若當前結(jié)點的左孩子指針不空，將左孩子指針入隊；若當前結(jié)點的右孩子指針不空，右孩子指針入隊。⑥轉(zhuǎn)步驟③。二叉樹的層次遍歷算法

若已知一棵二叉樹的先序（或中序，或后序，或?qū)有颍┬蛄?，能否唯一確定這棵二叉樹呢？ABC例：已知先序序列為ABC，則可能的二叉樹有5種。ABC6.3知識拓展例：已知先序遍歷序列為ABC，后序遍歷序列為CBA，則下列二叉樹都滿足條件。ABCABC若已知一棵二叉樹的先序序列和后序序列，能否唯一確定這棵二叉樹呢？由兩個遍歷序列構(gòu)造二叉樹若已知一棵二叉樹的先序序列和中序序列，能否唯一確定這棵二叉樹呢？怎樣確定？

例如：已知一棵二叉樹的先序遍歷序列和中序遍歷序列分別為ABCDEFGHI和BCAEDGHFI，如何構(gòu)造該二叉樹呢?

由兩個遍歷序列構(gòu)造二叉樹先序：ABCDEFG

HI中序：BCAEDGHFI先序：BC中序：BC

BCDEFGHIA先序：DEFGHI中序：EDGHFIABCDEFGHI先序：FG

HI中序：GHFI先序：DEFGHI中序：EDGHFIABCDEFGHIABCDEFIGH由兩個遍歷序列構(gòu)造二叉樹已知一棵二叉樹的先序序列和中序序列，構(gòu)造該二叉樹的過程如下：1.根據(jù)先序序列的第一個元素建立根結(jié)點；2.在中序序列中找到該元素，確定根結(jié)點的左右子樹的中序序列；3.在先序序列中確定左右子樹的先序序列；4.由左子樹的先序序列和中序序列建立左子樹；5.由右子樹的先序序列和中序序列建立右子樹。BiTreePreInCreate(charpre[],charin[],intipre,intimid,intn){ inti; if(n==0) returnNULL; BiTreep=newBiTNode; //創(chuàng)建根結(jié)點 p->data=pre[ipre]; for(i=0;i<n;i++) //在中序序列中查找根結(jié)點位置 if(pre[ipre]==in[imid+i]) break; p->lchild=PreInCreate(pre,in,ipre+1,imid,i); p->rchild=PreInCreate(pre,in,ipre+i+1,imid+i+1,n-i-1); returnp;}根據(jù)關(guān)鍵值查找結(jié)點

BiTreeSearch(BiTreeT,ElemTypex){ BiTreeq; if(T==NULL) returnNULL; if(T->data==x) returnT; q=Search(T->lchild,x); if(q!=NULL)returnq; returnSearch(T->rchild,x); }查找結(jié)點的父結(jié)點BiTreeSearchParent(BiTreeT,BiTreechild){BiTreeq; if(T==NULL||child==NULL) returnNULL;if(T->lchild==child||T->rchild==child) returnT; q=SearchParent(T->lchild,child);if(q!=NULL)returnq; returnSearchParent(T->rchild,child); }6.3知識拓展——線索二叉樹在前面討論的二叉樹各種遍歷算法，其本質(zhì)是將樹形結(jié)構(gòu)轉(zhuǎn)換為線性序列，便于簡化問題。在遍歷序列中，每個結(jié)點都有自己的前驅(qū)和后繼，求結(jié)點的前驅(qū)和后繼屬于基本操作?？焖俚貙崿F(xiàn)這個基本操作，對二叉樹許多算法的性能有重要意義。最簡單的方法是在遍歷過程中尋求答案，缺點是時間復雜度等同遍歷算法的時間復雜度O(n)，這對于基本操作而言，顯然效率太低。為了實現(xiàn)在遍歷序列中快速查找結(jié)點的前驅(qū)、后繼，可以利用二叉鏈表中空的指針域，指向結(jié)點在遍歷序列中的前驅(qū)、后繼，這些指向前驅(qū)和后繼的指針稱為線索。6.3知識拓展——線索二叉樹線索：將二叉鏈表中的空指針域指向前驅(qū)結(jié)點和后繼結(jié)點的指針被稱為線索；線索化：使二叉鏈表中結(jié)點的空鏈域存放其前驅(qū)或后繼信息的過程稱為線索化；線索二叉樹：加上線索的二叉樹稱為線索二叉樹。

ltype

lchild

data

childrtype0:lchild指向該結(jié)點的左孩子1:lchild指向該結(jié)點的前驅(qū)結(jié)點0:rchild指向該結(jié)點的右孩子1:rchild指向該結(jié)點的后繼結(jié)點ltype=rtype=結(jié)點結(jié)構(gòu)6.3知識拓展——線索二叉樹

ltype

lchild

data

rchildrtype結(jié)點結(jié)構(gòu)6.3知識拓展——線索二叉樹enumflag{Child,Thread};typedefstructBiThrNode{

ElemTypedata;

structBiThrNode*lchild,*rchild;flagltype,rtype;}*BiThrTree;線索二叉樹的畫法先序線索二叉樹：先序序列為：ABCD中序線索二叉樹：中序序列為：BADC線索二叉樹的畫法后序線索二叉樹：后序序列為：BDCA線索二叉樹的畫法template<classT>classInBiThrTree{ BiThrNode<T>*root;public:

InBiThrTree(){root=NULL;}

InBiThrTree(vector<T>&pre);//根據(jù)pre創(chuàng)建二叉樹

~InBiThrTree(); voidInThreaded();//中序線索化

BiThrNode<T>*GetNext(BiThrNode<T>*p);//求后繼

BiThrNode<T>*GetPrev(BiThrNode<T>*p);//求前驅(qū)

voidTravese();//中序遍歷private: BiThrNode<T>*CreateByPre(vector<T>&pre,int&i);//僅與InBiThrTree(vector<T>&pre)相關(guān)

voidFree(BiThrNode<T>*p);//僅與析構(gòu)相關(guān)

voidInThreaded(BiThrNode<T>*p,BiThrNode<T>*&pre);//僅與InThreaded()相關(guān)};線索二叉樹的存儲結(jié)構(gòu)分析：建立線索鏈表，實質(zhì)上就是將二叉鏈表中的空指針改為指向前驅(qū)或后繼的線索，而前驅(qū)或后繼的信息只有在遍歷該二叉樹時才能得到。建立二叉鏈表遍歷二叉樹，將空指針改為線索中序線索鏈表的建立A頭指針BCDEFG∧∧∧∧∧∧00000000000000∧∧中序線索鏈表的建立過程建立二叉鏈表遍歷二叉樹，將空指針改為線索A頭指針BCDEFG∧∧∧∧∧∧00000000000000∧∧中序遍歷二叉鏈表p為正在訪問的結(jié)點pre為剛訪問過的結(jié)點p1中序線索鏈表的建立過程建立二叉鏈表遍歷二叉樹，將空指針改為線索A頭指針BCDEFG∧∧∧∧∧∧00000000000000∧∧pre1p11中序遍歷二叉鏈表p為正在訪問的結(jié)點pre為剛訪問過的結(jié)點中序線索鏈表的建立過程建立二叉鏈表遍歷二叉樹，將空指針改為線索A頭指針BCDEFG∧∧∧∧∧∧00000000000000∧pre11p11中序遍歷二叉鏈表p為正在訪問的結(jié)點pre為剛訪問過的結(jié)點中序線索鏈表的建立過程建立二叉鏈表遍歷二叉樹，將空指針改為線索A頭指針BCDEFG∧∧∧∧∧∧00000000000000pre11p11中序遍歷二叉鏈表p為正在訪問的結(jié)點pre為剛訪問過的結(jié)點中序線索鏈表的建立過程建立二叉鏈表遍歷二叉樹，將空指針改為線索A頭指針BCDEFG∧∧∧∧∧00000000000000pre11p1111中序遍歷二叉鏈表p為正在訪問的結(jié)點pre為剛訪問過的結(jié)點中序線索鏈表的建立過程建立二叉鏈表遍歷二叉樹，將空指針改為線索A頭指針BCDEFG∧∧∧∧00000000000000pre11p1111中序遍歷二叉鏈表p為正在訪問的結(jié)點pre為剛訪問過的結(jié)點中序線索鏈表的建立過程建立二叉鏈表遍歷二叉樹，將空指針改為線索A頭指針BCDEFG∧∧∧00000000000000pre11p11111中序遍歷二叉鏈表p為正在訪問的結(jié)點pre為剛訪問過的結(jié)點中序線索鏈表的建立過程建立二叉鏈表遍歷二叉樹，將空指針改為線索A頭指針BCDEFG∧∧00000000000000pre11111111中序遍歷二叉鏈表p為正在訪問的結(jié)點pre為剛訪問過的結(jié)點中序線索鏈表的建立過程建立二叉鏈表遍歷二叉樹，將空指針改為線索遍歷二叉鏈表，建立線索：①如果二叉鏈表T為空，則空操作返回；②對T的左子樹建立線索；③對T所指結(jié)點建立線索；

若T沒有左孩子，則為T加上前驅(qū)線索;

若T沒有右孩子，則將T右標志置為1；

若結(jié)點prenode右標志為1，則為prenode加上后繼線索；

令prenode指向剛剛訪問的結(jié)點T；④對T的右子樹建立線索。建立二叉鏈表遍歷二叉樹，將空指針改為線索中序線索鏈表的建立過程建立二叉鏈表遍歷二叉樹，將空指針改為線索中序線索鏈表的建立過程voidInThreaded(BiThrTree&T){ if(T==NULL)//如果二叉鏈表p為空，則空操作返回 return; InThreaded(T->lchild);//線索化左子樹

if(T->lchild==NULL) //對p的左指針處理 { T->ltype=Thread; T->lchild=prenode; } if(T->rchild==NULL) //對p的右指針處理 T->rtype=Thread; if(prenode!=NULL) { if(prenode->rtype==Thread) prenode->rchild=T; } prenode=T;

InThreaded(T->rchild);//線索化右子樹}中序線索鏈表上查找結(jié)點P的后繼對于中序線索二叉樹上的任一結(jié)點，尋找其中序的后繼結(jié)點，有以下兩種情況：1）如果該結(jié)點的右標志為1，即無右孩子，那么其右指針域所指向的結(jié)點便是它的后繼結(jié)點；2）如果該結(jié)點的右標志為0，表明該結(jié)點有右孩子，根據(jù)中序遍歷的定義，它的前驅(qū)結(jié)點是以該結(jié)點的右孩子為根結(jié)點的子樹的最左結(jié)點，即沿著其右子樹的左指針鏈向下查找，當某結(jié)點的左標志為1時，它就是所要找的后繼結(jié)點。

if(p->rtype==Thread)returnp->rchild;p=p->rchild;while(p->ltype==Child)p=p->lchild;中序線索鏈表上查找結(jié)點P的前驅(qū)對于中序線索二叉樹上的任一結(jié)點，尋找其中序的前驅(qū)結(jié)點，有以下兩種情況：1）如果該結(jié)點的左標志為1，即無左孩子，那么其左指針域所指向的結(jié)點便是它的前驅(qū)結(jié)點；2）如果該結(jié)點的左標志為0，即有左孩子，表明該結(jié)點有左孩子，根據(jù)中序遍歷的定義，它的前驅(qū)結(jié)點是以該結(jié)點的左孩子為根結(jié)點的子樹的最右結(jié)點，即沿著其左子樹的右指針鏈向下查找，當某結(jié)點的右標志為1時，它就是所要找的前驅(qū)結(jié)點。if(p->ltype==Thread)returnp->lchild;p=p->lchild;while(p->rtype==Child)p=p->rchild;在中序線索二叉樹上遍歷利用在中序線索二叉樹上尋找后繼結(jié)點和前驅(qū)結(jié)點的算法，就可以遍歷到二叉樹的所有結(jié)點。比如，先找到按某序遍歷的第一個結(jié)點，然后再依次查詢其后繼；或先找到按某序遍歷的最后一個結(jié)點，然后再依次查詢其前驅(qū)。這樣，既不用棧也不用遞歸就可以訪問到二叉樹的所有結(jié)點。在中序線索二叉樹上查找值為x的結(jié)點在中序線索二叉樹上查找值為x的結(jié)點，實質(zhì)上就是在線索二叉樹上進行遍歷，將訪問結(jié)點的操作具體寫為那結(jié)點的值與x比較的語句。6.3知識拓展——Huffman樹與Huffman編碼

信息編碼問題假設給定一個字符串“ADCBDABDCBDBCDCDCD”，請對其中字符進行編碼，使得該字符串的編碼存儲空間最少，且從存儲空間取出編碼也能還原成唯一的原字符串。Huffman樹與Huffman編碼

問題分析信息編碼是指將信息符號串轉(zhuǎn)換為編碼文件，其主要目標之一是提高信息的存儲效率。存儲效率可以用編碼系統(tǒng)的平均碼長來衡量。設編碼系統(tǒng)中有

個符號，每個符號的編碼長度為L1,L2,…,Ln，各符號出現(xiàn)的頻率分別是F1,F2,…,Fn，則Huffman樹與Huffman編碼

問題分析信息編碼的方法可分為定長編碼和不定長編碼兩大類。定長編碼是指在編碼系統(tǒng)中，每個符號的代碼長度相等，如常用的ASCII碼，每個符號的編碼都是一個字節(jié)。不定長編碼應用于各種符號的使用頻率差異較大的場合。其基本思想是利用各種符號出現(xiàn)的統(tǒng)計頻率來編碼，使經(jīng)常出現(xiàn)的符號的編碼較短，不常出現(xiàn)的符號的編碼較長，目的是使信息經(jīng)過編碼后的編碼文件長度盡可能短。因此不定長編碼也稱為統(tǒng)計編碼。統(tǒng)計編碼相比定長編碼不僅節(jié)省磁盤空間，還能起到提高傳遞、運算速度的效果。Huffman樹與Huffman編碼

問題分析信息編碼的方法可分為定長編碼和不定長編碼兩大類。不定長編碼的優(yōu)點：存儲效率優(yōu)于定長編碼的效率。缺點：不定長編碼由于碼長不固定，在還原字符時，存在各符號的碼串相互混淆的可能。如問題中原字符串前兩個字符為“AD”，用上述不定長編碼，編碼串為“101”，進行還原時，可以解釋為“AD”也可以解釋為“DB”，因此這樣的編碼方式不能還原成唯一的原字符串。不定長編碼必須增加約束條件：在同一編碼系統(tǒng)中，任何符號的編碼不能是另一符號編碼的前綴。滿足此條件的編碼也被稱為前綴編碼，有效的統(tǒng)計編碼一定是前綴編碼。Huffman樹與Huffman編碼

問題分析如何設計高效率的前綴編碼？1952年正在麻省理工攻讀博士學位的DavidA.Huffman給出了最優(yōu)解決方案，即Huffman編碼，中文通常寫作哈夫曼編碼。葉子結(jié)點的權(quán)值：對葉子結(jié)點賦予的一個有意義的數(shù)值量。二叉樹的帶權(quán)路徑長度：設二叉樹具有n個帶權(quán)值的葉子結(jié)點，從根結(jié)點到各個葉子結(jié)點的路徑長度與相應葉子結(jié)點權(quán)值的乘積之和。

記為：WPL=?=nkkklw1第k個葉子的權(quán)值；從根結(jié)點到第k個葉子的路徑長度Huffman樹

Huffman樹：給定一組具有確定權(quán)值的葉子結(jié)點，帶權(quán)路徑長度最小的二叉樹。例：對于“ADCBDABDCBDBCDCDCD”，4個葉子結(jié)點ABCD，其權(quán)值分別為{2，4，5，7}，可以構(gòu)造出形狀不同的多個二叉樹。WPL=36WPL=46WPL=41245724574527Huffman樹

圖中有Huffman樹嗎？如何快速地構(gòu)造一棵Huffman？第1步：初始化W＝{2，4，5，7}Huffman樹的構(gòu)造過程7524第2步：選取與合并42

6第3步：刪除與加入7542

6Huffman樹的構(gòu)造

重復第2步7542

65

11W＝{2，4，5，7}Huffman樹的構(gòu)造過程42

6重復第3步W＝{2，4，5，7}Huffman樹的構(gòu)造過程75

1142

65

1142

67

18重復第2步Huffman樹的特點：1.權(quán)值越大的葉子結(jié)點越靠近根結(jié)點，而權(quán)值越小的葉子結(jié)點越遠離根結(jié)點。2.只有度為0（葉子結(jié)點）和度為2（分支結(jié)點）的結(jié)點，不存在度為1的結(jié)點。

7524Huffman樹

Huffman樹的存儲結(jié)構(gòu)設置一個數(shù)組（向量）huffTree[2n-1]保存哈夫曼樹中各點的信息，數(shù)組（向量）元素的結(jié)點結(jié)構(gòu)。data：編碼值weight：權(quán)值域，保存該結(jié)點的權(quán)值；lchild：指針域，結(jié)點的左孩子結(jié)點在數(shù)組中的下標；rchild：指針域，結(jié)點的右孩子結(jié)點在數(shù)組中的下標；parent：指針域，該結(jié)點的雙親結(jié)點在數(shù)組中的下標。

dataweightlchildrchildparentweightparentlchildrchild-1-1-1-1-1-1-1-1-1-1-1-10123456初態(tài)752424572-1-1-14-1-1