工學數據結構第6章樹和二叉樹課件

數據結構課程的內容1數據結構課程的內容1第6章樹和二叉樹（Tree&BinaryTree）6.1

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

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

討論1：樹是非線性結構，該怎樣存儲？————仍然有順序存儲、鏈式存儲等方式。

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

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

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

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

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

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

④……

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

（利用二進制性質可輕松求出）

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

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

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

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

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

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

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

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

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

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

個結點。

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

個。

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

。

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

29討論：不是完全二叉樹怎么辦？答：一律轉為完全二叉樹！A[1]二、鏈式存儲結構

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

（相應地，訪問樹中結點時也只能從根開始）注：如果需要倒查某結點的雙親，可以再增加一個雙親域（直接前趨）指針，將二叉鏈表變成三叉鏈表。30二、鏈式存儲結構

用二叉鏈表即可方便表示。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赫夫曼樹及其應用32第6章樹和二叉樹（Tree&BinaryTre6.3遍歷二叉樹和線索二叉樹一、遍歷二叉樹（TraversingBinaryTree）二、線索二叉樹（ThreadedBinaryTree）336.3遍歷二叉樹和線索二叉樹一、遍歷二叉樹（Trave遍歷定義——指按某條搜索路線遍訪每個結點且不重復（又稱周游）。遍歷用途——它是樹結構插入、刪除、修改、查找和排序運算的前提，是二叉樹一切運算的基礎和核心。

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

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

注：“先、中、后”的意思是指訪問的結點D是先于子樹出現還是后于子樹出現。35遍歷規(guī)則———二叉樹由根、左子樹、右子樹構成，定義為D、L例1：先序遍歷的結果是：中序遍歷的結果是：后序遍歷的結果是：ABCDEABDECDBEACDEBCADLR—先序遍歷，即先根再左再右LDR—中序遍歷，即先左再根再右LRD—后序遍歷，即先左再右再根36例1：先序遍歷的結果是：AABD例2：用二叉樹表示算術表達式先序：-+a*b-cd/ef中序A+b*c-d-e/f后序abcd-*+ef/-37例2：用二叉樹表示算術表達式先序：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);}結點數據類型自定義typedefstructNode{intdata;structNode*lchild,*rchild；}Node,*root;38先序遍歷算法中序遍歷算法后序遍歷算法結點數據類型自定義38對遍歷的分析：1.從前面的三種遍歷算法可以知道：如果將printf語句抹去，從遞歸的角度看，這三種算法是完全相同的，或者說這三種遍歷算法的訪問路徑是相同的，只是訪問結點的時機不同。從虛線的出發(fā)點到終點的路徑上，每個結點經過3次。AFEDCBG第1次經過時訪問＝先序遍歷第2次經過時訪問＝中序遍歷第3次經過時訪問＝后序遍歷2.二叉樹遍歷的時間效率和空間效率時間效率:O(n)

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

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

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

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

（結點值陸續(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思路：利用前序遍歷來建樹（結點值陸續(xù)從鍵盤輸入，用DLR為習題討論：1.求二叉樹深度，或從x結點開始的子樹深度。

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

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

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

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

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

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

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

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

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

設一棵完全二叉樹具有1000個結點，則它有

個葉子結點，有

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

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

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

或者說，當前結點的指針p應當送到前驅結點的空右域中。若p->lchild＝NULL,則{p->Ltag=1;p->lchild＝pre;}

//p的前驅結點指針pre存入左空域若pre->rchild＝NULL,則{pre->Rtag＝1;pre->rchild=p;}//p存入其前驅結點pre的右空域56線索二叉樹的生成算法（算法6.6,見教材P134）目的：在3.線索二叉樹的遍歷理論上，只要找到序列中的第一個結點，然后依次訪問結點的后繼直到后繼為空時結束。但是，在線索化二叉樹中，并不是每個結點都能直接找到其后繼的，當標志為0時，R_child=右孩子地址指針，并非后繼！需要通過一定運算才能找到它的后繼。以中序線索二叉樹為例：對葉子結點（RTag=1），直接后繼指針就在其rchild域內；對其他結點（RTag=0），直接后繼是其右子樹最左下的結點；（因為中序遍歷規(guī)則是LDR，先左再根再右）①②④⑧⑤⑨③⑥⑦⑩……573.線索二叉樹的遍歷理論上，只要找到序列中的第一個結點，然程序注解(非遞歸，且不用棧）：P=T->lchild;//從頭結點進入到根結點；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);}//若有后繼標志，則直接提取p->rchild中線索并訪問后繼結點；p=p->rchild;//當前結點右域不空或已經找好了后繼，則一律從結點的右子樹開始重復{}的全部過程。}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ōu)樹——特點：左右子樹深度差≤1特點：“左小右大”由字符串構成的二叉樹排序樹例如，12個球只稱3次分出輕重特點：路徑長度帶權值帶權路徑長度最短的樹，又稱Huffman樹，用途之一是通信中的壓縮編碼。60提前介紹：二叉樹的應用平衡樹——特點：左右子樹深度差≤16二叉樹小結1、定義和性質2、存儲結構3、遍歷4、線索化：線索樹順序結構鏈式結構二叉鏈表三叉鏈表先序線索樹中序線索樹后序線索樹樹二叉樹森林中序遍歷后序遍歷先序遍歷霍夫曼樹霍夫曼編碼61二叉樹小結1、定義和性質2、存儲結構3、遍歷4、線索化：線索第6章樹和二叉樹（Tree&BinaryTree）6.1樹的基本概念6.2二叉樹6.3遍歷二叉樹和線索二叉樹6.4樹和森林6.5赫夫曼樹及其應用62第6章樹和二叉樹（Tree&BinaryTre6.4樹和森林1.樹和森林與二叉樹的轉換2.樹和森林的存儲方式3.樹和森林的遍歷636.4樹和森林1.樹和森林與二叉樹的轉換631.樹和森林與二叉樹的轉換轉換步驟：step1:將樹中同一結點的兄弟相連;step2:保留結點的最左孩子連線，刪除其它孩子連線；step3:將同一孩子的連線繞左孩子旋轉45度角。加線抹線旋轉討論1：樹如何轉為二叉樹？641.樹和森林與二叉樹的轉換轉換步驟：加線抹線旋轉討論1方法：加線—抹線—旋轉

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

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

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

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

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

(2)

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

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

權值集合w={7,19,2,6,32,3,21,10}，按哈夫曼樹構造規(guī)則（合并、刪除、替換），可得到哈夫曼樹。88例2（嚴題集6.26③）：假設用于通信的電文僅由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}為清晰起見，重新排序為對應的哈夫曼編碼（左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對應的哈夫曼編碼（左0右1）：235611107321728上機練習：

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

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

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

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

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

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

討論1：樹是非線性結構，該怎樣存儲？————仍然有順序存儲、鏈式存儲等方式。

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

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

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

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

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

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

④……

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

（利用二進制性質可輕松求出）

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

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

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

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

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

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

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

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

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

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

個結點。

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

個。

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

。

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

124討論：