工學(xué)數(shù)據(jù)結(jié)構(gòu)第6章樹和二叉樹課件

數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容1數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容1第6章樹和二叉樹（Tree&BinaryTree）6.1

樹的基本概念6.2二叉樹6.3遍歷二叉樹和線索二叉樹6.4樹和森林6.5赫夫曼樹及其應(yīng)用2第6章樹和二叉樹（Tree&BinaryTre6.1樹的基本概念1. 樹的定義2. 若干術(shù)語3. 邏輯結(jié)構(gòu)4. 存儲結(jié)構(gòu)5. 樹的運算36.1樹的基本概念1. 樹的定義31.樹的定義注1：過去許多書籍中都定義樹為n≥1，曾經(jīng)有“空樹不是樹”的說法，但現(xiàn)在樹的定義已修改。注2：樹的定義具有遞歸性，即樹中還有樹。由一個或多個(n≥0)結(jié)點組成的有限集合T，有且僅有一個結(jié)點稱為根（root），當(dāng)n>1時，其余的結(jié)點分為m(m≥0)個互不相交的有限集合T1,T2，…，Tm。每個集合本身又是棵樹，被稱作這個根的子樹。41.樹的定義注1：過去許多書籍中都定義樹為n≥1，曾樹的表示法有幾種：圖形表示法嵌套集合表示法廣義表表示法目錄表示法5樹的表示法有幾種：圖形表示法5樹的抽象數(shù)據(jù)類型定義（見教材P118-119）ADTTree{數(shù)據(jù)對象D:數(shù)據(jù)關(guān)系R:基本操作P：}ADTTree若D為空集，則稱為空樹；//允許n=0若D中僅含一個數(shù)據(jù)元素，則R為空集；其他情況下的R存在二元關(guān)系：①root唯一//關(guān)于根的說明②Dj∩Dk=Φ//關(guān)于子樹不相交的說明③……//關(guān)于子樹的子樹不相交的說明D是具有相同特性的數(shù)據(jù)元素的集合。6樹的抽象數(shù)據(jù)類型定義（見教材P118-119）ADTTr6.1樹的基本概念1. 樹的定義2. 若干術(shù)語3. 邏輯結(jié)構(gòu)4. 存儲結(jié)構(gòu)5. 樹的運算76.1樹的基本概念1. 樹的定義72.若干術(shù)語——即上層的那個結(jié)點(直接前驅(qū))——即下層結(jié)點的子樹的根(直接后繼)——同一雙親下的同層結(jié)點（孩子之間互稱兄弟）——即雙親位于同一層的結(jié)點（但并非同一雙親）——即從根到該結(jié)點所經(jīng)分支的所有結(jié)點——即該結(jié)點下層子樹中的任一結(jié)點ABCGEIDHFJMLK根葉子森林有序樹無序樹——即根結(jié)點(沒有前驅(qū))——即終端結(jié)點(沒有后繼)——指m棵不相交的樹的集合(例如刪除A后的子樹個數(shù))雙親孩子兄弟堂兄弟祖先子孫——結(jié)點各子樹從左至右有序，不能互換（左為第一）——結(jié)點各子樹可互換位置。82.若干術(shù)語——即上層的那個結(jié)點(直接前驅(qū))ABCG2.若干術(shù)語（續(xù)）——即樹的數(shù)據(jù)元素——結(jié)點掛接的子樹數(shù)（有幾個直接后繼就是幾度，亦稱“次數(shù)”）結(jié)點結(jié)點的度結(jié)點的層次終端結(jié)點分支結(jié)點樹的度樹的深度(或高度)ABCGEIDHFJMLK——從根到該結(jié)點的層數(shù)（根結(jié)點算第一層）——即度為0的結(jié)點，即葉子——即度不為0的結(jié)點（也稱為內(nèi)部結(jié)點）——所有結(jié)點度中的最大值（Max{各結(jié)點的度}）——指所有結(jié)點中最大的層數(shù)（Max{各結(jié)點的層次}）問：右上圖中的結(jié)點數(shù)＝；樹的度＝；樹的深度＝133492.若干術(shù)語（續(xù)）——即樹的數(shù)據(jù)元素結(jié)點樹的度ABC6.1樹的基本概念1. 樹的定義2. 若干術(shù)語3. 邏輯結(jié)構(gòu)4. 存儲結(jié)構(gòu)5. 樹的運算106.1樹的基本概念1. 樹的定義103.樹的邏輯結(jié)構(gòu)

(特點)：一對多（1:n），有多個直接后繼（如家譜樹、目錄樹等等），但只有一個根結(jié)點，且子樹之間互不相交。113.樹的邏輯結(jié)構(gòu)(特點)：一對多（1:n），有多個直接6.1樹的基本概念1. 樹的定義2. 若干術(shù)語3. 邏輯結(jié)構(gòu)4. 存儲結(jié)構(gòu)5. 樹的運算126.1樹的基本概念1. 樹的定義124.樹的存儲結(jié)構(gòu)

討論1：樹是非線性結(jié)構(gòu)，該怎樣存儲？————仍然有順序存儲、鏈?zhǔn)酱鎯Φ确绞健?/p>

134.樹的存儲結(jié)構(gòu)討論1：樹是非線性結(jié)構(gòu)，該怎樣存儲？13討論3：樹的鏈?zhǔn)酱鎯Ψ桨笐?yīng)該怎樣制定？可規(guī)定為：從上至下、從左至右將樹的結(jié)點依次存入內(nèi)存。重大缺陷：復(fù)原困難（不能唯一復(fù)原就沒有實用價值）。討論2：樹的順序存儲方案應(yīng)該怎樣制定？可用多重鏈表：一個前趨指針，n個后繼指針。細節(jié)問題：樹中結(jié)點的結(jié)構(gòu)類型樣式該如何設(shè)計？

即應(yīng)該設(shè)計成“等長”還是“不等長”？缺點：等長結(jié)構(gòu)太浪費（每個結(jié)點的度不一定相同）；不等長結(jié)構(gòu)太復(fù)雜（要定義好多種結(jié)構(gòu)類型）。解決思路：先研究最簡單、最有規(guī)律的樹，然后設(shè)法把一般的樹轉(zhuǎn)化為簡單樹。14討論3：樹的鏈?zhǔn)酱鎯Ψ桨笐?yīng)該怎樣制定？可規(guī)定為：從上至下、從6.1樹的基本概念1. 樹的定義2. 若干術(shù)語3. 邏輯結(jié)構(gòu)4. 存儲結(jié)構(gòu)5. 樹的運算156.1樹的基本概念1. 樹的定義155.樹的運算

要明確：1.普通樹（即多叉樹）若不轉(zhuǎn)化為二叉樹，則運算很難實現(xiàn)。2.二叉樹的運算仍然是插入、刪除、修改、查找、排序等，但這些操作必須建立在對樹結(jié)點能夠“遍歷”的基礎(chǔ)上！（遍歷——指每個結(jié)點都被訪問且僅訪問一次，不遺漏不重復(fù)）。165.樹的運算要明確：16第6章樹和二叉樹（Tree&BinaryTree）6.1樹的基本概念6.2二叉樹6.3遍歷二叉樹和線索二叉樹6.4樹和森林6.5赫夫曼樹及其應(yīng)用17第6章樹和二叉樹（Tree&BinaryTre6.2二叉樹為何要重點研究每結(jié)點最多只有兩個“叉”的樹？二叉樹的結(jié)構(gòu)最簡單，規(guī)律性最強；可以證明，所有樹都能轉(zhuǎn)為唯一對應(yīng)的二叉樹。1. 二叉樹的定義2. 二叉樹的性質(zhì)3. 二叉樹的存儲結(jié)構(gòu)186.2二叉樹為何要重點研究每結(jié)點最多只有兩個“叉”1.二叉樹的定義定義：是n（n≥0）個結(jié)點的有限集合，由一個根結(jié)點以及兩棵互不相交的、分別稱為左子樹和右子樹的二叉樹組成。邏輯結(jié)構(gòu)：一對二（1：2）

基本特征:①每個結(jié)點最多只有兩棵子樹（不存在度大于2的結(jié)點）；②左子樹和右子樹次序不能顛倒（有序樹）?；拘螒B(tài)：

問：具有3個結(jié)點的二叉樹可能有幾種不同形態(tài)？普通樹呢？

