5.1二叉樹及其抽象數(shù)據(jù)類型 5.2二叉樹的周游5.3二叉樹的實現(xiàn)5.4二叉樹的應用5.5樹及其抽象數(shù)據(jù)類型 5.6 樹的實現(xiàn)5.7 樹林線性結(jié)構和非線性結(jié)構。 樹形結(jié)構是以分支關系定義的層次結(jié)構，在現(xiàn)實世界中廣泛存在，在計算機領域中也有廣泛應用。 本章重點討論二叉樹的存儲結(jié)構及其各種操作，并研究樹和森林與二叉樹之間的轉(zhuǎn)換關系。 5.1.1 5.1.1 基本概念基本概念 5.1.2 5.1.2 主要性質(zhì)主要性質(zhì) 5.1.3 5.1.3 抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型二叉樹： 它是結(jié)點的有限集合，這個集合或者為空集或者由一個根及兩棵不相交的分別稱作這個根的“左子樹”和“右子樹”的二叉樹組成。 它的每一個結(jié)點至多有兩棵子樹，并且子樹有左右之分，不能隨意顛倒。5.1.1 5.1.1 基本概念基本概念二叉樹的基本形態(tài)：左子樹右子樹右子樹左子樹（1）空二叉樹（2）只有一個根結(jié)點（3）有根結(jié)點 和左子樹（4）有根結(jié)點 和右子樹（5）有根結(jié)點 和左，右子樹 父結(jié)點父結(jié)點，左（右）子結(jié)點，子結(jié)點，邊邊 若結(jié)點x是二叉樹中某一棵子樹的根結(jié)點，結(jié)點y是x的左（右）子樹的根，則稱x是y的父結(jié)點父結(jié)點；y是x的左（右）子結(jié)點子結(jié)點；有序?qū)ΨQ作從x到y(tǒng)的邊邊。例如樹t中，C是E的父結(jié)點，E是C的子結(jié)點，是從C到E的邊 兄弟結(jié)點兄弟結(jié)點具有同一父結(jié)點彼此稱作兄弟兄弟。樹t中B，C互為兄弟，D，E互為兄弟。 圖5.2二叉樹tA AB BC CD DE EF F 圖5.2二叉樹tA AB BC CD DE EF F 祖先祖先，子孫子孫若結(jié)點y在以結(jié)點x為根的一個子樹中，且yx，則稱x是y的祖先祖先，y是x的子孫子孫。例如樹t中，A是其它各結(jié)點的祖先；C是D,E,F的祖先。 路徑路徑，路徑長度路徑長度如果x是y的一個祖先，又有xx0，x1，xny，滿足xi（i0，1，n-1）為xi+1的父結(jié)點，則稱x0，x1，xn為從x到y(tǒng)的一條路徑路徑。n稱為這條路路徑的長度徑的長度。例如樹t中A，C，D，F(xiàn)是從A到F的一條路徑，其長度為3。 圖5.2二叉樹tA AB BC CD DE EF F 圖5.2二叉樹tA AB BC CD DE EF F 結(jié)點的層數(shù)結(jié)點的層數(shù)規(guī)定根的層數(shù)根的層數(shù)為0，其余結(jié)點的層數(shù)結(jié)點的層數(shù)等于其父母結(jié)點的層數(shù)加1。如t中，0層的結(jié)點是A，1層的結(jié)點有B，C，3層的結(jié)點是F。 二叉樹的高度二叉樹的高度樹中結(jié)點的最大層數(shù)稱為二叉樹的高度二叉樹的高度。 例如樹t中，樹的深度為3。 圖5.2二叉樹tA AB BC CD DE EF F 圖5.2二叉樹tA AB BC CD DE EF F 結(jié)點的度數(shù)結(jié)點的度數(shù)結(jié)點的非空子樹個數(shù)叫作結(jié)點的度數(shù)度數(shù)。例如t中A,B,C,D,E,F的度數(shù)分別為2,0,2,1,0,0 樹葉樹葉、分支結(jié)點分支結(jié)點左（右）子樹均為空的結(jié)點稱作樹葉樹葉；否則稱作分分支結(jié)點支結(jié)點。例如樹t中B，E，F(xiàn)都是樹葉，其余結(jié)點都是分支結(jié)點。 圖5.2二叉樹tA AB BC CD DE EF F 圖5.2二叉樹tA AB BC CD DE EF F 滿二叉樹滿二叉樹：如果一棵二叉樹的任何結(jié)點或者是樹葉，或者有兩棵非空子樹，則此二叉樹稱作滿二叉樹。 完全二叉樹完全二叉樹：如果一棵二叉樹只有最下面的兩層結(jié)點度數(shù)可以小于2，并且最下面一層的結(jié)點都集中在該層最左邊的若干位置上，則此二叉樹稱為完全二叉樹。完全二叉樹不一定是滿二叉樹。滿二叉樹完全二叉樹擴充二叉樹擴充二叉樹 ： 把原二叉樹的結(jié)點都變?yōu)槎葦?shù)為2的分支結(jié)點，也就是說，如果原結(jié)點的度數(shù)為2，則不變，度數(shù)為1，則增加一個分支，度數(shù)為0（樹葉）增加兩個分支。 新增加的結(jié)點用小方框表示，稱為外部結(jié)點,原來的結(jié)點稱為內(nèi)部結(jié)點。外部路徑長度E：在擴充的二叉樹里從根到每個外部結(jié)點的路徑長度之和。內(nèi)部路徑長度I：在擴充的二叉樹里從根到每個內(nèi)部結(jié)點的路徑長度之和。 性質(zhì)性質(zhì)1. 在非空二叉樹的第i層上至多有2i個結(jié)點（i0）。歸納： i=0, 結(jié)點數(shù)=1=20 . 假設對于j(0j i), 結(jié)點數(shù)至多有2j . 對于i=j+1, 結(jié)點數(shù)至多為 2* 2j=2j+1 .性質(zhì)性質(zhì)2. 深度為k的二叉樹至多有2k+1-1個結(jié)點（k 0）。 K k M= mi = 2i = 2k+1-1 i=0 i=0 20 + 21 + 22 + 2k5.1.2 5.1.2 主要性質(zhì)主要性質(zhì)性質(zhì)性質(zhì)3. 對任何一棵非空二叉樹T，如果葉結(jié)點數(shù) 為n0，度為2的結(jié)點數(shù)為n2，則n0=n2+1。 n0+n1+n2 = 所有 結(jié)點的度數(shù)和+1 = n1+ 2*n2 +1 性質(zhì)性質(zhì)4. 具有n個結(jié)點的完全二叉樹的深度k為log2n . n=20+21+22+2k-1+mk =2k-1+mk 2k-1n 2k+1-1 2k n 2k+1 k log2n k+1 k= log2n 性質(zhì)性質(zhì)5. 對于具有n個結(jié)點的完全二叉樹，如果按從上到下和從左到右的順序?qū)Χ鏄渲械乃薪Y(jié)點從0開始到n-1進行編號，則對任意的下標為i的結(jié)點，有： 1）如果i=0，則它是根結(jié)點，它沒有父結(jié)點；如果i0, 則它的父結(jié)點的下標為 (i-1)/2 ; 2）2i+1 n-1，則下標為i的結(jié)點的左子結(jié)點的下標為2i1；否則下標為i的結(jié)點無左子結(jié)點。 3）2i+2 n-1，則下標為i的結(jié)點的右子結(jié)點的下標為2i2；否則下標為i的結(jié)點無右子結(jié)點。性質(zhì)6 在滿二叉樹中，葉子結(jié)點的個數(shù)比分支結(jié)點的個數(shù)多1。 由于滿二叉樹中，分支結(jié)點度數(shù)全部為2；其他結(jié)點都是葉子結(jié)點。根據(jù)性質(zhì)3， n0=n2+1，可以得到此性質(zhì)。性質(zhì)7 在擴充二叉樹中，外部結(jié)點的個數(shù)比內(nèi)部結(jié)點的個數(shù)多1。 由于擴充二叉樹都是滿二叉樹，根據(jù)性質(zhì)6可以得到此性質(zhì)。性質(zhì)8 對任意擴充二叉樹，外部路徑長度E和內(nèi)部路徑長度I之間滿足以下關系：E = I + 2n其中，n是內(nèi)部結(jié)點的個數(shù)。證明：當n=1時，I=0, E=2, 此等式成立。 設有n個內(nèi)部結(jié)點的擴充二叉樹，下式成立。 En=In+2n (1) 對于 n+1 個內(nèi)部結(jié)點的擴充二叉樹，去掉一個 作為原來二叉樹路徑長度為K的內(nèi)部結(jié)點，內(nèi)部路徑長度變?yōu)椋?In=In+1-K (2) 外部路徑長度變?yōu)椋篍n=En+1-2(K+1)+K= En+1 -K-2 即： En+1= En+K+2 En+1= (In+2n) +K+2= (In+1-K) +2n+K+2= In+1+2(n+1) 代入（1） 代入（2）abceef5.1.3 抽象數(shù)據(jù)類型ADT BinTree isoperations BinTree createEmptyBinTree(void) 創(chuàng)建一棵空的二叉樹 BinTree consBinTree(BinTreeNode root,BinTree left,BinTree right) 返回一棵二叉樹，其根結(jié)點是root，左右二叉樹分別為left和rightint isNULL(BinTree t)判斷二叉樹t是否為空。BinTreeNode root(BinTree t)返回二叉樹t的根結(jié)點；若為空二叉樹，則返回一個特殊值。BinTreeNode parent(BinTree t,BinTreeNode p)返回結(jié)點p的父結(jié)點；當p為根時，返回一個特殊值。 BinTree leftChild (BinTree t,BinTreeNode p) 返回p結(jié)點的左子樹，當p結(jié)點沒有左子樹時， 返回一個特殊值。 BinTree rightChild (BinTree t,BinTreeNode p) 返回p結(jié)點的y右子樹，當p結(jié)點沒有右子樹時， 返回一個特殊值。end ADT BinTree5.2.1 什么是周游什么是周游二叉樹的周游二叉樹的周游(Traversing Binary Tree)： 按某條搜索路徑訪問二叉樹中的所有結(jié)點 ，使得每個結(jié)點被訪問一次且僅被訪問一次。DLR5.2.2 周游的分類深度優(yōu)先周游三種方式： 先根次序 (DLR) 中 根 序 (LDR) 后根次序 (LRD)DLR先根次序：先根次序：若二叉樹不空，則若二叉樹不空，則（1 1）訪問根結(jié)點；）訪問根結(jié)點；（2 2）先根次序周游左子樹；）先根次序周游左子樹；（3 3）先根次序周游右子樹。）先根次序周游右子樹。A AB BD DC CE EF FI IH HG G訪問訪問A A先根次序周游先根次序周游A A的左子樹的左子樹先根次序周游先根次序周游A A的右子樹的右子樹A AB BD DC CE EF FI IH HG G訪問訪問A A先根次序周游先根次序周游A A的左子樹的左子樹訪問訪問B B先根次序周游先根次序周游B B的左子樹（的左子樹（訪問訪問D D）先根次序周游先根次序周游B B的右子樹的右子樹( (空操作空操作) )先根次序周游先根次序周游A A的右子樹的右子樹訪問訪問C C先根次序周游先根次序周游C C的左子樹（的左子樹（訪問訪問E E、G G）先根次序周游先根次序周游C C的右子樹（的右子樹（訪問訪問F F、H H、I I）先序序列：先序序列：A B D C E G F H IA B D C E G F H I中根中根( (對稱對稱) )次序：次序：若二叉樹不空，則若二叉樹不空，則（1 1）中根次序周游左子樹；）中根次序周游左子樹；（2 2）訪問根結(jié)點；）訪問根結(jié)點；（3 3）中根次序周游右子樹。）中根次序周游右子樹。中根次序周游中根次序周游A A的左子樹的左子樹訪問訪問A A中根次序周游中根次序周游A A的右子樹的右子樹A AB BD DC CE EF FI IH HG GA AB BD DC CE EF FI IH HG G中根次序周游中根次序周游A A的左子樹的左子樹中根次序周游中根次序周游B B的左子樹（的左子樹（訪問訪問D D）訪問訪問B B中根次序周游中根次序周游B B的右子樹的右子樹( (空操作空操作) )訪問訪問A A中根次序周游中根次序周游A A的右子樹的右子樹中根次序周游中根次序周游C C的左子樹（的左子樹（訪問訪問E E、G G）訪問訪問C C中根次序周游中根次序周游C C的右子樹（的右子樹（訪問訪問H H、F F、I I）中序序列：中序序列：D B A E G C H F ID B A E G C H F I后根次序：后根次序：若二叉樹不空，則若二叉樹不空，則（1 1）后根次序周游左子樹；）后根次序周游左子樹；（2 2）后根次序周游右子樹；）后根次序周游右子樹；（3 3）訪問根結(jié)點。）訪問根結(jié)點。后根次序周游后根次序周游A A的左子樹的左子樹后根次序周游后根次序周游A A的右子樹的右子樹訪問訪問A AA AB BD DC CE EF FI IH HG GA AB BD DC CE EF FI IH HG G后根次序周游后根次序周游A A的左子樹的左子樹后根次序周游后根次序周游B B的左子樹（的左子樹（訪問訪問D D）后根次序周游后根次序周游B B的右子樹的右子樹( (空操作空操作) )訪問訪問B B后根次序周游后根次序周游A A的右子樹的右子樹后根次序周游后根次序周游C C的左子樹（的左子樹（訪問訪問G G、E E）后根次序周游后根次序周游C C的右子樹（的右子樹（訪問訪問H H、I I、F F）訪問訪問C C訪問訪問A A后序序列：后序序列：D B G E H I F C AD B G E H I F C Al廣度優(yōu)先周游l若二叉樹的高度為h，則從0到h層逐層如下處理：從左到右逐個訪問存在的結(jié)點。A AB BD DC CE EF FI IH HG G對右圖所示二叉樹進行廣度優(yōu)先搜索，得到：A,B,C,D,E,F,G,H,I如圖所示的二叉樹如圖所示的二叉樹先序序列為：先序序列為：A B D E H K M N C F GA B D E H K M N C F G中序序列為：中序序列為：D B H E M K N A F C GD B H E M K N A F C G后序序列為：后序序列為：D H M N K E B F G C AD H M N K E B F G C A A AB BE ED DC CH HK KN NM MG GF F5.2.3 5.2.3 一個例子一個例子如圖所示的二叉樹是表達式如圖所示的二叉樹是表達式(a-b)(a-b)(c+d)(c+d)的語法結(jié)構圖。的語法結(jié)構圖。先序序列為：先序序列為： -ab+cd-ab+cd中序序列為：中序序列為： a-ba-bc+dc+d后序序列為：后序序列為： ab-cdab-cd+ + b ba ad dc c遞歸算法先根次序中根次序后根次序非遞歸算法 *先根次序中根次序后根次序 1 2算法算法5.15.1void preOrder( BinTree t) if (t=NULL) return; visit(root(t); preOrder(leftChild(t); preOrder(rightChild(t);理解遞歸算法：理解遞歸算法：大事化小大事化小小事化了小事化了根據(jù)是數(shù)學歸納法根據(jù)是數(shù)學歸納法算法證明：算法證明：設二叉樹結(jié)點個設二叉樹結(jié)點個數(shù)為數(shù)為n，則：，則：算法算法5.15.1void preOrder( BinTree t) if (t=NULL) return; visit(root(t); preOrder(leftChild(t); preOrder(rightChild(t);算法證明：算法證明：設二叉樹結(jié)點個設二叉樹結(jié)點個數(shù)為數(shù)為n，則：，則：當當n=0時，時，t=NULL，算法，算法做空操作，算法做空操作，算法功能成立。功能成立。算法算法5.15.1void preOrder( BinTree t) if (t=NULL) return; visit(root(t); preOrder(leftChild(t); preOrder(rightChild(t);算法證明：算法證明：設二叉樹結(jié)點個設二叉樹結(jié)點個數(shù)為數(shù)為n，則：，則：當當n=0時，時，t=NULL，算法，算法做空操作，算法做空操作，算法功能成立。功能成立。假設假設ni時時, 算法算法功能成立，則當功能成立，則當n=i時：時：訪問根訪問根算法算法5.15.1void preOrder( BinTree t) if (t=NULL) return; visit(root(t); preOrder(leftChild(t); preOrder(rightChild(t);算法證明：算法證明：設二叉樹結(jié)點個設二叉樹結(jié)點個數(shù)為數(shù)為n，則：，則：當當n=0時，時，p=NULL，算法，算法做空操作，算法做空操作，算法功能成立。功能成立。假設假設ni時時, 算法算法功能成立，則當功能成立，則當n=i時：時：訪問根訪問根周游根的左子樹周游根的左子樹左子樹中結(jié)點個數(shù)左子樹中結(jié)點個數(shù)i，根據(jù)歸納假，根據(jù)歸納假設算法功能成立設算法功能成立算法算法5.15.1void preOrder( BinTree t) if (t=NULL) return; visit(root(t); preOrder(leftChild(t); preOrder(rightChild(t);算法證明：算法證明：設二叉樹結(jié)點個設二叉樹結(jié)點個數(shù)為數(shù)為n，則：，則：當當n=0時，時，p=NULL，算法，算法做空操作，算法做空操作，算法功能成立。功能成立。假設假設ni時時, 算法算法功能成立，則當功能成立，則當n=i時：時：訪問根訪問根周游根的左子樹周游根的左子樹周游根的右子樹周游根的右子樹右子樹中結(jié)點個數(shù)右子樹中結(jié)點個數(shù)i，根據(jù)歸納假，根據(jù)歸納假設算法功能成立設算法功能成立算法算法5.15.1void preOrder( BinTree t) if (t=NULL) return; visit(root(t); preOrder(leftChild(t); preOrder(rightChild(t);算法算法5.2 5.2 二叉樹中序周游的遞歸算法二叉樹中序周游的遞歸算法void inOrder(BinTree t) if (t=NULL) return; inOrder(leftChild(t); visit(root(t); inOrder(rightChild(t);算法算法5.3 5.3 二叉樹后根次序周游的遞歸算法二叉樹后根次序周游的遞歸算法void postOrder(BinTree t) if (t=NULL) return; postOrder(leftChild(t); postOrder(rightChild(t); visit(root(t);廣度優(yōu)先周游算法5.8 廣度優(yōu)先周游二叉樹void levelOrder(BinTree t) BinTree c,cc; Queue q=createEmptyQueue(); if(t=NULL) return; c=t; enqueue(q,c); while(!isEmptyQueue(q) c=frontQueue(q);dequeue(q); visit(c); cc=leftChild(c); if(cc!=NULL)enqueue(q,cc); cc=rightChild(c); if(cc!=NULL)enqueue(q,cc); 二叉樹的實現(xiàn) 5.3.1 5.3.1 順序表示順序表示 5.3.2 5.3.2 鏈接表示鏈接表示 5.3.3 5.3.3 線索二叉樹線索二叉樹* * 用一組地址連續(xù)的存儲單元按層次次序依次存儲完全二叉樹的結(jié)點。ABCGFEDHIJ A B C D E F G H I J 下標 0 1 2 3 4 5 6 7 8 9 對于一般二叉樹，則應將其每個結(jié)點與完全二叉樹上的結(jié)點相對照，存儲在一維數(shù)組的相應分量中。圖5.11 一般二叉樹及其順序表示采用順序表示，類型聲明如下： struct SeqBinTree /* 順序樹類型定義順序樹類型定義 */ int MAXNUM; int n;DataType *nodelist;；typedef struct SeqBINTree *PSeqBINTree;運算的實現(xiàn)算法5.9 返回下標為p的結(jié)點的父結(jié)點的下標int parent_seq(PSeqBinTree t,intint parent_seq(PSeqBinTree t,int p) p) if(p=t-n) return 1; if(p=t-n) return 1; return (p-1)/2; return (p-1)/2; 算法5.10 返回下標為p的結(jié)點的左子結(jié)點的下標int leftChild_seq(PSeqBinTree t,intint leftChild_seq(PSeqBinTree t,int p) p) if(p=t-n) return 1; if(p=t-n) return 1; return 2 return 2* *p+1;p+1; 算法5.11 返回下標為p的結(jié)點的右子結(jié)點的下標int rightChild_seq(PSeqBinTree t,intint rightChild_seq(PSeqBinTree t,int p) p) if(p=t-n) return 1; if(p=t-n) return 1; return 2 return 2* *(p+1);(p+1); 二叉樹的鏈接表示是指用一個鏈表來存儲一棵二叉樹，二叉樹中的每一個結(jié)點用鏈表中的一個鏈結(jié)點來存儲，最常用的鏈接表示方式是左-右指針表示法（llink-rlink表示法，也稱做二叉鏈表），這種表示法在每個鏈結(jié)點中除存儲結(jié)點本身的數(shù)據(jù)外，再設置兩個指針字段：llink和rlink，分別存放結(jié)點的左子女和右子女所在鏈結(jié)點的存儲地址，當結(jié)點的某個子女為空時，則相應的指針為空指針。 struct BinTreeNodestruct BinTreeNode; ; / /* * 二叉樹中結(jié)點二叉樹中結(jié)點 * */ /typedef struct BinTreeNodetypedef struct BinTreeNode * *PBinTreeNodePBinTreeNode; ;struct BinTreeNodestruct BinTreeNode DataTypeDataType info; info;/ /* * 數(shù)據(jù)域數(shù)據(jù)域 * */ /PBinTreeNode llinkPBinTreeNode llink; ;/ /* * 指向左子女指向左子女 * */ /PBinTreeNode rlinkPBinTreeNode rlink; ;/ /* * 指向右子女指向右子女 * */ /;typedef struct BinTreeNode typedef struct BinTreeNode * *BinTreeBinTree; ; 算法5.12 返回結(jié)點p的左子結(jié)點的地址PBinTreeNode leftChild_link(PBinTreeNodePBinTreeNode leftChild_link(PBinTreeNode p) p) if(p=NULL) return NULL; if(p=NULL) return NULL; return p-llink return p-llink; ; 算法5.13 返回結(jié)點p的右子結(jié)點的地址PBinTreeNode rightChild_link(PBinTreeNodePBinTreeNode rightChild_link(PBinTreeNode p) p) if(p=NULL) return NULL; if(p=NULL) return NULL; return p-rlink return p-rlink; ; ABDCEFIHGt A B C E F I H G D 圖5.12(a) 二叉樹的二叉鏈表表示A B D C E F I H G 圖5.12(b) 三叉鏈表表示t 周游是二叉樹各種操作的基礎，可以在周游過程中進行各種操作，如可以在周游過程中生成結(jié)點，從而建立一棵二叉樹。ABDCEFIHG 例：輸入字符序列： ABDCEGFHI建立如圖所示的二叉樹，其中，表示空結(jié)點。算法 按先根序列創(chuàng)建二叉樹ABDCEFIHG算法算法 根據(jù)先根序列創(chuàng)建二叉樹根據(jù)先根序列創(chuàng)建二叉樹intint i=0; i=0;BinTree createRest_BTree(charBinTree createRest_BTree(char * *string)string)/ /* * 遞歸創(chuàng)建從根開始的二叉樹遞歸創(chuàng)建從根開始的二叉樹 * */ / PBinTreeNode pbnode PBinTreeNode pbnode; ; char ch char ch; ; ch=stringi ch=stringi+;+; if(ch=) pbnode if(ch=) pbnode=NULL;=NULL; else else pbnode =new struct BinTreeNode pbnode =new struct BinTreeNode; ; pbnode-info=ch pbnode-info=ch; ; pbnode-llink=createRest_BTree(string pbnode-llink=createRest_BTree(string);/);/構造左子樹構造左子樹 pbnode-rlink=createRest_BTree(stringpbnode-rlink=createRest_BTree(string);/);/構造右子樹構造右子樹 return pbnode return pbnode; ; 算法算法5.1void preOrder( BinTreevoid preOrder( BinTree t) t) if (t=NULL) return; if (t=NULL) return; visit(root(t); visit(root(t); preOrder(leftChild(t preOrder(leftChild(t);); preOrder(rightChild(t preOrder(rightChild(t);); 算法算法5.1void preOrdervoid preOrder( BinTree( BinTree t) t) if (t=NULL) return; if (t=NULL) return; cout coutinfo;info; preOrder(t preOrder(t-llink-llink);); preOrder(t preOrder(t-rlink-rlink);); /輸出二叉樹輸出二叉樹void disptree1( BinTreevoid disptree1( BinTree p) p) / /先序輸出先序輸出p p為根的二叉樹為根的二叉樹 if (p=NULL) coutif (p=NULL) cout; return; return; cout coutinfo;info; disptree1(p-llink disptree1(p-llink);); disptree1(p-rlink disptree1(p-rlink);); 算法算法5.1void preOrdervoid preOrder( BinTree( BinTree t) t) if (t=NULL) return; if (t=NULL) return; cout coutinfo;info; preOrder(t preOrder(t-llink-llink);); preOrder(t preOrder(t-rlink-rlink);); void dispTree2( BinTreevoid dispTree2( BinTree t) t) / /以括號表示法以括號表示法D(L,R)D(L,R)輸出二叉樹輸出二叉樹t t if (t=NULL) return; if (t=NULL) return; cout coutinfo;info; if(t-llink!=NULL|t-rlink if(t-llink!=NULL|t-rlink!=NULL)!=NULL) coutllink coutllink); ); coutrlink);cout coutrlink);cout);); 作業(yè) ：p.166 復習題 1、2、8p.168 算法題 1補充題：1.證明算法5.2二叉樹中序周游的遞歸算二叉樹中序周游的遞歸算法的正確性。法的正確性。網(wǎng)絡課堂測試：網(wǎng)絡課堂測試：5 5 二叉樹與樹（二叉樹與樹（1 1）二叉樹的應用 5.4.1 5.4.1 堆與優(yōu)先隊列堆與優(yōu)先隊列* * 5.4.2 5.4.2 哈夫曼樹及其應用哈夫曼樹及其應用5.4.2 5.4.2 哈夫曼樹及其應用哈夫曼樹及其應用擴充二叉樹的外部路徑長度：其中：li為從根到第i個外部結(jié)點的路徑長度，m為外部結(jié)點的個數(shù) 1miiEl擴充二叉樹的帶權的外部路徑長度 其中：wi是第i個外部結(jié)點的權值，li為從根到第i個外部結(jié)點的路徑長度，m為外部結(jié)點的個數(shù)。 1mi iiWPLwl哈夫曼樹 假設有一組（無序）實數(shù)w1 , w2 , w3 , wm，現(xiàn)要構造一棵以wi（i = 1,2,，m）為權的m個外部結(jié)點的擴充的二叉樹，使得帶權的外部路徑長度WPL最小。滿足這一要求的擴充二叉樹就稱為哈夫曼樹哈夫曼樹或最優(yōu)二叉樹最優(yōu)二叉樹。l例如以下是帶有相同權值例如以下是帶有相同權值5,4,7,2,5的四棵二叉樹。的四棵二叉樹。24575(a)24575(b)27545(c)24575(d)它們的帶權路徑長度分別為：它們的帶權路徑長度分別為：(a)WPL=2 1+7 4+5 4+5 3+4 2=73(b)WPL=7 3+ 4 3+5 3+5 3+2 1=65(c)WPL=5 2+ 5 2+2 3+4 3+7 2=52(d)WPL=4 3+ 2 3+7 2+5 2+5 2=52其中其中(c)和和(d)樹的帶權路徑長度為最小。樹的帶權路徑長度為最小?？梢则炞C它們恰為最優(yōu)二叉樹?？梢则炞C它們恰為最優(yōu)二叉樹。在解某些判定問題時，利用赫夫曼樹可以得到最在解某些判定問題時，利用赫夫曼樹可以得到最佳判定算法。佳判定算法。例如，編制一個將百分制轉(zhuǎn)換成五級分制的程序。例如，編制一個將百分制轉(zhuǎn)換成五級分制的程序。通常的算法是：通常的算法是：If(a60) b=E;If(a60) b=E;else if(a70) b=D;else if(a70) b=D; else if(a80) b=C; else if(a80) b=C; else if(a90) b=B; else if(a90) b=B; else b=A else b=A；l在實際生活中，學生的成績在五個等級上的分布是不在實際生活中，學生的成績在五個等級上的分布是不均勻的。假設其分布規(guī)律如下表示：均勻的。假設其分布規(guī)律如下表示：分數(shù)分數(shù)0596069 7079 8089 90100比例數(shù)比例數(shù)0.050.150.400.300.10d60d90d80d70EDCABYYYYNNNN0.050.150.40.30.1WPL=3.15d60CBDAEYYYYNNNN0.40.30.150.050.1WPL=2.0570d 8080d 9060d 70d60d70d80CEDNNYYYYd=0)個結(jié)點結(jié)點的有限集T。當T非空時，滿足：（1）有且僅有一個特別標出的稱為根根的 結(jié)點；（2）除除根結(jié)點根結(jié)點外，其余結(jié)點可分為m（m=0） 個互不相交非空的有限集T1, T2, , Tm, 其中 每一個集合本身又是一棵樹，稱為根的子樹子樹 (Subtree)?？諛淇諛洌翰话ㄈ魏谓Y(jié)點的樹。l在樹中也可以定義父結(jié)點、子結(jié)點、路徑、路徑長度、結(jié)點的度、樹的度等概念，與前面二叉樹中定義相同。 無序樹無序樹、有序樹有序樹對子樹的次序不加區(qū)別的樹叫作無序樹無序樹。對子樹之間的次序加以區(qū)別的樹叫作有序樹有序樹。例如在圖5.24中，按無序樹的概念t和t是同一棵樹，按有序樹的概念則是不同的樹，本章討論的樹一般是有序樹。 結(jié)點的次序結(jié)點的次序 在有序樹中可以從左到右地規(guī)定結(jié)點的次序次序。按從左到右的順序，我們可以把一個結(jié)點的最左邊的子結(jié)點簡稱為最左子結(jié)點最左子結(jié)點，或直接稱為長子長子，而把長子右邊的結(jié)點稱為次子次子。例如在t中結(jié)點B是結(jié)點A的長子，結(jié)點C是結(jié)點A的次子，是結(jié)點B的兄弟。 5.5.2 抽象數(shù)據(jù)類型ADT Tree isoperations Tree createEmptyTree(void) 創(chuàng)建一顆空樹 Tree consTree(Node p, Tree t1,.,Tree ti) 以p為根，t1,.,ti為子樹創(chuàng)建一顆樹 int isNull(Tree t) 判斷樹t是否為空樹 Node root(Tree t) 返回樹t的根結(jié)點。 Node parent(Node p) 返回結(jié)點p的父結(jié)點。 Tree leftChild(Tree t) 返回樹t的長子樹。 Tree rightSibling(Tree t) 返回樹t的右兄弟樹。end ADT Tree5.5.3 5.5.3 樹的周游樹的周游周游的定義:按某一規(guī)律系統(tǒng)的訪問樹中的所有 結(jié)點，并使每個結(jié)點恰好被訪問一次。周游的方法：按深度方向和按寬度方向周游。按深度方向（以右圖為例） 先根次序 后根次序 先根次序 (1,2,3,5,8,9,6,10,4,7) （1） 訪問根結(jié)點； （2）從左到右按先根次序周游根結(jié)點的每棵子樹。 后根次序 (2,8,9,5,10,6,3,7,4,1) （1）從左到右按后根次序周游根結(jié)點的每棵子樹; （2）訪問根結(jié)點。按寬度方向周游 先訪問層數(shù)為0的結(jié)點，然后從左到右逐個訪 問層數(shù)為1的結(jié)點，依此類推，直到訪問完樹中 的全部結(jié)點。 層次序列（1，2，3，4，5，6，7，8，9，10）5.6 5.6 樹的實現(xiàn)樹的實現(xiàn)struct ParTreeNode/* 樹中結(jié)點結(jié)構 */ DataTypeinfo; /* 結(jié)點中的元素 */intparent; /* 結(jié)點的父結(jié)點位置 */;struct ParTree struct ParTreeNode nodelistMAXNUM; /* 存放樹中的結(jié)點 */ int n; /* 樹中結(jié)點的個數(shù) */; typedef struct ParTree *PParTree;5.6.1 父指針表示法用一組連續(xù)空間存儲樹的結(jié)點，并附設一個指示器指示其雙親結(jié)點的位置。結(jié)構類型如下： 優(yōu)點：a)容易找到父結(jié)點及其所有的祖先； b)能找到結(jié)點的子女和兄弟； 缺點：a)沒有表示出結(jié)點之間的左右次序； b)找結(jié)點的子女和兄弟比較費事。改進方法：按一種周游次序在數(shù)組中存放結(jié)點,。常見的一種方法是依次存放樹的先根序列，如下圖：(a) (b) 圖5.5 一棵樹的父指針表示 算法5.6 5.75.6.2 樹的子表表示法 結(jié)點表中的每一元素又包含一個子表，存放該結(jié)點的所有子結(jié)點。結(jié)點表順序存放，子表用鏈接表示。struct EdgeNode /* 子表中節(jié)點的結(jié)構 */intnodeposition;struct EdgeNode*link;struct ChiTreeNode /* 結(jié)點表中節(jié)點的結(jié)構 */DataTypeinfo;struct EdgeNode*children;子表表示的樹結(jié)構定義如下：struct ChiTree /* 樹結(jié)構 */ struct ChiTreeNode nodelistMAXNUM; introot; /* 根結(jié)點的位置 */ intn; /* 結(jié)點的個數(shù) */typedef struct ChiTree * PChiTree; 求某個結(jié)點的最左子女運算很容易實現(xiàn)，找到結(jié)點的全部子女也很容易，但求某個結(jié)點的父母和右兄弟實現(xiàn)起來比較費事。另一個缺點是：合并若干個子樹構成一個新樹時（createTree_chitree操作）也要考慮多個結(jié)點表的合并問題，由于這些結(jié)點表通常用順序方式表示，所以合并起來比較麻煩。 1 7 2 3 4 6 8 9 5 圖5.6 樹的子表表示法children 在樹的每個結(jié)點中，除信息域外，增加指向其最左子女和右兄弟的指針。struct CSNode; /* 樹中結(jié)點結(jié)構 */typedef struct CSNode *PCSNode;/ 結(jié)點的指針類型 struct CSNode /* 結(jié)點結(jié)構定義 */ DataType info;/* 結(jié)點中的元素 */PCSNode lchild; /* 結(jié)點的最左子女的指針 */PCSNode rsibling; /* 結(jié)點的右兄弟的指針 */; typedef struct CSNode *CSTree; /* 樹類型定義 */ 5.6.3 樹的長子-兄弟表示法 t a b d c e h i j f g 圖5.7 樹的長子兄弟表法樹林樹林：是m（m=0）棵互不相交的樹所組成的集合。樹林中所有的樹都是有序的，彼此稱為兄弟。 先根次序周游：首先訪問樹林中第一棵樹的根結(jié)點；然后先根次序周游根結(jié)點的所有子樹構成的樹林；最后先根周游除去第一棵樹后剩下的樹林。A, B, C, K, D, E, H, F, J, G 5.7.1 5.7.1 樹林的周游樹林的周游 后根次序周游：首先后根次序周游第一棵樹根結(jié)點的所有子樹構成的樹林；然后訪問第一棵樹的根結(jié)點；最后后根周游除去第一棵樹后剩下的樹林。 B, K, C, A, H, E, J, F, G, D 5.7.2 5.7.2 樹林的存儲表示樹林的存儲表示 父指針表示法 子表表示法 長子-兄弟表示法樹林的父結(jié)點表示方法 1 2 3 5 9 8 6 7 樹林的子表表示法 t A B D C E H J K F G 樹林的長子兄弟表示法5.7.3 5.7.3 樹林與二叉樹的轉(zhuǎn)換樹林與二叉樹的轉(zhuǎn)換 1. 樹、樹林轉(zhuǎn)換為二叉樹執(zhí)行步驟：（1）在所有相鄰的兄弟結(jié)點之間連一條線；（2）對每個非終端結(jié)點，只保留它到其最左子女的 連線，刪去它與其它子女的連線；（3）以根結(jié)點為軸心，將整棵樹進行旋轉(zhuǎn)。樹、樹林樹、樹林 二叉樹二叉樹ABCKDEFGHJ圖5.20 樹林轉(zhuǎn)換為二叉樹ABCKDEFGHJl樹樹-二叉樹二叉樹ABDCEFHG兄弟連線兄弟連線保留父母到第一個保留父母到第一個(最左最左)孩子的連線孩子的連線去除父母與其它孩子的連線去除父母與其它孩子的連線第一個孩子作為左孩子，右兄弟降為右子女第一個孩子作為左孩子，右兄弟降為右子女ABDCEFHGABDCEFHG執(zhí)行步驟：（1）若某結(jié)點是其父母的左子女，則把該結(jié)點 的右子女，右子女的右子女， ,都與 該結(jié)點的父母用線連接起來； （2）去掉原二叉樹中所有父母到右子女的連線。ABDCEKHFJG圖 5.22 二叉樹轉(zhuǎn)換為樹林ABDCEKHFJG圖 5.22 二叉樹轉(zhuǎn)換為樹林lP.166 l復習題 6、11、12、13、14l網(wǎng)絡課堂測試：網(wǎng)絡課堂測試：5 5 二叉樹與樹（二叉樹與樹（2 2）l實驗實驗4.1-4.44.1-4.4l樹、樹林、二叉樹的一些基本概念和術語；l二叉鏈表存儲結(jié)構l樹、二叉樹的周游l哈夫曼樹的構造方法及應用