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

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

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

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

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

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

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

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

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

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

n0＝n2+1

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

n2＝n0–1

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

2k-1≤n＜2k

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

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

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

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

k-1≤log2n＜k即：

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

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

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

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

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

i/2；結點i的左孩子為2i；結點i的右孩子為2i＋1。

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

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

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

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

lchild

data

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

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

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

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

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

{

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

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

{Inorder(T->lchild);

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

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

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

D##

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

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

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

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

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

由兩個遍歷序列構造二叉樹先序：ABCDEFG

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

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

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

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); }查找結點的父結點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知識拓展——線索二叉樹在前面討論的二叉樹各種遍歷算法，其本質是將樹形結構轉換為線性序列，便于簡化問題。在遍歷序列中，每個結點都有自己的前驅和后繼，求結點的前驅和后繼屬于基本操作?？焖俚貙崿F(xiàn)這個基本操作，對二叉樹許多算法的性能有重要意義。最簡單的方法是在遍歷過程中尋求答案，缺點是時間復雜度等同遍歷算法的時間復雜度O(n)，這對于基本操作而言，顯然效率太低。為了實現(xiàn)在遍歷序列中快速查找結點的前驅、后繼，可以利用二叉鏈表中空的指針域，指向結點在遍歷序列中的前驅、后繼，這些指向前驅和后繼的指針稱為線索。6.3知識拓展——線索二叉樹線索：將二叉鏈表中的空指針域指向前驅結點和后繼結點的指針被稱為線索；線索化：使二叉鏈表中結點的空鏈域存放其前驅或后繼信息的過程稱為線索化；線索二叉樹：加上線索的二叉樹稱為線索二叉樹。

ltype

lchild

data

childrtype0:lchild指向該結點的左孩子1:lchild指向該結點的前驅結點0:rchild指向該結點的右孩子1:rchild指向該結點的后繼結點ltype=rtype=結點結構6.3知識拓展——線索二叉樹

ltype

lchild

data

rchildrtype結點結構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);//求前驅

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

voidFree(BiThrNode<T>*p);//僅與析構相關

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

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

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

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

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

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

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

問題分析信息編碼是指將信息符號串轉換為編碼文件，其主要目標之一是提高信息的存儲效率。存儲效率可以用編碼系統(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編碼，中文通常寫作哈夫曼編碼。葉子結點的權值：對葉子結點賦予的一個有意義的數(shù)值量。二叉樹的帶權路徑長度：設二叉樹具有n個帶權值的葉子結點，從根結點到各個葉子結點的路徑長度與相應葉子結點權值的乘積之和。

記為：WPL=?=nkkklw1第k個葉子的權值；從根結點到第k個葉子的路徑長度Huffman樹

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

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

6第3步：刪除與加入7542

6Huffman樹的構造

重復第2步7542

65

11W＝{2，4，5，7}Huffman樹的構造過程42

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

1142

65

1142

67

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

7524Huffman樹

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

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