5種/2種191.二叉樹的定義定義：是n（n≥0）個結(jié)點的有限集合，由一二叉樹的抽象數(shù)據(jù)類型定義（見教材P121-122）ADTBinaryTree{數(shù)據(jù)對象D:數(shù)據(jù)關(guān)系R:基本操作P：}ADTBinaryTree若D=Φ，則R=Φ；若D≠Φ，則R={H}；存在二元關(guān)系：①root唯一//關(guān)于根的說明②Dj∩Dk=Φ//關(guān)于子樹不相交的說明③……//關(guān)于根和左右子樹有唯一聯(lián)系的說明

④……

//關(guān)于左子樹和右子樹的說明D是具有相同特性的數(shù)據(jù)元素的集合。20二叉樹的抽象數(shù)據(jù)類型定義（見教材P121-122）ADTB6.2二叉樹1. 二叉樹的定義2. 二叉樹的性質(zhì)3. 二叉樹的存儲結(jié)構(gòu)216.2二叉樹1. 二叉樹的定義212.二叉樹的性質(zhì)(3+2)討論1：第i層的結(jié)點數(shù)至多是多少？

（利用二進制性質(zhì)可輕松求出）

性質(zhì)1:在二叉樹的第i層上至多有2i-1個結(jié)點（i>0）。性質(zhì)2:深度為k的二叉樹至多有2k-1個結(jié)點（k>0）。2i-1個提問：第i層上至少有

個結(jié)點？1討論2：深度為k的二叉樹，至多有多少個結(jié)點？

（利用二進制性質(zhì)可輕松求出）2k-1提問：深度為k時至少有

個結(jié)點？k222.二叉樹的性質(zhì)(3+2)討論1：第i層的結(jié)點數(shù)至討論3：二叉樹的葉子數(shù)和度為2的結(jié)點數(shù)之間有關(guān)系嗎？性質(zhì)3:對于任何一棵二叉樹，若2度的結(jié)點數(shù)有n2個，則葉子數(shù)（n0）必定為n2＋1（即n0=n2+1）證明：∵二叉樹中全部結(jié)點數(shù)n＝n0+n1+n2(葉子數(shù)＋1度結(jié)點數(shù)＋2度結(jié)點數(shù))又∵二叉樹中全部結(jié)點數(shù)n＝B+1

(總分支數(shù)＋根結(jié)點)（除根結(jié)點外，每個結(jié)點必有一個直接前趨，即一個分支）而總分支數(shù)B=n1+2n2(1度結(jié)點必有1個直接后繼，2度結(jié)點必有2個)三式聯(lián)立可得：n0+n1+n2=

n1+2n2+1,即n0=n2+1實際意義：葉子數(shù)＝2度結(jié)點數(shù)＋1ABCGEIDHFJ23討論3：二叉樹的葉子數(shù)和度為2的結(jié)點數(shù)之間有關(guān)系嗎？性質(zhì)3:對于兩種特殊形式的二叉樹（滿二叉樹和完全二叉樹），還特別具備以下2個性質(zhì)：性質(zhì)4:具有n個結(jié)點的完全二叉樹的深度必為log2n＋1性質(zhì)5:對完全二叉樹，若從上至下、從左至右編號，則編號為i

的結(jié)點，其左孩子編號必為2i，其右孩子編號必為2i＋1；其雙親的編號必為i/2（i＝1時為根,除外）。證明：根據(jù)性質(zhì)2，深度為k的二叉樹最多只有2k-1個結(jié)點，且完全二叉樹的定義是與同深度的滿二叉樹前面編號相同，即它的總結(jié)點數(shù)n位于k層和k-1層滿二叉樹容量之間，即2k-1-1<n≤2k-1或2k-1≤n<2k三邊同時取對數(shù)，于是有：k-1≤log2n<k因為k是整數(shù)，所以k=log2n+1x----表示不大于x的最大整數(shù)X----表示不小于x的最小整數(shù)24對于兩種特殊形式的二叉樹（滿二叉樹和完全二叉樹），還特別具備滿二叉樹：一棵深度為k且有2k-1個結(jié)點的二叉樹。

（特點：每層都“充滿”了結(jié)點）完全二叉樹：深度為k的，有n個結(jié)點的二叉樹，當(dāng)且僅當(dāng)其每一個結(jié)點都與深度為k的滿二叉樹中編號從1至n的結(jié)點一一對應(yīng)。AOBCGEKDJFIHNML深度為4的滿二叉樹深度為4的完全二叉樹ABCGEIDHFJ為何要研究這兩種特殊形式？因為它們在順序存儲方式下可以復(fù)原！

解釋：完全二叉樹的特點就是，只有最后一層葉子不滿，且全部集中在左邊。這其實是順序二叉樹的含義。25滿二叉樹：一棵深度為k且有2k-1個結(jié)點的二叉樹。

3.深度為9的二叉樹中至少有

個結(jié)點。

Ａ)２9Ｂ)２8Ｃ)９Ｄ)２9－12.深度為k的二叉樹的結(jié)點總數(shù)，最多為

個。

Ａ)２k-1Ｂ)log2kＣ)２k－１Ｄ)２k課堂練習(xí)：1.樹Ｔ中各結(jié)點的度的最大值稱為樹Ｔ的

。

Ａ)高度Ｂ)層次Ｃ)深度Ｄ)度課堂討論：滿二叉樹和完全二叉樹有什么區(qū)別？答：滿二叉樹是葉子一個也不少的樹，而完全二叉樹雖然前n-1層是滿的，但最底層卻允許在右邊缺少連續(xù)若干個結(jié)點。滿二叉樹是完全二叉樹的一個特例。√√√263.深度為9的二叉樹中至少有個結(jié)點。2.深度為k6.2二叉樹1. 二叉樹的定義2. 二叉樹的性質(zhì)3. 二叉樹的存儲結(jié)構(gòu)276.2二叉樹1. 二叉樹的定義273.二叉樹的存儲結(jié)構(gòu)一、順序存儲結(jié)構(gòu)按二叉樹的結(jié)點“自上而下、從左至右”編號，用一組連續(xù)的存儲單元存儲。ABCDEFGHI[1][2][3][4][5][6][7][8][9]ABCGEIDHF問：順序存儲后能否復(fù)原成唯一對應(yīng)的二叉樹形狀？答：若是完全/滿二叉樹則可以做到唯一復(fù)原。而且有規(guī)律：下標(biāo)值為i的雙親，其左孩子的下標(biāo)值必為2i，其右孩子的下標(biāo)值必為2i＋1（即性質(zhì)5）例如，對應(yīng)[2]的兩個孩子必為[4]和[5],即B的左孩子必是D,右孩子必為E。T[0]一般不用283.二叉樹的存儲結(jié)構(gòu)一、順序存儲結(jié)構(gòu)A[1]ABCGEID討論：不是完全二叉樹怎么辦？答：一律轉(zhuǎn)為完全二叉樹！方法很簡單，將各層空缺處統(tǒng)統(tǒng)補上“虛結(jié)點”，其內(nèi)容為空。AB^C^^^D^…E[1][2][3][4][5][6][7][8][9].[16]ABECD缺點：①浪費空間；②插入、刪除不便

29討論：不是完全二叉樹怎么辦？答：一律轉(zhuǎn)為完全二叉樹！A[1]二、鏈?zhǔn)酱鎯Y(jié)構(gòu)

用二叉鏈表即可方便表示。dataleft_childright_childdataleft_childright_child二叉樹結(jié)點數(shù)據(jù)類型定義：typedefstructnode*tree_pointer;typedefstructnode{intdata;tree_pointerleft_child,right_child;}node;一般從根結(jié)點開始存儲。

（相應(yīng)地，訪問樹中結(jié)點時也只能從根開始）注：如果需要倒查某結(jié)點的雙親，可以再增加一個雙親域（直接前趨）指針，將二叉鏈表變成三叉鏈表。30二、鏈?zhǔn)酱鎯Y(jié)構(gòu)

用二叉鏈表即可方便表示。dataleft_例：

ABECD^AB^D^C^^E^31例：ABECD^AB^D^C^^E^31第6章樹和二叉樹（Tree&BinaryTree）6.1樹的基本概念6.2二叉樹6.3遍歷二叉樹和線索二叉樹6.4樹和森林6.5赫夫曼樹及其應(yīng)用32第6章樹和二叉樹（Tree&BinaryTre6.3遍歷二叉樹和線索二叉樹一、遍歷二叉樹（TraversingBinaryTree）二、線索二叉樹（ThreadedBinaryTree）336.3遍歷二叉樹和線索二叉樹一、遍歷二叉樹（Trave遍歷定義——指按某條搜索路線遍訪每個結(jié)點且不重復(fù)（又稱周游）。遍歷用途——它是樹結(jié)構(gòu)插入、刪除、修改、查找和排序運算的前提，是二叉樹一切運算的基礎(chǔ)和核心。

遍歷方法——牢記一種約定，對每個結(jié)點的查看都是“先左后右”。一、遍歷二叉樹（TraversingBinaryTree）34遍歷定義——指按某條搜索路線遍訪每個結(jié)點且不重復(fù)（又稱周游）遍歷規(guī)則———二叉樹由根、左子樹、右子樹構(gòu)成，定義為D、

L、RD、L、R的組合定義了六種可能的遍歷方案：LDR,LRD,DLR,DRL,RDL,RLD若限定先左后右，則有三種實現(xiàn)方案：DLRLDRLRD先(根)序遍歷中(根)序遍歷后(根)序遍歷

注：“先、中、后”的意思是指訪問的結(jié)點D是先于子樹出現(xiàn)還是后于子樹出現(xiàn)。35遍歷規(guī)則———二叉樹由根、左子樹、右子樹構(gòu)成，定義為D、L例1：先序遍歷的結(jié)果是：中序遍歷的結(jié)果是：后序遍歷的結(jié)果是：ABCDEABDECDBEACDEBCADLR—先序遍歷，即先根再左再右LDR—中序遍歷，即先左再根再右LRD—后序遍歷，即先左再右再根36例1：先序遍歷的結(jié)果是：AABD例2：用二叉樹表示算術(shù)表達式先序：-+a*b-cd/ef中序A+b*c-d-e/f后序abcd-*+ef/-37例2：用二叉樹表示算術(shù)表達式先序：37先序遍歷算法DLR(Node*root){if(root!=NULL)//非空二叉樹

{printf(“%d”,root->data);//訪問DDLR(root->lchild);//遞歸遍歷左子樹DLR(root->rchild);//遞歸遍歷右子樹}

return(0);}中序遍歷算法LDR(Node*root){if(root!=NULL){LDR(root->lchild);printf(“%d”,root->data);

LDR(root->rchild);}return(0);}后序遍歷算法LRD(Node*root){if(root!=NULL)

{LRD(root->lchild);LRD(root->rchild);printf(“%d”,root->data);}return(0);}結(jié)點數(shù)據(jù)類型自定義typedefstructNode{intdata;structNode*lchild,*rchild；}Node,*root;38先序遍歷算法中序遍歷算法后序遍歷算法結(jié)點數(shù)據(jù)類型自定義38對遍歷的分析：1.從前面的三種遍歷算法可以知道：如果將printf語句抹去，從遞歸的角度看，這三種算法是完全相同的，或者說這三種遍歷算法的訪問路徑是相同的，只是訪問結(jié)點的時機不同。從虛線的出發(fā)點到終點的路徑上，每個結(jié)點經(jīng)過3次。AFEDCBG第1次經(jīng)過時訪問＝先序遍歷第2次經(jīng)過時訪問＝中序遍歷第3次經(jīng)過時訪問＝后序遍歷2.二叉樹遍歷的時間效率和空間效率時間效率:O(n)

//每個結(jié)點只訪問一次空間效率:O(n)

//棧占用的最大輔助空間39對遍歷的分析：1.從前面的三種遍歷算法可以知道：如果將pr例：【嚴(yán)題集6.42③】編寫遞歸算法，計算二叉樹中葉子結(jié)點的數(shù)目。思路：輸出葉子結(jié)點比較簡單，用任何一種遍歷算法，凡是左右指針均空者，則為葉子，將其統(tǒng)計并打印出來。DLR(Node*root)//采用中序遍歷的遞歸算法{if(root!=NULL)//非空二叉樹條件，還可寫成if(root){if(!root->lchild&&!root->rchild)//是葉子結(jié)點則統(tǒng)計并打印{sum++;printf("%d\n",root->data);}

DLR(root->lchild);//遞歸遍歷左子樹，直到葉子處；

DLR(root->rchild);}//遞歸遍歷右子樹，直到葉子處；}return(0);}40例：【嚴(yán)題集6.42③】編寫遞歸算法，計算二叉樹中葉子結(jié)點的思路：利用前序遍歷來建樹

（結(jié)點值陸續(xù)從鍵盤輸入，用DLR為宜）statuscreateBTree(Bintree&T){scanf(“%c”,&ch);if(ch==’’)T=NULL;else{if(!(T=(BiTNode*)malloc(sizeof(BinTNode))))exit(overflow);T->data=ch;createBTpre(T->lchild);

createBTpre(T->rchild);}returnOK;}建樹——見教材P131程序41思路：利用前序遍歷來建樹（結(jié)點值陸續(xù)從鍵盤輸入，用DLR為習(xí)題討論：1.求二叉樹深度，或從x結(jié)點開始的子樹深度。

算法思路：只查各結(jié)點后繼鏈表指針，若左(右)孩子的左(右)指針非空，則層次數(shù)加1；否則函數(shù)返回。2.按層次輸出二叉樹中所有結(jié)點。

算法思路：既然要求從上到下，從左到右，則利用隊列存放各子樹結(jié)點的指針是個好辦法，而不必拘泥于遞歸算法。技巧：當(dāng)根結(jié)點入隊后，令其左、右孩子結(jié)點入隊，而左孩子出隊時又令它的左右孩子結(jié)點入隊，……由此便可產(chǎn)生按層次輸出的效果。ABCDE42習(xí)題討論：1.求二叉樹深度，或從x結(jié)點開始的子樹深度。3中序遍歷的非遞歸(迭代)算法算法思路：若不用遞歸，則要實現(xiàn)二叉樹遍歷的“嵌套”規(guī)則，必用堆棧。可直接用while語句和push/pop操作。參見教材P130-131程序。4.判別給定二叉樹是否為完全二叉樹（即順序二叉樹）。

算法思路：完全二叉樹的特點是：沒有左子樹空而右子樹單獨存在的情況(前k-1層都是滿的，且第k層左邊也滿）。技巧:按層序遍歷方式，先把所有結(jié)點（不管當(dāng)前結(jié)點是否有左右孩子）都入隊列.若為完全二叉樹,則層序遍歷時得到的肯定是一個連續(xù)的不包含空指針的序列.如果序列中出現(xiàn)了空指針，則說明不是完全二叉樹。433中序遍歷的非遞歸(迭代)算法算法思路：若不用遞歸，則要實特別討論：若已知先序/后序遍歷結(jié)果和中序遍歷結(jié)果，能否“恢復(fù)”出二叉樹？【嚴(yán)題集6.31④】

證明：由一棵二叉樹的先序序列和中序序列可唯一確定這棵二叉樹。

例：已知一棵二叉樹的中序序列和后序序列分別是BDCEAFHG和DECBHGFA，請畫出這棵二叉樹。分析：①由后序遍歷特征，根結(jié)點必在后序序列尾部（即A）；②由中序遍歷特征，根結(jié)點必在其中間，而且其左部必全部是左子樹子孫（即BDCE），其右部必全部是右子樹子孫（即FHG）；③繼而，根據(jù)后序中的DECB子樹可確定B為A的左孩子，根據(jù)HGF子串可確定F為A的右孩子；以此類推。44特別討論：若已知先序/后序遍歷結(jié)果和中序遍歷結(jié)果，能否“恢復(fù)中序遍歷：BDCEAFHG

后序遍歷：DECBHGFA（BDCE）（FHG）ABF（DCE）（HG）CDEGHABBFF45中序遍歷：BDCEAFHG

后序遍歷：DE問：用二叉鏈表法（l_child,r_child）存儲包含n個結(jié)點的二叉樹，結(jié)點的指針區(qū)域中會有多少個空指針？分析：用二叉鏈表存儲包含n個結(jié)點的二叉樹，結(jié)點必有2n個鏈域（見二叉鏈表數(shù)據(jù)類型說明）。 除根結(jié)點外，二叉樹中每一個結(jié)點有且僅有一個雙親（直接前驅(qū)），所以只會有n－1個結(jié)點的鏈域存放指針，指向非空子女結(jié)點（即直接后繼）。思考：二叉鏈表空間效率這么低，能否利用這些空閑區(qū)存放有用的信息或線索？——我們可以用它來存放當(dāng)前結(jié)點的直接前驅(qū)和后繼等線索，以加快查找速度。所以，空指針數(shù)目＝2n－(n-1)=n+1個。n+146問：用二叉鏈表法（l_child,r_child）存儲包含6.3遍歷二叉樹和線索二叉樹一、遍歷二叉樹（TraversingBinaryTree）二、線索二叉樹（ThreadedBinaryTree）476.3遍歷二叉樹和線索二叉樹一、遍歷二叉樹（Trave二、線索二叉樹（ThreadedBinaryTree）普通二叉樹只能找到結(jié)點的左右孩子信息，而該結(jié)點的直接前驅(qū)和直接后繼只能在遍歷過程中獲得。若將遍歷后對應(yīng)的有關(guān)前驅(qū)和后繼預(yù)存起來，則從第一個結(jié)點開始就能很快“順藤摸瓜”而遍歷整個樹了。兩種解決方法增加兩個域：fwd和bwd；利用空鏈域（n+1個空鏈域）存放前驅(qū)指針存放后繼指針如何預(yù)存這類信息？例如中序遍歷結(jié)果：BDCEAFHG，實際上已將二叉樹轉(zhuǎn)為線性排列，顯然具有唯一前驅(qū)和唯一后繼！可能是根、或最左（右）葉子48二、線索二叉樹（ThreadedBinaryTree）普規(guī)定：1）若結(jié)點有左子樹，則lchild指向其左孩子；否則，lchild指向其直接前驅(qū)(即線索)；2）若結(jié)點有右子樹，則rchild指向其右孩子；否則，rchild指向其直接后繼(即線索)。為了避免混淆，增加兩個標(biāo)志域，如下圖所示：lchildLTagdataRTagrchild約定:當(dāng)Tag域為0時,表示正常情況;當(dāng)Tag域為1時,表示線索情況.49規(guī)定：1）若結(jié)點有左子樹，則lchild指向其左孩子；2）有關(guān)線索二叉樹的幾個術(shù)語：線索鏈表：用上一頁結(jié)點結(jié)構(gòu)所構(gòu)成的二叉鏈表線索：指向結(jié)點前驅(qū)和后繼的指針線索二叉樹：加上線索的二叉樹（圖形式樣）線索化：對二叉樹以某種次序遍歷使其變?yōu)榫€索二叉樹的過程注：在線索化二叉樹中，并不是每個結(jié)點都能直接找到其后繼的，當(dāng)標(biāo)志為0時，則需要通過一定運算才能找到它的后繼。50有關(guān)線索二叉樹的幾個術(shù)語：線索鏈表：用上一頁結(jié)點結(jié)構(gòu)所dataAGEIDJHCFBltag0011110101rtag0001010111AGEIDJHCFB例1：帶了兩個標(biāo)志的某先序遍歷結(jié)果如表所示，請畫出對應(yīng)二叉樹。51dataAGEIDJHCFBltag0011110101rtABCGEIDHFroot懸空？懸空？解：該二叉樹中序遍歷結(jié)果為:

H,D,I,B,E,A,F,C,G所以添加線索應(yīng)當(dāng)按如下路徑進行：例2：畫出以下二叉樹對應(yīng)的中序線索二叉樹。為避免懸空態(tài)，應(yīng)增設(shè)一個頭結(jié)點52ABCGEIDHFroot懸空？懸空？解：該二叉樹中序遍歷結(jié)對應(yīng)的中序線索二叉樹存儲結(jié)構(gòu)如圖所示：00A00C00B11E11F11G00D11I11H注：此圖中序遍歷結(jié)果為:H,D,I,B,E,A,F,C,G0--root053對應(yīng)的中序線索二叉樹存儲結(jié)構(gòu)如圖所示：00A00C00B114.【2000年計算機系考研題】給定如圖所示二叉樹T，請畫出與其對應(yīng)的中序線索二叉樹。

2825405560330854解:因為中序遍歷序列是：5540256028083354對應(yīng)線索樹應(yīng)當(dāng)按此規(guī)律連線，即在原二叉樹中添加虛線。NILNIL544.【2000年計算機系考研題】給定如圖所示二叉樹T，請畫上堂課例題討論問:

設(shè)一棵完全二叉樹具有1000個結(jié)點，則它有

個葉子結(jié)點，有

個度為2的結(jié)點。先計算樹的深度k=log2n＋1=10;末層節(jié)點數(shù)=1000-(29-1)=489第9層節(jié)點數(shù)=28=256第9層葉子節(jié)點數(shù)=(256*2-489)/2=11法1：先求全部葉子數(shù)。n0＝489(末層)＋11(第9層)=500個；法2：先求2度結(jié)點數(shù)。n2=255(前8層)＋244(第9層)=499個；法3：無需求樹深k，便可快捷求出完全二叉樹的葉子數(shù)：

n0=n/2//取大于n/2的最小整數(shù)值可由二叉樹性質(zhì)5輕松證明！(編號為i的結(jié)點，其孩子編號必為2i和2i+1)①②④⑧⑤⑨③?⑦……nn已知最后一個結(jié)點編號為n，則其雙親（n/2或(n-1)/2)肯定是最后一個非葉子結(jié)點。其編號之后的全部結(jié)點都是葉子了！故，n0=n-n/2或n-(n-1)/2=n/2

55上堂課例題討論問:設(shè)一棵完全二叉樹具有1000個結(jié)點，則線索二叉樹的生成算法（算法6.6,見教材P134）目的：在依某種順序遍歷二叉樹時修改空指針，添加前驅(qū)或后繼。注解：為方便添加結(jié)點的前驅(qū)或后繼，需要設(shè)置兩個指針：p指針→當(dāng)前結(jié)點之指針；pre指針→前驅(qū)結(jié)點之指針。技巧：當(dāng)結(jié)點p的左/右域為空時，只改寫它的左域（裝入前驅(qū)pre），而其右域（后繼）留給下一結(jié)點來填寫。

或者說，當(dāng)前結(jié)點的指針p應(yīng)當(dāng)送到前驅(qū)結(jié)點的空右域中。若p->lchild＝NULL,則{p->Ltag=1;p->lchild＝pre;}

//p的前驅(qū)結(jié)點指針pre存入左空域若pre->rchild＝NULL,則{pre->Rtag＝1;pre->rchild=p;}//p存入其前驅(qū)結(jié)點pre的右空域56線索二叉樹的生成算法（算法6.6,見教材P134）目的：在3.線索二叉樹的遍歷理論上，只要找到序列中的第一個結(jié)點，然后依次訪問結(jié)點的后繼直到后繼為空時結(jié)束。但是，在線索化二叉樹中，并不是每個結(jié)點都能直接找到其后繼的，當(dāng)標(biāo)志為0時，R_child=右孩子地址指針，并非后繼！需要通過一定運算才能找到它的后繼。以中序線索二叉樹為例：對葉子結(jié)點（RTag=1），直接后繼指針就在其rchild域內(nèi)；對其他結(jié)點（RTag=0），直接后繼是其右子樹最左下的結(jié)點；（因為中序遍歷規(guī)則是LDR，先左再根再右）①②④⑧⑤⑨③⑥⑦⑩……573.線索二叉樹的遍歷理論上，只要找到序列中的第一個結(jié)點，然程序注解(非遞歸，且不用棧）：P=T->lchild;//從頭結(jié)點進入到根結(jié)點；while(p!=T)

{while(p->LTag==link)p=p->lchild;//先找到中序遍歷起點if(!visit(p->data))returnERROR;//若起點值為空則出錯告警while(p->RTag==Thread……){p=p->rchild;Visit(p->data);}//若有后繼標(biāo)志，則直接提取p->rchild中線索并訪問后繼結(jié)點；p=p->rchild;//當(dāng)前結(jié)點右域不空或已經(jīng)找好了后繼，則一律從結(jié)點的右子樹開始重復(fù){}的全部過程。}ReturnOK;線索二叉樹的中序遍歷算法（算法6.5,參見教材P134）LTag=0RTag=158程序注解(非遞歸，且不用棧）：線索二叉樹的中序遍歷算法（算法流程：returnOK;p=T->lchild;p!=Tp->LTag==0p=p->lchild;vist(p->data);p->LTag==1&&p->rchild!=Tp=p->rchild;visit(p->data);p=p->rchild;YNYNYN59算法流程：returnOK;p=T->lchild;p!=提前介紹：二叉樹的應(yīng)用平衡樹——排序樹——字典樹——判定樹——帶權(quán)樹——最優(yōu)樹——特點：左右子樹深度差≤1特點：“左小右大”由字符串構(gòu)成的二叉樹排序樹例如，12個球只稱3次分出輕重特點：路徑長度帶權(quán)值帶權(quán)路徑長度最短的樹，又稱Huffman樹，用途之一是通信中的壓縮編碼。60提前介紹：二叉樹的應(yīng)用平衡樹——特點：左右子樹深度差≤16二叉樹小結(jié)1、定義和性質(zhì)2、存儲結(jié)構(gòu)3、遍歷4、線索化：線索樹順序結(jié)構(gòu)鏈?zhǔn)浇Y(jié)構(gòu)二叉鏈表三叉鏈表先序線索樹中序線索樹后序線索樹樹二叉樹森林中序遍歷后序遍歷先序遍歷霍夫曼樹霍夫曼編碼61二叉樹小結(jié)1、定義和性質(zhì)2、存儲結(jié)構(gòu)3、遍歷4、線索化：線索第6章樹和二叉樹（Tree&BinaryTree）6.1樹的基本概念6.2二叉樹6.3遍歷二叉樹和線索二叉樹6.4樹和森林6.5赫夫曼樹及其應(yīng)用62第6章樹和二叉樹（Tree&BinaryTre6.4樹和森林1.樹和森林與二叉樹的轉(zhuǎn)換2.樹和森林的存儲方式3.樹和森林的遍歷636.4樹和森林1.樹和森林與二叉樹的轉(zhuǎn)換631.樹和森林與二叉樹的轉(zhuǎn)換轉(zhuǎn)換步驟：step1:將樹中同一結(jié)點的兄弟相連;step2:保留結(jié)點的最左孩子連線，刪除其它孩子連線；step3:將同一孩子的連線繞左孩子旋轉(zhuǎn)45度角。加線抹線旋轉(zhuǎn)討論1：樹如何轉(zhuǎn)為二叉樹？641.樹和森林與二叉樹的轉(zhuǎn)換轉(zhuǎn)換步驟：加線抹線旋轉(zhuǎn)討論1方法：加線—抹線—旋轉(zhuǎn)

abeidfhgc樹轉(zhuǎn)二叉樹舉例：abeidfhgc兄弟相連長兄為父孩子靠左根結(jié)點肯定沒有右孩子！65方法：加線—抹線—旋轉(zhuǎn)abeidfhgc樹轉(zhuǎn)二叉樹舉例：a討論2：二叉樹怎樣還原為樹？abeidfhgc要點：把所有右孩子變?yōu)樾值埽?/p>

abeidfhgc66討論2：二叉樹怎樣還原為樹？abeidfhgc要點：把所有右法一：①各森林先各自轉(zhuǎn)為二叉樹；②依次連到前一個二叉樹的右子樹上。討論3：森林如何轉(zhuǎn)為二叉樹？法二：森林直接變兄弟，再轉(zhuǎn)為二叉樹（參見教材P138圖6.17）即F={T1,T2,…,Tm}B={root,LB,RB}67法一：討論3：森林如何轉(zhuǎn)為二叉樹？法二：森林直接變兄弟，再轉(zhuǎn)ABCDEFGHJIABCDEFGHJIABCDEFGHJI森林轉(zhuǎn)二叉樹舉例：（法二）兄弟相連長兄為父孩子靠左頭根為根A68ABCDEFGHJIABCDEFGHJIABCDEFGHJI討論4：二叉樹如何還原為森林？要點：把最右邊的子樹變?yōu)樯?，其余右子樹變?yōu)樾值?/p>

ABCDEFGHJIABCDEFGHJIEFABCDGHJI即B={root,LB,RB}F={T1,T2,…,Tm}69討論4：二叉樹如何還原為森林？要點：把最右邊的子樹變?yōu)樯郑?.4樹和森林1.樹和森林與二叉樹的轉(zhuǎn)換2.樹和森林的存儲方式3.樹和森林的遍歷706.4樹和森林1.樹和森林與二叉樹的轉(zhuǎn)換702.樹和森林的存儲方式樹有三種常用存儲方式：①雙親表示法②孩子表示法③孩子兄弟表示法1、用雙親表示法來存儲思路：用一組連續(xù)空間來存儲樹的結(jié)點，同時在每個結(jié)點中附設(shè)一個指示器，指示其雙親結(jié)點在鏈表中的位置。parentsdata結(jié)點結(jié)構(gòu)dataparents1樹結(jié)構(gòu)

23n712.樹和森林的存儲方式樹有三種常用存儲方式：1、用雙親表示ABCGEIDHF缺點：求結(jié)點的孩子時需要遍歷整個結(jié)構(gòu)。01234567812233ABCDEFGHI-1001例1:雙親表示法72ABCGEIDHF缺點：求結(jié)點的孩子時需要遍歷整個結(jié)構(gòu)。01思路：將每個結(jié)點的孩子排列起來，形成一個帶表頭（裝父結(jié)點）的線性表（n個結(jié)點要設(shè)立n個鏈表）；再將n個表頭用數(shù)組存放起來，這樣就形成一個混合結(jié)構(gòu)。例如：abecdfhgdefghgfedcbah123456782、用孩子表示法來存儲bc73思路：將每個結(jié)點的孩子排列起來，形成一個帶表頭（裝父結(jié)點）的思路：用二叉鏈表來表示樹，但鏈表中的兩個指針域含義不同。左指針指向該結(jié)點的第一個孩子；右指針指向該結(jié)點的下一個兄弟結(jié)點。nextsiblingdatafirstchild3、用孩子兄弟表示法來存儲指向左孩子指向右兄弟74思路：用二叉鏈表來表示樹，但鏈表中的兩個指針域含義不同。neabecdfhgbacedfgh問：樹轉(zhuǎn)二叉樹的“連線—抹線—旋轉(zhuǎn)”如何由計算機自動實現(xiàn)？答：用“左孩子右兄弟”表示法來存儲即可。

存儲的過程就是轉(zhuǎn)換的過程！例如：75abecdfhgbacedfgh問：樹轉(zhuǎn)二叉樹的“連線—抹線6.4樹和森林1.樹和森林與二叉樹的轉(zhuǎn)換2.樹和森林的存儲方式3.樹和森林的遍歷766.4樹和森林1.樹和森林與二叉樹的轉(zhuǎn)換763、樹和森林的遍歷先序遍歷訪問根結(jié)點；依次先序遍歷根結(jié)點的每棵子樹。樹的遍歷例如：abdec先序序列：后序序列：abcdebdcea后序遍歷依次后序遍歷根結(jié)點的每棵子樹；訪問根結(jié)點。樹沒有中序遍歷（因子樹不分左右）遍歷深度遍歷（先序、中序、后序）廣度遍歷（層次）773、樹和森林的遍歷先序遍歷樹的遍歷例如：abdec先序序列：討論：若采用“先轉(zhuǎn)換，后遍歷”方式，結(jié)果是否一樣？abdec先序遍歷：后序遍歷：中序遍歷：decbaabdecabcdebdcea1.樹的先序遍歷二法相同；2.樹的后序遍歷相當(dāng)于對應(yīng)二叉樹的中序遍歷；3.樹沒有中序遍歷，因為子樹無左右之分。結(jié)論：78討論：若采用“先轉(zhuǎn)換，后遍歷”方式，結(jié)果是否一樣？abdec先序遍歷若森林為空，返回；訪問森林中第一棵樹的根結(jié)點；先序遍歷第一棵樹中根結(jié)點的子樹森林；先序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。中序遍歷若森林為空，返回；中序遍歷森林中第一棵樹的根結(jié)點的子樹森林；訪問第一棵樹的根結(jié)點；中序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。森林的遍歷ABCDEFGHJI79先序遍歷森林的遍歷ABCDEFGHJI79討論：若采用“先轉(zhuǎn)換，后遍歷”方式，結(jié)果是否相同？例如：ABCDEFGHJI先序序列：中序序列：ABCDEFGHIJBCDAFEHJIGABCDEFGHJI先序序列：中序序列：ABCDEFGHIJBCDAFEHJIG結(jié)論：森林的先序和中序遍歷在兩種方式下的結(jié)果相同。80討論：若采用“先轉(zhuǎn)換，后遍歷”方式，結(jié)果是否相同？例如：AB第6章樹和二叉樹（Tree&BinaryTree）6.1樹的基本概念6.2二叉樹6.3遍歷二叉樹和線索二叉樹6.4樹和森林6.5赫夫曼樹及其應(yīng)用81第6章樹和二叉樹（Tree&BinaryTre路徑：路徑長度：樹的路徑長度：帶權(quán)路徑長度：樹的帶權(quán)路徑長度：霍夫曼樹：由一結(jié)點到另一結(jié)點間的分支所構(gòu)成路徑上的分支數(shù)目從樹根到每一結(jié)點的路徑長度之和。結(jié)點到根的路徑長度與結(jié)點上權(quán)的乘積預(yù)備知識：若干術(shù)語debacfg樹中所有葉子結(jié)點的帶權(quán)路徑長度之和帶權(quán)路徑長度最小的樹。a→e的路徑長度＝樹長度＝2106.5Huffman樹及其應(yīng)用——最優(yōu)二叉樹（霍夫曼樹）82路徑：由一結(jié)點到另一結(jié)點間的分支所構(gòu)成路徑上的分支數(shù)Huffman樹簡介：樹的帶權(quán)路徑長度如何計算？WPL=wklkk=1nabdc7524(a)cdab2457(b)bdac7524(c)經(jīng)典之例：WPL=36WPL=46WPL=35哈夫曼樹則是：WPL最小的樹。WPL最小WeightedPathLength83Huffman樹簡介：樹的帶權(quán)路徑長度如何計算？WPL=(1)由給定的n個權(quán)值{w0,w1,w2,…,wn-1}，構(gòu)造具有n棵擴充二叉樹的森林F={T0,T1,T2,…,Tn-1}，其中每一棵擴充二叉樹Ti只有一個帶有權(quán)值wi的根結(jié)點，其左、右子樹均為空。

(2)

重復(fù)以下步驟,直到F中僅剩下一棵樹為止：

①在F中選取兩棵根結(jié)點的權(quán)值最小的擴充二叉樹,做為左、右子樹構(gòu)造一棵新的二叉樹。置新的二叉樹的根結(jié)點的權(quán)值為其左、右子樹上根結(jié)點的權(quán)值之和。②在F中刪去這兩棵二叉樹。③把新的二叉樹加入F。構(gòu)造霍夫曼樹的基本思想：構(gòu)造Huffman樹的步驟（即Huffman算法）：權(quán)值大的結(jié)點用短路徑，權(quán)值小的結(jié)點用長路徑。84(1)由給定的n個權(quán)值{w0,w1,w2,…,例1：設(shè)有4個字符d,i,a,n，出現(xiàn)的頻度分別為7,5,2,4，怎樣編碼才能使它們組成的報文在網(wǎng)絡(luò)中傳得最快？法1：等長編碼。例如用二進制編碼來實現(xiàn)。取d=00，i=01，a=10，n=11怎樣實現(xiàn)Huffman編碼？法2：不等長編碼，例如用哈夫曼編碼來實現(xiàn)。取d=0;i=10,a=110,n=111最快的編碼是哪個？是非等長的Huffman碼！先要構(gòu)造Huffman樹！85例1：設(shè)有4個字符d,i,a,n，出現(xiàn)的頻度分別為7,5,2操作要點1：對權(quán)值的合并、刪除與替換——在權(quán)值集合{7,5,2,4}中，總是合并當(dāng)前值最小的兩個權(quán)構(gòu)造Huffman樹的步驟：注：方框表示外結(jié)點（葉子，字符對應(yīng)的權(quán)值），圓框表示內(nèi)結(jié)點（合并后的權(quán)值）。86操作要點1：對權(quán)值的合并、刪除與替換構(gòu)造Huffman樹的步操作要點2：按左0右1對Huffman樹的所有分支編號！dain111000Huffman編碼結(jié)果：d=0,i=10,a=110,n=111WPL=1×7＋2×5+3*(2+4)=35特點：每一碼都不是另一碼的前綴，絕不會錯譯!稱為前綴碼——將Huffman樹與Huffman編碼掛鉤87操作要點2：按左0右1對Huffman樹的所有分支編號！da例2（嚴(yán)題集6.26③）：假設(shè)用于通信的電文僅由8個字母{a,b,c,d,e,f,g,h}構(gòu)成，它們在電文中出現(xiàn)的概率分別為{0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10}，試為這8個字母設(shè)計哈夫曼編碼。如果用0～7的二進制編碼方案又如何？霍夫曼編碼的基本思想是：概率大的字符用短碼，概率小的用長碼。由于霍夫曼樹的WPL最小，說明編碼所需要的比特數(shù)最少。這種編碼已廣泛應(yīng)用于網(wǎng)絡(luò)通信中。解：先將概率放大100倍，以方便構(gòu)造哈夫曼樹。

權(quán)值集合w={7,19,2,6,32,3,21,10}，按哈夫曼樹構(gòu)造規(guī)則（合并、刪除、替換），可得到哈夫曼樹。88例2（嚴(yán)題集6.26③）：假設(shè)用于通信的電文僅由8個字母{w4={19,21,28,32}為清晰起見，重新排序為:

w={2,3,6,7,10,19,21,32}2356w1={5,6,7,10,19,21,32}w2={7,10,11,19,21,32}w3={11,17,19,21,32}111071728211940w5={28,32,40}3260w6={40,60}w7={100}100bcadegfh哈夫曼樹××××××××××××××89w4={19,21,28,32}為清晰起見，重新排序為對應(yīng)的哈夫曼編碼（左0右1）：23561110732172821194060100bcadegfh00000111111100符編碼頻率a0.07b0.19c0.02d0.06e0.32f0.03g0.21h0.10符編碼頻率a0.07b0.19c0.02d0.06e0.32f0.03g0.21h0.10Huffman碼的WPL＝2(0.19+0.32+0.21)+4(0.07+0.06+0.10)+5(0.02+0.03)

=1.44+0.92+0.25=2.61

WPL＝3(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=31100001111011101011111011101000001010011100101110111二進制碼90對應(yīng)的哈夫曼編碼（左0右1）：235611107321728上機練習(xí)：

設(shè)字符集為26個英文字母，其出現(xiàn)頻度如下表所示。51481156357203251頻度zyxwvut字符11611882380頻度p21fq15gr47hsonmlkj字符5710332221364186頻度iedcba空格字符先建哈夫曼樹，再利用此樹對報文“Thisprogramismyfavorite”進行編碼和譯碼。91上機練習(xí)：

設(shè)字符集為26個英文字母，其出現(xiàn)頻度如下表所示。提示1：霍夫曼樹中各結(jié)點的結(jié)構(gòu)可以定義為如下5個分量：charweightparentlchildRchild將整個霍夫曼樹的結(jié)點存儲在一個數(shù)組中：HT[1..n];將結(jié)點的編碼存儲在HC[1..n]中。提示3：霍夫曼樹如何構(gòu)造？構(gòu)造好之后又如何求得各結(jié)點對應(yīng)的霍夫曼編碼？——算法參見教材P147。提示2：霍夫曼樹的存儲結(jié)構(gòu)可采用順序存儲結(jié)構(gòu)：92提示1：霍夫曼樹中各結(jié)點的結(jié)構(gòu)可以定義為如下5個分量：cha小結(jié)：哈夫曼樹及其應(yīng)用1.Huffman算法的思路：——權(quán)值大的結(jié)點用短路徑，權(quán)值小的結(jié)點用長路徑。2.構(gòu)造Huffman樹的步驟：對權(quán)值的合并、刪除與替換3.Huffman編碼規(guī)則：左“0”右“1”，是一種前綴碼也稱為最小冗余編碼、緊致碼，等等，它是數(shù)據(jù)壓縮學(xué)的基礎(chǔ)。補充1：構(gòu)造Huffman樹的過程描述補充2：對Huffman編碼器程序的解釋93小結(jié)：哈夫曼樹及其應(yīng)用1.Huffman算法的思路：2.構(gòu)造怎樣生成Huffman樹？步驟如下：(1)由給定的n個權(quán)值{w1,w2,…,wn}構(gòu)成n棵二叉樹的集合（即森林）F={T1,T2,…,Tn

}，其中每棵二叉樹Ti中只有一個帶權(quán)為wi的根結(jié)點，其左右子樹均空。(2)

在F中選取兩棵根結(jié)點的權(quán)值最小的樹做為左右子樹構(gòu)造一棵新的二叉樹，且置新的二叉樹的根結(jié)點的權(quán)值為其左右子樹上根結(jié)點的權(quán)值之和。(3)在F中刪去這兩棵樹，同時將新得到的二叉樹加入F中。(4)重復(fù)(2)和(3),直到F只含一棵樹為止。這棵樹便是赫夫曼樹。94怎樣生成Huffman樹？步驟如下：(1)由給定的n本章小結(jié)1、定義和性質(zhì)2、存儲結(jié)構(gòu)3、遍歷4、線索化：線索樹順序結(jié)構(gòu)鏈?zhǔn)浇Y(jié)構(gòu)二叉鏈表三叉鏈表先序線索樹中序線索樹后序線索樹樹二叉樹森林先序遍歷后序遍歷遍歷存儲結(jié)構(gòu)遍歷雙親表示孩子表示孩子兄弟先序遍歷后序遍歷中序遍歷后序遍歷先序遍歷霍夫曼樹霍夫曼編碼95本章小結(jié)1、定義和性質(zhì)2、存儲結(jié)構(gòu)3、遍歷4、線索化：線索樹數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容96數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容1第6章樹和二叉樹（Tree&BinaryTree）6.1

樹的基本概念6.2二叉樹6.3遍歷二叉樹和線索二叉樹6.4樹和森林6.5赫夫曼樹及其應(yīng)用97第6章樹和二叉樹（Tree&BinaryTre6.1樹的基本概念1. 樹的定義2. 若干術(shù)語3. 邏輯結(jié)構(gòu)4. 存儲結(jié)構(gòu)5. 樹的運算986.1樹的基本概念1. 樹的定義31.樹的定義注1：過去許多書籍中都定義樹為n≥1，曾經(jīng)有“空樹不是樹”的說法，但現(xiàn)在樹的定義已修改。注2：樹的定義具有遞歸性，即樹中還有樹。由一個或多個(n≥0)結(jié)點組成的有限集合T，有且僅有一個結(jié)點稱為根（root），當(dāng)n>1時，其余的結(jié)點分為m(m≥0)個互不相交的有限集合T1,T2，…，Tm。每個集合本身又是棵樹，被稱作這個根的子樹。991.樹的定義注1：過去許多書籍中都定義樹為n≥1，曾樹的表示法有幾種：圖形表示法嵌套集合表示法廣義表表示法目錄表示法100樹的表示法有幾種：圖形表示法5樹的抽象數(shù)據(jù)類型定義（見教材P118-119）ADTTree{數(shù)據(jù)對象D:數(shù)據(jù)關(guān)系R:基本操作P：}ADTTree若D為空集，則稱為空樹；//允許n=0若D中僅含一個數(shù)據(jù)元素，則R為空集；其他情況下的R存在二元關(guān)系：①root唯一//關(guān)于根的說明②Dj∩Dk=Φ//關(guān)于子樹不相交的說明③……//關(guān)于子樹的子樹不相交的說明D是具有相同特性的數(shù)據(jù)元素的集合。101樹的抽象數(shù)據(jù)類型定義（見教材P118-119）ADTTr6.1樹的基本概念1. 樹的定義2. 若干術(shù)語3. 邏輯結(jié)構(gòu)4. 存儲結(jié)構(gòu)5. 樹的運算1026.1樹的基本概念1. 樹的定義72.若干術(shù)語——即上層的那個結(jié)點(直接前驅(qū))——即下層結(jié)點的子樹的根(直接后繼)——同一雙親下的同層結(jié)點（孩子之間互稱兄弟）——即雙親位于同一層的結(jié)點（但并非同一雙親）——即從根到該結(jié)點所經(jīng)分支的所有結(jié)點——即該結(jié)點下層子樹中的任一結(jié)點ABCGEIDHFJMLK根葉子森林有序樹無序樹——即根結(jié)點(沒有前驅(qū))——即終端結(jié)點(沒有后繼)——指m棵不相交的樹的集合(例如刪除A后的子樹個數(shù))雙親孩子兄弟堂兄弟祖先子孫——結(jié)點各子樹從左至右有序，不能互換（左為第一）——結(jié)點各子樹可互換位置。1032.若干術(shù)語——即上層的那個結(jié)點(直接前驅(qū))ABCG2.若干術(shù)語（續(xù)）——即樹的數(shù)據(jù)元素——結(jié)點掛接的子樹數(shù)（有幾個直接后繼就是幾度，亦稱“次數(shù)”）結(jié)點結(jié)點的度結(jié)點的層次終端結(jié)點分支結(jié)點樹的度樹的深度(或高度)ABCGEIDHFJMLK——從根到該結(jié)點的層數(shù)（根結(jié)點算第一層）——即度為0的結(jié)點，即葉子——即度不為0的結(jié)點（也稱為內(nèi)部結(jié)點）——所有結(jié)點度中的最大值（Max{各結(jié)點的度}）——指所有結(jié)點中最大的層數(shù)（Max{各結(jié)點的層次}）問：右上圖中的結(jié)點數(shù)＝；樹的度＝；樹的深度＝13341042.若干術(shù)語（續(xù)）——即樹的數(shù)據(jù)元素結(jié)點樹的度ABC6.1樹的基本概念1. 樹的定義2. 若干術(shù)語3. 邏輯結(jié)構(gòu)4. 存儲結(jié)構(gòu)5. 樹的運算1056.1樹的基本概念1. 樹的定義103.樹的邏輯結(jié)構(gòu)

(特點)：一對多（1:n），有多個直接后繼（如家譜樹、目錄樹等等），但只有一個根結(jié)點，且子樹之間互不相交。1063.樹的邏輯結(jié)構(gòu)(特點)：一對多（1:n），有多個直接6.1樹的基本概念1. 樹的定義2. 若干術(shù)語3. 邏輯結(jié)構(gòu)4. 存儲結(jié)構(gòu)5. 樹的運算1076.1樹的基本概念1. 樹的定義124.樹的存儲結(jié)構(gòu)

討論1：樹是非線性結(jié)構(gòu)，該怎樣存儲？————仍然有順序存儲、鏈?zhǔn)酱鎯Φ确绞健?/p>

1084.樹的存儲結(jié)構(gòu)討論1：樹是非線性結(jié)構(gòu)，該怎樣存儲？13討論3：樹的鏈?zhǔn)酱鎯Ψ桨笐?yīng)該怎樣制定？可規(guī)定為：從上至下、從左至右將樹的結(jié)點依次存入內(nèi)存。重大缺陷：復(fù)原困難（不能唯一復(fù)原就沒有實用價值）。討論2：樹的順序存儲方案應(yīng)該怎樣制定？可用多重鏈表：一個前趨指針，n個后繼指針。細節(jié)問題：樹中結(jié)點的結(jié)構(gòu)類型樣式該如何設(shè)計？

即應(yīng)該設(shè)計成“等長”還是“不等長”？缺點：等長結(jié)構(gòu)太浪費（每個結(jié)點的度不一定相同）；不等長結(jié)構(gòu)太復(fù)雜（要定義好多種結(jié)構(gòu)類型）。解決思路：先研究最簡單、最有規(guī)律的樹，然后設(shè)法把一般的樹轉(zhuǎn)化為簡單樹。109討論3：樹的鏈?zhǔn)酱鎯Ψ桨笐?yīng)該怎樣制定？可規(guī)定為：從上至下、從6.1樹的基本概念1. 樹的定義2. 若干術(shù)語3. 邏輯結(jié)構(gòu)4. 存儲結(jié)構(gòu)5. 樹的運算1106.1樹的基本概念1. 樹的定義155.樹的運算

要明確：1.普通樹（即多叉樹）若不轉(zhuǎn)化為二叉樹，則運算很難實現(xiàn)。2.二叉樹的運算仍然是插入、刪除、修改、查找、排序等，但這些操作必須建立在對樹結(jié)點能夠“遍歷”的基礎(chǔ)上！（遍歷——指每個結(jié)點都被訪問且僅訪問一次，不遺漏不重復(fù)）。1115.樹的運算要明確：16第6章樹和二叉樹（Tree&BinaryTree）6.1樹的基本概念6.2二叉樹6.3遍歷二叉樹和線索二叉樹6.4樹和森林6.5赫夫曼樹及其應(yīng)用112第6章樹和二叉樹（Tree&BinaryTre6.2二叉樹為何要重點研究每結(jié)點最多只有兩個“叉”的樹？二叉樹的結(jié)構(gòu)最簡單，規(guī)律性最強；可以證明，所有樹都能轉(zhuǎn)為唯一對應(yīng)的二叉樹。1. 二叉樹的定義2. 二叉樹的性質(zhì)3. 二叉樹的存儲結(jié)構(gòu)1136.2二叉樹為何要重點研究每結(jié)點最多只有兩個“叉”1.二叉樹的定義定義：是n（n≥0）個結(jié)點的有限集合，由一個根結(jié)點以及兩棵互不相交的、分別稱為左子樹和右子樹的二叉樹組成。邏輯結(jié)構(gòu)：一對二（1：2）

基本特征:①每個結(jié)點最多只有兩棵子樹（不存在度大于2的結(jié)點）；②左子樹和右子樹次序不能顛倒（有序樹）?；拘螒B(tài)：

問：具有3個結(jié)點的二叉樹可能有幾種不同形態(tài)？普通樹呢？

5種/2種1141.二叉樹的定義定義：是n（n≥0）個結(jié)點的有限集合，由一二叉樹的抽象數(shù)據(jù)類型定義（見教材P121-122）ADTBinaryTree{數(shù)據(jù)對象D:數(shù)據(jù)關(guān)系R:基本操作P：}ADTBinaryTree若D=Φ，則R=Φ；若D≠Φ，則R={H}；存在二元關(guān)系：①root唯一//關(guān)于根的說明②Dj∩Dk=Φ//關(guān)于子樹不相交的說明③……//關(guān)于根和左右子樹有唯一聯(lián)系的說明

④……

//關(guān)于左子樹和右子樹的說明D是具有相同特性的數(shù)據(jù)元素的集合。115二叉樹的抽象數(shù)據(jù)類型定義（見教材P121-122）ADTB6.2二叉樹1. 二叉樹的定義2. 二叉樹的性質(zhì)3. 二叉樹的存儲結(jié)構(gòu)1166.2二叉樹1. 二叉樹的定義212.二叉樹的性質(zhì)(3+2)討論1：第i層的結(jié)點數(shù)至多是多少？

（利用二進制性質(zhì)可輕松求出）

性質(zhì)1:在二叉樹的第i層上至多有2i-1個結(jié)點（i>0）。性質(zhì)2:深度為k的二叉樹至多有2k-1個結(jié)點（k>0）。2i-1個提問：第i層上至少有

個結(jié)點？1討論2：深度為k的二叉樹，至多有多少個結(jié)點？

（利用二進制性質(zhì)可輕松求出）2k-1提問：深度為k時至少有

個結(jié)點？k1172.二叉樹的性質(zhì)(3+2)討論1：第i層的結(jié)點數(shù)至討論3：二叉樹的葉子數(shù)和度為2的結(jié)點數(shù)之間有關(guān)系嗎？性質(zhì)3:對于任何一棵二叉樹，若2度的結(jié)點數(shù)有n2個，則葉子數(shù)（n0）必定為n2＋1（即n0=n2+1）證明：∵二叉樹中全部結(jié)點數(shù)n＝n0+n1+n2(葉子數(shù)＋1度結(jié)點數(shù)＋2度結(jié)點數(shù))又∵二叉樹中全部結(jié)點數(shù)n＝B+1

(總分支數(shù)＋根結(jié)點)（除根結(jié)點外，每個結(jié)點必有一個直接前趨，即一個分支）而總分支數(shù)B=n1+2n2(1度結(jié)點必有1個直接后繼，2度結(jié)點必有2個)三式聯(lián)立可得：n0+n1+n2=

n1+2n2+1,即n0=n2+1實際意義：葉子數(shù)＝2度結(jié)點數(shù)＋1ABCGEIDHFJ118討論3：二叉樹的葉子數(shù)和度為2的結(jié)點數(shù)之間有關(guān)系嗎？性質(zhì)3:對于兩種特殊形式的二叉樹（滿二叉樹和完全二叉樹），還特別具備以下2個性質(zhì)：性質(zhì)4:具有n個結(jié)點的完全二叉樹的深度必為log2n＋1性質(zhì)5:對完全二叉樹，若從上至下、從左至右編號，則編號為i

的結(jié)點，其左孩子編號必為2i，其右孩子編號必為2i＋1；其雙親的編號必為i/2（i＝1時為根,除外）。證明：根據(jù)性質(zhì)2，深度為k的二叉樹最多只有2k-1個結(jié)點，且完全二叉樹的定義是與同深度的滿二叉樹前面編號相同，即它的總結(jié)點數(shù)n位于k層和k-1層滿二叉樹容量之間，即2k-1-1<n≤2k-1或2k-1≤n<2k三邊同時取對數(shù)，于是有：k-1≤log2n<k因為k是整數(shù)，所以k=log2n+1x----表示不大于x的最大整數(shù)X----表示不小于x的最小整數(shù)119對于兩種特殊形式的二叉樹（滿二叉樹和完全二叉樹），還特別具備滿二叉樹：一棵深度為k且有2k-1個結(jié)點的二叉樹。

（特點：每層都“充滿”了結(jié)點）完全二叉樹：深度為k的，有n個結(jié)點的二叉樹，當(dāng)且僅當(dāng)其每一個結(jié)點都與深度為k的滿二叉樹中編號從1至n的結(jié)點一一對應(yīng)。AOBCGEKDJFIHNML深度為4的滿二叉樹深度為4的完全二叉樹ABCGEIDHFJ為何要研究這兩種特殊形式？因為它們在順序存儲方式下可以復(fù)原！

解釋：完全二叉樹的特點就是，只有最后一層葉子不滿，且全部集中在左邊。這其實是順序二叉樹的含義。120滿二叉樹：一棵深度為k且有2k-1個結(jié)點的二叉樹。

3.深度為9的二叉樹中至少有

個結(jié)點。

Ａ)２9Ｂ)２8Ｃ)９Ｄ)２9－12.深度為k的二叉樹的結(jié)點總數(shù)，最多為

個。

Ａ)２k-1Ｂ)log2kＣ)２k－１Ｄ)２k課堂練習(xí)：1.樹Ｔ中各結(jié)點的度的最大值稱為樹Ｔ的

。

Ａ)高度Ｂ)層次Ｃ)深度Ｄ)度課堂討論：滿二叉樹和完全二叉樹有什么區(qū)別？答：滿二叉樹是葉子一個也不少的樹，而完全二叉樹雖然前n-1層是滿的，但最底層卻允許在右邊缺少連續(xù)若干個結(jié)點。滿二叉樹是完全二叉樹的一個特例。√√√1213.深度為9的二叉樹中至少有個結(jié)點。2.深度為k6.2二叉樹1. 二叉樹的定義2. 二叉樹的性質(zhì)3. 二叉樹的存儲結(jié)構(gòu)1226.2二叉樹1. 二叉樹的定義273.二叉樹的存儲結(jié)構(gòu)一、順序存儲結(jié)構(gòu)按二叉樹的結(jié)點“自上而下、從左至右”編號，用一組連續(xù)的存儲單元存儲。ABCDEFGHI[1][2][3][4][5][6][7][8][9]ABCGEIDHF問：順序存儲后能否復(fù)原成唯一對應(yīng)的二叉樹形狀？答：若是完全/滿二叉樹則可以做到唯一復(fù)原。而且有規(guī)律：下標(biāo)值為i的雙親，其左孩子的下標(biāo)值必為2i，其右孩子的下標(biāo)值必為2i＋1（即性質(zhì)5）例如，對應(yīng)[2]的兩個孩子必為[4]和[5],即B的左孩子必是D,右孩子必為E。T[0]一般不用1233.二叉樹的存儲結(jié)構(gòu)一、順序存儲結(jié)構(gòu)A[1]ABCGEID討論：不是完全二叉樹怎么辦？答：一律轉(zhuǎn)為完全二叉樹！方法很簡單，將各層空缺處統(tǒng)統(tǒng)補上“虛結(jié)點”，其內(nèi)容為空。AB^C^^^D^…E[1][2][3][4][5][6][7][8][9].[16]ABECD缺點：①浪費空間；②插入、刪除不便

124討論：