《樹與二叉樹整》PPT課件.pptVIP

第6章 樹與二叉樹,樹 (tree) 結(jié)構(gòu)是一種多分支多層次的數(shù)據(jù)結(jié)構(gòu)，由一組結(jié)點組成。由于它呈現(xiàn)與自然界樹類似的結(jié)構(gòu)形式，所以稱之為樹。在許多算法中，常用樹型結(jié)構(gòu)描述問題的求解過程或表示求解的對策等。,樹的邏輯結(jié)構(gòu),6.1 樹,2,樹的存儲結(jié)構(gòu),樹是由 n (n0) 個結(jié)點組成的有限集。在任意一棵非空樹 T 中：, 有且僅有一個特定的稱為根 (root) 結(jié)點；, 當(dāng) n1 時，其余結(jié)點分成 m (m0) 個互不相交的有限集T1，T2，Tm，其中每一個集合本身又都是一棵樹，并且稱為根的子樹。,3,6.1.1 樹的邏輯結(jié)構(gòu),1. 樹的定義,4,2. 樹的基本操作,樹結(jié)構(gòu)中經(jīng)常會用到一些基本術(shù)語。例如：,結(jié)點,結(jié)點的度,葉結(jié)點,分支結(jié)點,樹的度,雙親及孩子,兄弟,堂兄弟,祖先,子孫,層次,樹的深度,有序樹,無序樹,森林,5,3. 樹的基本概念,6,6.1.2 樹的存儲結(jié)構(gòu),假設(shè)以一組連續(xù)空間存儲樹的結(jié)點，同時在每個結(jié)點中附設(shè)一個指示器指示其雙親結(jié)點在連續(xù)空間中的位置。,typedef struct / 雙親表示結(jié)構(gòu)定義 TNode treeMAX; / 結(jié)點數(shù)組 int nodenum; / 結(jié)點數(shù) ParentTree; / 雙親表示結(jié)構(gòu)類型名,#define Max 100 typedef struct TNode / 結(jié)點結(jié)構(gòu)定義 DataType data; / 數(shù)據(jù)域 int parent; / 雙親位置域 TNode;,1. 雙親表示法,7,樹,數(shù)組下標(biāo),0,1,2,3,4,5,6,7,8,9,雙親存儲結(jié)構(gòu),由于樹中每個結(jié)點可能有多棵子樹，則可以用多重鏈表，即每個結(jié)點有多個指針域，其中每個指針指向一棵子樹的根結(jié)點，此時，鏈表中的結(jié)點可以有如下 3 種結(jié)構(gòu)格式：,8,同構(gòu)結(jié)點格式,不同構(gòu)結(jié)點格式,單鏈表存儲結(jié)構(gòu),2. 孩子表示法,(1) 同構(gòu)結(jié)點格式。即多重鏈表中的結(jié)點是同構(gòu)的。,其中 d 為樹的度。由于樹中很多結(jié)點的度都小于 d，所以鏈表中有很多空鏈域，空間比較浪費。,9,設(shè)樹的度為 k，結(jié)點數(shù)為 n。若采用同構(gòu)結(jié)點格式，每個結(jié)點具有 k 個固定鏈域，那么共有 nk 個鏈域。由于 n 個結(jié)點要有 ( n - 1) 個枝相連，而每枝需要 1 個鏈域。因此，這棵樹的空鏈域的個樹為： n ( k 1 ) +1。,由此可知，樹的度越大，空鏈域越多。如果采用同構(gòu)結(jié)點格式將造成空間的極大浪費。,(2) 不同構(gòu)結(jié)點格式。即多重鏈表中的結(jié)點是不同構(gòu)的。,其中,種存儲結(jié)構(gòu)避免了孩子表示法存儲結(jié)構(gòu)中出現(xiàn)的空鏈域，節(jié)約存儲空間。但是由于每個結(jié)點的孩子鏈域數(shù)不同，所以在這種結(jié)構(gòu)上進(jìn)行的各種操作不易實現(xiàn)。,為結(jié)點的度，degree 域的值和,相同。這,10,(3) 單鏈表存儲結(jié)構(gòu)。即把每個結(jié)點的孩子結(jié)點排列起來，看成是一個線性表，且以單鏈表作為存儲結(jié)構(gòu)，則 n 個結(jié)點有 n 個孩子鏈表（葉子結(jié)點的孩子鏈表為空表）。而 n 個頭指針又組成一個線性表，為了便于查找，可以采用順序存儲結(jié)構(gòu)。,11,樹,0,1,2,3,4,5,6,7,8,9,根位置,12,樹的孩子兄弟表示法又稱二叉樹表示法，或二叉鏈表表示法，即以二叉鏈表作為樹的存儲結(jié)構(gòu)。鏈表中每個結(jié)點的結(jié)構(gòu)相同，都有 3 個域：數(shù)據(jù)域 data 存放樹中結(jié)點的信息；孩子域 firstchild 存放該結(jié)點的第一個孩子結(jié)點（從左算起）的地址；兄弟域 nextsibling 存放該結(jié)點的下一個兄弟結(jié)點（從左向右）的地址。,13,3. 孩子兄弟表示法,樹,14,二叉樹 (binary tree) 是另一種樹型結(jié)構(gòu)，它的特點是每個結(jié)點至多只有兩棵子樹（即二叉樹中不存在度大于 2 的結(jié)點），并且，二叉樹的子樹有左右之分，其次序不能任意顛倒。,二叉樹的邏輯結(jié)構(gòu),6.2 二叉樹,15,二叉樹的基本性質(zhì),二叉樹的存儲結(jié)構(gòu),二叉樹是一個有限的結(jié)點的集合，該集合或者為空，或者由一個根結(jié)點加上兩棵分別稱為左子樹和右子樹的、互不相交的二叉樹組成。,16,二叉樹定義是一個遞歸定義，即在二叉樹的定義中又用到二叉樹的概念。,6.2.1 二叉樹的邏輯結(jié)構(gòu),1. 二叉樹的定義,性質(zhì)1：在二叉樹的第 i 層上至多有 2i-1 個結(jié)點（i1）。,證明：利用歸納法容易證得此性質(zhì)。 i = 1 時，只有一個根結(jié)點。2i-1 = 20 = 1，命題成立。 假定對所有的 j (1ji)，命題成立，即第 j 層上至多有 2 j-1 個結(jié)點。那么，可以證明 j = i 時命題也成立。 根據(jù)歸納假設(shè)，第 i-1 層上至多有 2i-2 個結(jié)點。由于二叉樹的每個結(jié)點的度最多為 2，所以在第 i 層上最多的結(jié)點數(shù)為第 i-1 層上的 2 倍，即 22i-2 = 2i-1。,17,6.2.2 二叉樹的基本性質(zhì),性質(zhì)2：深度為 k 的二叉樹至多有 2k1 個結(jié)點（k1）。,= 2k1,18,證明： 由性質(zhì)1 可見，深度為 k 的二叉樹的最大結(jié)點數(shù)為,性質(zhì)3：對任何一棵二叉樹 T，如果其終端結(jié)點數(shù)為 n0，度為 2 的結(jié)點數(shù)為 n2，則 n0 n2 + 1。,19,證明： (1) 設(shè) n1 為二叉樹 T 中度為 1 的結(jié)點數(shù)。n 為二叉樹中總結(jié)點數(shù)。因為二叉樹中所有結(jié)點的度均小于或等于 2，則：n = n0 + n1 + n2 。 (2) 設(shè) B 為二叉樹 T 中的分支總數(shù)。 從入支的角度看，二叉樹中除了根結(jié)點外，其余結(jié)點都有一個且僅有一個入支，則：n = B + 1。 從出支的角度看，度為 1 的結(jié)點只有一個出支，度為 2 的結(jié)點有兩個出支，則：B = n1 + 2n2 故：n = n1 + 2n2 + 1；最后得到： n0 = n2 + 1。,為便于介紹下面兩個二叉樹性質(zhì)，先了解滿二叉樹 (full binary tree) 和完全二叉樹 (complete binary tree) 的概念。,20,滿二叉樹的特點是：每一層上的結(jié)點數(shù)都達(dá)到最大值；滿二叉樹中只有度為 0 和度為 2 的結(jié)點，不存在度為 1 的結(jié)點；每一個結(jié)點均有兩棵高度相同的子樹，葉子結(jié)點都在樹的最下面的同一層上。,滿二叉樹：一棵深度為 k 并且有 2k-1 個結(jié)點的二叉樹，稱之為滿二叉樹。,如果對滿二叉樹的結(jié)點進(jìn)行編號，約定編號從根結(jié)點起，自上而下，自左至右。由此可以引出完全二叉樹的定義。,完全二叉樹的特點是：二叉樹中的葉子結(jié)點只可能出現(xiàn)在二叉樹中層次最大的兩層上；最下一層的結(jié)點一定是從最左邊開始向右放的；并且若某個結(jié)點沒有左孩子，則它一定沒有右孩子。,21,完全二叉樹：一棵深度為 k 并且有 n 個結(jié)點的二叉樹，當(dāng)且僅當(dāng)其每一個結(jié)點都與深度為 k 的滿二叉樹中編號從 1 至 n 的結(jié)點一一對應(yīng)時，稱之為完全二叉樹。,性質(zhì)4：具有 n 個結(jié)點的完全二叉樹的深度為 log2n + 1 （ x 表示不大于 x 的最大整數(shù)）,22,證明： 設(shè)所求完全二叉樹深度為 k，則它的前 k-1 層可視為深度為 k-1 的滿二叉樹，共有 2k-1-1 個結(jié)點，故該完全二叉樹的總結(jié)點數(shù) n 一定滿足式子：n2k-1-1。 根據(jù)性質(zhì) 2，可以確定：n 2k-1 由此得到：2k-1-1n2k-1 或 2k-1 n2k 等價關(guān)系：k-1log2nk 因為 k 是整數(shù)，所以 k-1 = log2n，即 k = log2n + 1,性質(zhì)5：如果對一棵有 n 個結(jié)點的完全二叉樹（此二叉樹的深度為 log2n +1）的結(jié)點按照層次編號（從第 1 層到第 log2n +1 層，每層從左到右），那么對任一結(jié)點 i（1 i n），有,23,(1) 若 i = 1，則結(jié)點 i 是二叉樹的根，沒有雙親結(jié)點；若 i 1，則其雙親結(jié)點是結(jié)點 i / 2。,(2) 若 2i n，則結(jié)點 i 沒有左孩子（結(jié)點 i 為葉子結(jié)點）；否則其左孩子是結(jié)點 2i。,(3) 若 2i + 1n，則結(jié)點 i 沒有右孩子；否則其右孩子是結(jié)點 2i + 1。,二叉樹和其他數(shù)據(jù)結(jié)構(gòu)一樣也分順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)；而鏈?zhǔn)酱鎯Y(jié)構(gòu)又分二叉鏈表存儲結(jié)構(gòu)和三叉鏈表存儲結(jié)構(gòu)。,24,6.2.3 二叉樹的存儲結(jié)構(gòu),二叉樹的順序存儲結(jié)構(gòu)就是用一組地址連續(xù)的存儲單元來存放一棵二叉樹的所有結(jié)點元素。,# define MAX_TREE_SIZE 100 / 二叉樹的最大結(jié)點數(shù) typedef DataType SqBiTreeMAX_TREE_SIZE; / 定義順序樹類型SqBiTree，約定0 號單元存儲根結(jié)點 SqBiTree bt; /定義了一棵二叉樹bt,25,1. 順序存儲結(jié)構(gòu),順序存儲結(jié)構(gòu)僅適用于完全二叉樹。如果存儲一般二叉樹，則會造成存儲空間的浪費，這時就需要使用二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)。 二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)主要是設(shè)計結(jié)點結(jié)構(gòu)。根據(jù)結(jié)點結(jié)構(gòu)的不同，又可以分為二叉鏈表存儲結(jié)構(gòu)和三叉鏈表存儲結(jié)構(gòu)。,26,2. 鏈?zhǔn)酱鎯Y(jié)構(gòu),(1) 二叉鏈表存儲結(jié)構(gòu),tyepdef struct Node DataType data; structNode *lchild, *rchild; / 左右孩子指針 BiTNode *BiTree; / 二叉鏈表存儲結(jié)構(gòu)類型名,左孩子指針,右孩子指針,數(shù)據(jù)域,27,二叉樹的結(jié)點由一個數(shù)據(jù)元素和分別指向其左、右子樹的兩個分支構(gòu)成，則表示二叉樹的鏈表中的結(jié)點包括三個域：數(shù)據(jù)域、左指針域和右指針域，稱為二叉鏈表存儲結(jié)構(gòu)。,(2) 三叉鏈表存儲結(jié)構(gòu),tyepdef struct TriTNode TElemType data; struct TriTNode *lchild, *rchild, *parent; TriTNode *TriTree; / 三叉鏈表存儲結(jié)構(gòu)類型名,左孩子指針,右孩子指針,數(shù)據(jù)域,雙親指針,28,為方便找到結(jié)點雙親，在二叉鏈表結(jié)構(gòu)中增加一個指向其雙親結(jié)點的指針域，則表示二叉樹的鏈表中的結(jié)點包括四個域：數(shù)據(jù)域、左指針域、右指針域和雙親指針域，稱為三叉鏈表存儲結(jié)構(gòu)。,在二叉樹的很多應(yīng)用中，常要求在二叉樹中查找某些指定的結(jié)點或?qū)Χ鏄渲腥拷Y(jié)點逐一進(jìn)行某種操作，這就需要依次訪問二叉樹中的結(jié)點，即遍歷二叉樹。,6.4 遍歷二叉樹,29,遍歷二叉樹 (traversing binary tree) 是指按某種規(guī)律巡查二叉樹，對樹中的每個結(jié)點訪問一次且僅訪問一次。在訪問每個結(jié)點時可對結(jié)點進(jìn)行各種操作，如：輸出結(jié)點的信息、對結(jié)點進(jìn)行計數(shù)、修改結(jié)點的信息等。,遍歷二叉樹的操作定義,30,遍歷二叉樹的遞歸算法,遍歷二叉樹的非遞歸算法,建立二叉樹的算法,二叉樹的定義是遞歸的，一棵非空的二叉樹由三個基本單元組成：根結(jié)點、左子樹和右子樹。因此，若能依次遍歷這三部分，便是遍歷了整個二叉樹。 設(shè)以 L、D、R 分別表示遍歷左子樹、訪問根結(jié)點和遍歷右子樹，則可能有 DLR、LDR、LRD、DRL、RDL、RLD 六種遍歷二叉樹的方案。如果限定先左子樹后右子樹，則只有前三種方案，分別稱之為先根（序）遍歷 DLR、中根（序）遍歷 LDR 和后根（序）遍歷 LRD。遍歷左子樹和右子樹的規(guī)律和遍歷整個二叉樹的規(guī)律相同，因而這三種遍歷都具有遞歸性。,31,6.3.1 遍歷二叉樹的操作定義,(1) 先根（序）DLR 遍歷二叉樹的操作定義,若二叉樹為空，則空操作；否則： 訪問根結(jié)點； 先序遍歷左子樹； 先序遍歷右子樹。,32,(2) 中根（序）LDR 遍歷二叉樹的操作定義,若二叉樹為空，則空操作；否則： 中序遍歷左子樹； 訪問根結(jié)點； 中序遍歷右子樹。,33,(3) 后根（序）LRD 遍歷二叉樹的操作定義,若二叉樹為空，則空操作；否則： 后序遍歷左子樹； 后序遍歷右子樹； 訪問根結(jié)點。,34,遍歷二叉樹可以根據(jù)二叉樹的遞歸定義寫出遞歸算法。分為：,先序遍歷二叉樹的遞歸算法,35,中序遍歷二叉樹的遞歸算法,后序遍歷二叉樹的遞歸算法,6.3.2 遍歷二叉樹的遞歸算法,1. 先序遍歷二叉樹的遞歸算法,void PreOrder (BiTree root) /* 采用二叉鏈表存儲結(jié)構(gòu)，root為指向二叉樹根結(jié)點指針，Visit 是對數(shù)據(jù)元素操作的應(yīng)用函數(shù)，先序遍歷二叉樹root的遞歸算法，對每個數(shù)據(jù)元素調(diào)用函數(shù) Visit 。*/ ,if (root!=NULL) / 若root不為空,36,Visit(root-data) / 訪問根結(jié)點 PreOrder (root-LChild) / 先序遍歷左子樹 PreOrder (root-RChild) /先序遍歷右子樹 / PreOrder,2. 中序遍歷二叉樹的遞歸算法,void InOrder (BiTree root) /* 采用二叉鏈表存儲結(jié)構(gòu)，root為指向二叉樹(或某一子樹)根結(jié)點指針，Visit 是對數(shù)據(jù)元素操作的應(yīng)用函數(shù)， 中序遍歷二叉樹root的遞歸算法，對每個數(shù)據(jù)元素調(diào)用函數(shù) Visit 。*/ ,if (root!=NULL) / 若root不為空,37,InOrder (root-LChild) / 中序遍歷左子樹 Visit(root-data) / 訪問根結(jié)點 InOrder (root-RChild) /中序遍歷右子樹 / InOrder,3. 后序遍歷二叉樹的遞歸算法,38,void PostOrder (BiTree root) /* 采用二叉鏈表存儲結(jié)構(gòu)，root為指向二叉樹根結(jié)點指針，Visit 是對數(shù)據(jù)元素操作的應(yīng)用函數(shù)，后序遍歷二叉樹root的遞歸算法，對每個數(shù)據(jù)元素調(diào)用函數(shù) Visit 。*/ ,if (root!=NULL) / 若root不為空,PostOrder (root-LChild) / 后序遍歷左子樹 PostOrder (root-RChild) /后序遍歷右子樹 Visit(root-data) / 訪問根結(jié)點 / PostOrder,int Visit ( DataType e ) printf (e); / 輸出數(shù)據(jù)元素 e 的值 return OK; / PrintElement,對每個數(shù)據(jù)元素進(jìn)行訪問的時候，可以使用調(diào)用函數(shù) Visit，最簡單的 Visit 函數(shù)是：,39,在有些算法語言中是不允許遞歸調(diào)用的，所以也有必要討論遍歷二叉樹的非遞歸算法。非遞歸的程序中要用棧來保存遍歷經(jīng)過的路徑，才能訪問到二叉樹中的每一個結(jié)點。分為：,先序遍歷二叉樹的非遞歸算法,40,中序遍歷二叉樹的非遞歸算法,后序遍歷二叉樹的非遞歸算法,6.3.3 遍歷二叉樹的非遞歸算法,1. 先序遍歷二叉樹的非遞歸算法,(1) 算法思想,使用一個棧 S，用以存放已經(jīng)訪問過的根結(jié)點指針，以備在訪問該結(jié)點的左子樹之后再訪問其右子樹。顯然，開始時棧應(yīng)該為空。 算法開始時，先將棧 S 初始化，然后令 p 指向二叉樹的根結(jié)點，即 p = root。 如果指向根結(jié)點的指針非空或者棧非空，則做如下操作：,41,如果指向根結(jié)點的指針非空，則訪問根結(jié)點；然后將根結(jié)點指針進(jìn)棧；最后將指針指向該結(jié)點的左子樹根結(jié)點，繼續(xù)遍歷；,42,如果指向根結(jié)點的指針為空，則應(yīng)該退至上一層（即將棧頂存放的指針出棧）。有兩種情況：,當(dāng)指針為空并且棧為空時，遍歷結(jié)束。, 若從左子樹返回，則應(yīng)將指針指向當(dāng)前層（即棧頂指針?biāo)福└Y(jié)點的右子樹根結(jié)點， 繼續(xù)遍歷。 若從右子樹返回，則表明當(dāng)前層遍歷結(jié)束，應(yīng)該繼續(xù)退棧。從另一個角度看，這意味著遍歷右子樹時不再需要保存當(dāng)前層的根指針，可以直接修改指針。,PreOrder 非遞歸算法的時間復(fù)雜度,樹中非空鏈域的個數(shù)為 2n2+n1，再由二叉樹的性質(zhì) 3 (n0 = n2+1)，可知： 2n2 + n1 = n2 + n2 + n1 = n0 + n1 + n2 - 1 = n - 1 所以，遍歷每個結(jié)點的時間復(fù)雜度為 O(n)。,(2) 算法分析,43,假定二叉樹 T 有 n 個結(jié)點，算法中對每個結(jié)點都要入棧和出棧一次。因此，入棧和出棧都要執(zhí)行 n 次。此外，只有當(dāng) p 為非空時，才對當(dāng)前在棧頂?shù)慕Y(jié)點信息進(jìn)行訪問。,PreOrder非遞歸算法所需附加空間,44,算法所需要的附加空間為棧（用以存放已經(jīng)訪問的根結(jié)點）的容量。棧的容量與樹的深度有關(guān)，如果每個結(jié)點需要 1 個存儲單位，則遍歷深度為 k 的二叉樹，棧需要 k 個存儲單位，即所需要的空間為 O(k)。,2. 中序遍歷二叉樹的非遞歸算法, 算法思想,45,使用一個棧 S，用以存放待訪問的根結(jié)點指針，以備在訪問該結(jié)點的左子樹之后再訪問該結(jié)點及其右子樹。顯然，開始時棧應(yīng)該為空。 算法開始時，先將棧 S 初始化，然后令 p 指向二叉樹的根結(jié)點，即 p = root。 如果指向根結(jié)點的指針非空或者棧 S 非空，則做如下操作：,如果指向根結(jié)點指針非空，則將該指針進(jìn)棧，然后將指針指向該結(jié)點左子樹根結(jié)點，繼續(xù)遍歷。,46,如果指向根結(jié)點指針為空，則應(yīng)退至上一層（即將棧頂存放的指針出棧）：,當(dāng)指針為空并且棧為空時，遍歷結(jié)束。, 若從左子樹返回，則應(yīng)訪問當(dāng)前層（即棧頂指針?biāo)傅模└Y(jié)點，然后將指針指向該結(jié)點的右子樹根結(jié)點，繼續(xù)遍歷； 若從右子樹返回，則表明當(dāng)前層遍歷結(jié)束，應(yīng)繼續(xù)退棧。從另一個角度看，這意味著遍歷右子樹時不再需要保存當(dāng)前層的根指針，可直接修改指針。,(2)算法描述,void InOrder(BiTree root) /*采用二叉鏈表存儲結(jié)構(gòu)，Visit 是對元素操作的應(yīng)用函數(shù)。 中序遍歷二叉樹T 的非遞歸算法，對每個元素調(diào)用函數(shù) Visit*/ InitStack ( / 指針指向右子樹根結(jié)點，遍歷右子樹 / else / while / InOrder,樹中空鏈域的個數(shù)為 2n0+n1，再由二叉樹的性質(zhì)3 (n0 = n2+1)，可知： 2n0 + n1 = n0 + n0 + n1 = n0 + n1 + n2 + 1 = n + 1 所以，遍歷每個結(jié)點的時間復(fù)雜度為 O(n)。,(3) 算法分析,48,InOrder 非遞歸算法的時間復(fù)雜度,假定二叉樹 root 有 n 個結(jié)點，算法中對每個結(jié)點都要入棧和出棧一次。因此，入棧和出棧都要執(zhí)行 n 次。此外，只有當(dāng) p 為空時，才對當(dāng)前在棧頂?shù)慕Y(jié)點信息進(jìn)行訪問。,InOrder 非遞歸算法所需附加空間,49,算法所需附加空間為棧（用以存放待訪問的根結(jié)點）的容量。棧的容量與樹的深度有關(guān)，如果每個結(jié)點需要 1 個存儲單位，則遍歷深度為 k 的二叉樹，棧需要 k 個存儲單位，即所需要的空間為 O(k)。,3. 后序遍歷二叉樹的非遞歸算法,50,(1) 算法思想,在后序遍歷中，當(dāng)搜索指針指向某一結(jié)點時，不能馬上進(jìn)行訪問，而先要遍歷其左子樹，所以要將此結(jié)點入棧保存。當(dāng)遍歷完它的左子樹后，退棧再次得到該結(jié)點時，還不能進(jìn)行訪問，還需要遍歷其右子樹。所以，需要再次將此結(jié)點入棧保存。,為了區(qū)別同一結(jié)點的兩次入棧，在此算法中，設(shè)計一個棧 S 存放 SElemType 類型的數(shù)據(jù)，其結(jié)構(gòu)為：,typedef struct SElemType / 順序棧中數(shù)據(jù)的結(jié)構(gòu)定義 BiTNode *p; / 二叉樹的結(jié)點指針 int tag; / 標(biāo)志變量 / 當(dāng) tag = 0 時，表示該結(jié)點第一次入棧，暫不訪問； / 當(dāng) tag = 1 時，表示該結(jié)點第二次入棧，可以訪問。 SElemType;,算法開始時，先將棧 S 初始化，然后令 p 指向二叉樹的根結(jié)點，即 p = root。,51,如果指向根結(jié)點指針不為空，先將 tag 置零；再將 tag 和根結(jié)點一道送入棧中；然后將指針指向該結(jié)點的左子樹根結(jié)點；繼續(xù)遍歷。,52,如果指向根結(jié)點指針為空，則應(yīng)退至上一層，即將棧頂存放的數(shù)據(jù)項（SElemType類型，包括二叉樹結(jié)點指針和標(biāo)志變量）出棧：,直到棧為空并且指針為空時，遍歷結(jié)束。, 若 tag 為 0，則改變 tag 值，將 tag 置 1；再把 tag 和彈出的結(jié)點重新裝入棧中；然后將指針指向該結(jié)點的右子樹根結(jié)點；繼續(xù)遍歷。 若 tag = 1，則訪問彈出的結(jié)點，并且將彈出指針置為空。,void PostOrder (BiTree root) /*采用二叉鏈表存儲結(jié)構(gòu)，Visit 是對元素操作的應(yīng)用函數(shù)。 后序遍歷二叉樹 T 的非遞歸算法，對每個元素調(diào)用函數(shù)Visit*/ SElemtype Data;,InitStack (S); Data.p = root; / 使用棧 S 存放待訪問的根結(jié)點。令 Data.p 指向二叉樹根結(jié)點,do if ( Data.p ) / 若 Data.p 非空 Data.tag = 0; / 將 Data.tag 置零 Push ( S, Data ); / 將 Data.tag 和 Data.p 一道送入棧 S Data.p = Data.p-lchild; / 將指針指向左子樹根結(jié)點，遍歷左子樹 ,(2) 算法描述,53,else / 如果 Data.p 為空 Pop ( S, Data ); / 將 Data.tag 和 Data.p 一道彈出,if ( Data.tag = 0 ) / 如果標(biāo)志變量 Data.tag 為零 Data.tag = 1; / 將 Data.tag 置為 1 Push ( S, Data ) / 將 Data.tag 和 Data.p 一道送入棧 S 中 Data.p = Data.p-rchild; / 將指針指向右子樹根結(jié)點，遍歷右子樹 ,54,else / 如果標(biāo)志變量 Data.tag 為 1 Visit ( Data.p ); / 訪問 Data.p 指向的結(jié)點 Data.p = NULL; / 將 Data.p 指針置空 while ( ! Data.p ,return OK; / PostOrderTraverse,(3) 算法分析,55,PostOrder 非遞歸算法的時間復(fù)雜度,假定二叉樹 root 有 n 個結(jié)點，算法中對每個結(jié)點都要進(jìn)行兩次入棧和出棧。因此，入棧和出棧都要執(zhí)行 2n 次，則入棧、出棧的時間復(fù)雜度為 O(n)。 此外，每當(dāng) Data.p 為空時，就彈出棧頂?shù)臄?shù)據(jù)項 Data，然后根據(jù) Data.tag 的值是否為零，或訪問剛彈出的結(jié)點，或使數(shù)據(jù)項重新進(jìn)棧。重新入棧的時間已經(jīng)算在入棧、出棧所需時間之內(nèi)，訪問結(jié)點的時間顯然為 O(n)。所以，算法總的時間復(fù)雜度為 O(n)+O(n)，或者為 O(n)。,PostOrder 非遞歸算法所需附加空間,56,算法所需要的附加空間比前面兩個算法多。由于 Data.tag 變量用 1 位二進(jìn)制就可以表示，因此，所需要的空間仍然為 O(k)，其中 k 為二叉樹的深度。,后序遍歷方法二算法思想,57,從當(dāng)前結(jié)點開始,進(jìn)棧并走左子樹,直到左子樹為空, 否則，走右子樹。 直到棧為空并且指針為空時，遍歷結(jié)束。,如果棧頂結(jié)點的右子樹為空,或棧頂結(jié)點的右子樹為剛訪問過的結(jié)點,則退棧并訪問，然后將當(dāng)前結(jié)點指針置為空。,遍歷二叉樹是二叉樹各種操作的基礎(chǔ)，可以在遍歷的過程中對結(jié)點進(jìn)行各種操作，比如：對于一棵已知樹可以求結(jié)點的雙親，求結(jié)點的孩子結(jié)點，判定結(jié)點所在的層次等；反之，給定一棵二叉樹的遍歷序列結(jié)點，可建立二叉樹的存儲結(jié)構(gòu)。,58,6.3.4 建立二叉樹的算法,例如，如果按照先序序列建立二叉樹的二叉鏈表結(jié)構(gòu)，對下圖所示二叉樹，可以按照“擴(kuò)展先序遍歷順序”讀入字符，即可以建立相應(yīng)的二叉鏈表。,A B C D E G F,59,void CreateBiTree ( BiTree *bt) /*按先序次序輸入二叉樹中結(jié)點的值（一個字符）， 圓點字符表示空樹。構(gòu)造二叉鏈表表示的二叉樹 T。*/ , / CreateBiTree,scanf ( / 若是字符則令指針為空,else if ( ! ( *bt = ( BiTNode * ) malloc ( sizeof ( BiTNode ) ) ) ) return; (*bt)-data = ch; / 生成根結(jié)點 CreateBiTree ( / 構(gòu)造右子樹 ,60,先序、中序和后序遍歷二叉樹的結(jié)點比處理單鏈表中的一個結(jié)點要復(fù)雜。對單鏈表，我們曾經(jīng)定義了求前驅(qū)和求后繼的運算。那么在樹中可以嗎？,6.4 二叉線索樹,61,二叉線索樹的引出,二叉線索樹的定義,二叉線索樹的存儲結(jié)構(gòu),二叉線索樹的操作,(1) 先序排序如何實現(xiàn)求前驅(qū)和求后繼運算？,后繼,后繼,62,6.4.1 線索二叉樹的引出,對于求后繼運算，如果所考慮的結(jié)點是非葉子結(jié)點，那么該結(jié)點的左孩子就是它的后繼結(jié)點。,如果結(jié)點的左孩子不存在，那么該結(jié)點的右孩子就是它的后繼結(jié)點。,如果所考慮的結(jié)點是葉子結(jié)點，那么要找到該結(jié)點的后繼結(jié)點，就必須遍歷二叉樹。,對于求前驅(qū)運算，在先序排序下，不論何種情況都需要遍歷二叉樹。,(2) 后序排序如何實現(xiàn)求前驅(qū)和求后繼運算？,前驅(qū),前驅(qū),63,對于求前驅(qū)運算，如果所考慮的結(jié)點是非葉子結(jié)點，那么該結(jié)點的右孩子就是它的前驅(qū)結(jié)點。,如果該結(jié)點的右孩子不存在，那么該結(jié)點的左孩子就是它的前驅(qū)結(jié)點。,如果所考慮的結(jié)點是葉子結(jié)點，那么要找到該結(jié)點的前驅(qū)結(jié)點，就必須遍歷二叉樹。,對于求后繼運算，在后序排序下，不論何種情況都需要遍歷二叉樹。,(3) 中序排序如何實現(xiàn)求前驅(qū)和求后繼運算？,對于求后繼運算，若所考慮的結(jié)點有右孩子，那么就要從該右孩子開始，順著該右孩子的左孩子鏈域找下去，一直找到左孩子的鏈域是空為止，最后這個結(jié)點就是所考慮結(jié)點的后繼結(jié)點；若所考慮的結(jié)點無右孩子，那么就要遍歷二叉樹。,后繼,64,對于求前驅(qū)運算，若所考慮的結(jié)點有左孩子，那么就要從該左孩子開始，順著該左孩子的右孩子鏈域找下去，一直找到右孩子的鏈域是空為止，最后這個結(jié)點就是所考慮結(jié)點的前驅(qū)結(jié)點；若所考慮的結(jié)點無左孩子，那么就要遍歷二叉樹。,前驅(qū),(4) 如何保存在遍歷二叉樹的動態(tài)過程中得到的某一結(jié)點的前驅(qū)和后繼信息？ 方法有兩個。,65,66,試做如下規(guī)定：若結(jié)點有左子樹，則其 lchild 域指示其左孩子，否則令 lchild 域指示其前驅(qū)；若結(jié)點有右子樹，則其 rchild 域指示其右孩子，否則令 rchild 域指示其后繼。,為了避免混淆，需改變二叉鏈表的結(jié)點結(jié)構(gòu)，增加兩個標(biāo)志域：ltag 和 rtag。,其中：,ltag =,0,1,lchild 域指示結(jié)點的左孩子,lchild 域指示結(jié)點的前驅(qū),rtag =,0,1,rchild 域指示結(jié)點的右孩子,rchild 域指示結(jié)點的后繼,左孩子或前驅(qū)域,右孩子或后繼域,數(shù)據(jù)域,左標(biāo)志域,右標(biāo)志域,67,6.4.2 二叉線索樹的定義,這種存儲方式利用了二叉鏈表中原有的空鏈域，提高了結(jié)構(gòu)的存儲密度，是一種實用的做法。,相關(guān)概念如下：,68, 線索鏈表：以這種結(jié)點結(jié)構(gòu)構(gòu)成的二叉鏈表作為二叉樹的存儲結(jié)構(gòu)稱之。, 線索：在線索鏈表中指向結(jié)點前驅(qū)和后繼的指針稱之。, 線索二叉樹：加上線索的二叉樹稱之。, 線索化：對二叉樹以某種次序遍歷使其變?yōu)榫€索二叉樹的過程稱之。,typedef struct BiThrNode DataType data; / 數(shù)據(jù)域 struct BiThrNode *lchild, *rchild; / 左右孩子指針 PointerTag ltag, rtag; / 左右標(biāo)志 BiThrNode, *BiThrTree; / 線索二叉樹的類型名,通常，線索二叉樹指中序線索二叉樹，簡稱線索樹。,69,6.4.3 二叉樹線索的存儲結(jié)構(gòu),為了方便起見，仿照線性表的存儲結(jié)構(gòu)：,70, 在二叉樹線索鏈表上也添加一個頭結(jié)點，并令其 lchild 域指針指向二叉樹的根結(jié)點，其 rchild 域指針指向中序遍歷二叉樹時訪問的最后一個結(jié)點；, 令二叉樹中序序列第一個結(jié)點的 lchild 域指針和最后一個結(jié)點的 rchild 域指針均指向頭結(jié)點。,(1) 算法思想,71,判斷給定結(jié)點 t 的左指針 lchild 是否指向頭結(jié)點 Thrt。若是，則返回 ；若否，則繼續(xù)下面的操作。,判斷給定結(jié)點 t 的左標(biāo)志 ltag 是否為 1。若為 1，則t-LChild指向t的前驅(qū)。當(dāng)t-LChild=0時，則說明 p 指向結(jié)點 t 的左孩子(p=t-LChild)，這時就需要順著 p 所指結(jié)點的右鏈域?qū)ふ遥钡浇Y(jié)點右標(biāo)志 rtag 為 1；若為 1，則說明 p 指向結(jié)點 t 的線索，即 p 所指向的結(jié)點就是結(jié)點 t 的前驅(qū)。,6.4.4 二叉線索樹的操作,1. 在二叉線索樹中求結(jié)點的中序前驅(qū),int InPre( BiThrTree t, BiThrTree p ) / t 指向中序線索樹中某一結(jié)點，p 返回此結(jié)點的前驅(qū)； 并返回 OK ,p = t-lchild; / 將 t 的 lchild 域的值賦給 p if ( p = Thrt ) return ERROR; / 若 p 指向頭結(jié)點，則出錯,if ( t-ltag = 0) / 若 t 的左標(biāo)志為 0 while ( p-rtag = =0) p = p-rchild; / 順著 t 的左孩子的右鏈域?qū)ふ?，直到結(jié)點右標(biāo)志是 1 為止,return OK; / InPre,(2) 算法實現(xiàn),72,(3) 算法分析,73,如果 t 所指向結(jié)點的左孩子有 k 層右孩子，則需要進(jìn)行 k+1 次比較，因此 Inpre 算法的時間復(fù)雜度為 O(k)。,(1) 算法思想,74,判斷給定結(jié)點 t 的右指針 rchild 是否指向頭結(jié)點 Thrt。若是，則返回 ERROR；若否，則繼續(xù)。,判斷給定結(jié)點 t 的右標(biāo)志 rtag 是否為 0。若為 0，則用 p 指向結(jié)點 t 的右孩子，這時就需要順著 p 所指結(jié)點的左鏈域?qū)ふ?，直到結(jié)點左標(biāo)志 ltag 為 1；若為 1，則說明 p 指向結(jié)點 t 的線索，即 p 所指向的結(jié)點就是結(jié)點 t 的后繼。,2. 在二叉線索樹中求結(jié)點的中序后繼,int InNext ( BiThrTree t, BiThrTree p ) / t 指向中序線索樹中某一結(jié)點，p 返回此結(jié)點的后繼； 并返回 OK ,p = t-rchild; / 將 t 的 rchild 域值賦給 p if ( p = =Thrt ) return ERROR; / 若 p 指向頭結(jié)點，則出錯,if ( t-rtag = 0 ) / 若 t 的右標(biāo)志為 0 while ( p-ltag = =0) p = p-lchild; / 順著 t 的右孩子的左鏈域?qū)ふ遥钡浇Y(jié)點左標(biāo)志是 1 為止,return OK; / InNext,(2) 算法實現(xiàn),75,(3) 算法分析,76,如果 t 所指向結(jié)點的右孩子有 k 層左孩子，則需要進(jìn)行 k+1 次比較，因此 Next_Thr 算法的時間復(fù)雜度為 O(k)。,下面給出將值為 e 的新結(jié)點 r 插入到中序線索樹中，作為結(jié)點 p 的右孩子。 (1) 算法思想,77,建立新結(jié)點 r，使其數(shù)據(jù)域的值為 e；,如果結(jié)點 p 無右孩子，則做： 將新結(jié)點 r 插入線索樹中作為結(jié)點 p 的右孩子。 結(jié)點 p 的后繼是新結(jié)點 r的后繼，r的前驅(qū)是 p；且r.ltag = 1，r.rtag = 1。 修改 p.rchild,使其指向新結(jié)點 r,且 t.rtag = 0。,3. 在二叉線索樹中插入結(jié)點,如果 p 有右孩子，則做：,78, 將新結(jié)點 r 插入到線索樹中作為結(jié)點 p 的右孩子； p 的右子樹在新結(jié)點 r 插入之后，應(yīng)該成為新結(jié)點 r 的右子樹，這樣就有 r.rtag = 0；新結(jié)點 r 的前驅(qū)是 p；且 r.ltag = 1； 修改 p.rchild，使其指向新結(jié)點 r，且 p.rtag = 0。 求出新結(jié)點 r 的后繼，并修改 r 的后繼的 lchild 域，使其指向新結(jié)點 r，即這個結(jié)點的前驅(qū)應(yīng)該為 q。,int InsNode(BiThrTree Thrt, BiThrTree p, BiThrTree r) / 將新結(jié)點r插入到中序線索樹中作為結(jié)點 p的右孩子，并返回 OK ,if ( ! ( r = ( BiThrTree ) malloc ( sizeof ( BiThrNode ) ) ) ) exit ( OVERFLOW );,r-data = e; r-rchild = p-rchild; r-rtag = p-rtag; r-lchild = p; r-ltag = 1; p-rchild = r; p-rtag = 0;,if ( r-rtag = 0 ) InNext ( / 若 r 的右標(biāo)志為 0，則尋找 r 的后繼 s，并將 r 作為 s 的前驅(qū),return OK /InsNode,(2) 算法描述,79,(3) 算法分析,80,InsNode 算法的執(zhí)行時間主要取決于 InNext (r, s) 算法（求結(jié)點 r 的后繼 s）。如果 r 的右孩子有 k 層左孩子，則尋找 r 的后繼 s 需要進(jìn)行 k+1 次比較，因此 Next_Thr 算法時間復(fù)雜度為 O(k)。故 InNext 算法的時間復(fù)雜度也為 O(k)。 同理，可以編寫出將值為 e 的新結(jié)點 r 插入到中序線索樹中，作為結(jié)點 p 的左孩子。,(1) 算法思想,81, 令 p 指向根結(jié)點，且當(dāng)二叉樹為非空樹或遍歷未結(jié)束時，繼續(xù)做如下操作；, 順著 p 的左鏈域?qū)ふ?，直到結(jié)點的左標(biāo)志域 ltag = 1 時為止，即結(jié)點的左鏈域 lchild 為空；, 訪問其左鏈域 lchild 為空的結(jié)點；,4. 遍歷二叉線索樹, 當(dāng) p 的右標(biāo)志域 rtag = 1，并且右鏈域 rchild 不指向頭結(jié)點時（即 p 的 rchild 指向后繼），則訪問后繼；,82, 當(dāng) p 的右標(biāo)志域 rtag = 0（即 p 的 rchild 指向右孩子），或右鏈域 rchild 指向頭結(jié)點時，則令 p = p-rchild, 當(dāng) p 指向非空樹或遍歷未結(jié)束時，則重復(fù)執(zhí)行上述步驟 。,void TInOrder ( BiThrTree Thrt) /*Thrt 指向中序線索樹的頭結(jié)點， 頭結(jié)點的左鏈域 lchild 指向根結(jié)點，遍歷中序線索樹 T 的非遞歸算法， 對每個數(shù)據(jù)元素調(diào)用函數(shù) Visit 。*/ p = Thrt-lchild; / p 指向根結(jié)點 while ( p != Thrt ) / 當(dāng)空樹或遍歷結(jié)束時，p = = Thrt while ( p-ltag = = 0 ) p = p-lchild; / 順著 p 的左鏈域?qū)ふ?，直到結(jié)點左標(biāo)志是 1 時為止 if ( ! Visit ( p-data ) ) return ERROR; / 訪問其左子樹為空的結(jié)點 while ( p-rtag = = 1 / while / InOrderTraverse,(2) 算法描述,void TInOrder ( BiThrTree Thrt) /*Thrt 指向中序線索樹的頭結(jié)點， 頭結(jié)點的左鏈域 lchild 指向根結(jié)點， 遍歷中序線索樹 T 的非遞歸算法， 對每個數(shù)據(jù)元素調(diào)用函數(shù) Visit 。*/ ,p = Thrt-lchild; / p 指向根結(jié)點,while ( p != Thrt ) / 當(dāng)空樹或遍歷結(jié)束時，p = = Thrt while ( p-ltag = = 0 ) p = p-lchild; / 順著 p 的左鏈域?qū)ふ?，直到結(jié)點左標(biāo)志是 1 時為止,(2) 算法描述,84,if ( ! Visit ( p-data ) ) return ERROR; / 訪問其左子樹為空的結(jié)點,while ( p-rtag = = 1 ,(3) 算法分析,85,TInOrder 算法的時間復(fù)雜度為 O(n)。 在中序線索樹上遍歷，雖然時間復(fù)雜度也為 O(n)，但是其常數(shù)因子要比在中序二叉樹上遍歷小，并且不需要設(shè)立棧。,(1) 算法思想,86,由于線索化的實質(zhì)是將二叉鏈表中的空指針改為指向前驅(qū)或后繼線索，而前驅(qū)或后繼的信息只有在遍歷時才能得到，因此線索化的過程即為在遍歷的過程中修改空指針的過程。 為了記下遍歷過程中訪問結(jié)點的先后關(guān)系，需要附設(shè)指針 pre 始終指向剛剛訪問過的結(jié)點，若指針 p 指向當(dāng)前訪問的結(jié)點，則 pre 指向它的前驅(qū)。 先線索化以 root 為根的二叉樹， 后線索化頭結(jié)點。,5. 二叉樹的線索化,87,6.5 樹和森林與二叉樹的轉(zhuǎn)換,樹與二叉樹的轉(zhuǎn)換,森林與二叉樹的轉(zhuǎn)換,樹和森林的遍歷,由于樹和二叉樹都可以使用二叉鏈表作為存儲結(jié)構(gòu)，因此可以用二叉鏈表作為媒介導(dǎo)出樹與二叉樹之間的一個對應(yīng)關(guān)系。也就是說，給定一棵樹，可以找到惟一的一棵二叉樹與之對應(yīng)，從物理結(jié)構(gòu)來看，它們的二叉鏈表是相同的，只是解釋不同而已。,88,6.5.1 樹與二叉樹的轉(zhuǎn)換,1. 樹轉(zhuǎn)換為二叉樹 樹轉(zhuǎn)換為二叉樹的可以按照如下步驟進(jìn)行：,89,加線：在各兄弟結(jié)點之間加一連線；,除線：對任何結(jié)點，除了其最左邊的孩子之外，去掉該結(jié)點與其余孩子的各枝；,旋轉(zhuǎn)：將添加的水平連線和原有的連線，以樹的根結(jié)點為軸心，按順時針方向旋轉(zhuǎn) 45。,2. 二叉樹還原為樹 二叉樹還原為樹可以按照如下步驟進(jìn)行：,90,加線：若 p 結(jié)點是雙親的左孩子，則將 p 結(jié)點的右孩子，右孩子的右孩子，沿著右分支搜索到的所有右孩子，都分別與 p 結(jié)點的雙親用線連起來；,除線：去除原二叉樹中所有雙親結(jié)點與右孩子的連線；,旋轉(zhuǎn)：以樹的根結(jié)點為軸心，按逆時針方向旋轉(zhuǎn) 45。,從樹與二叉樹的轉(zhuǎn)換中可知，轉(zhuǎn)換之后的二叉樹的根結(jié)點沒有右孩子，如果把森林中的第二棵樹的根結(jié)點看成是第一棵樹的根結(jié)點的兄弟，則同樣可以導(dǎo)出森林和二叉樹的對應(yīng)關(guān)系。,91,6.5.2 森林與二叉樹的轉(zhuǎn)換,1. 森林轉(zhuǎn)換為二叉樹 森林轉(zhuǎn)換為二叉樹可以按照如下步驟進(jìn)行：,92,轉(zhuǎn)換：將森林中的每一棵樹轉(zhuǎn)換成二叉樹；,連線：將各棵轉(zhuǎn)換后的二叉樹的根結(jié)點相連；,旋轉(zhuǎn)：將添加的水平連線和原有的連線以第一棵樹根結(jié)點為軸心，按順時針方向粗略地旋轉(zhuǎn) 45。,93,轉(zhuǎn) 換,連 線,旋 轉(zhuǎn),94,2. 二叉樹還原為森林 二叉樹還原為森林可以按照如下步驟進(jìn)行：,抹線：抹掉二叉樹根結(jié)點右鏈上所有結(jié)點上的連線，分成若干個以右鏈上結(jié)點為根結(jié)點的子二叉樹；,轉(zhuǎn)換：將分好的子二叉樹轉(zhuǎn)換成樹；,調(diào)整：將轉(zhuǎn)換好的樹的根結(jié)點排列成一排。,1. 樹的遍歷,95,先根遍歷：若樹非空，則先訪問樹的根結(jié)點，然后依次先根遍歷根的每棵子樹。,后根遍歷：若樹非空，則先依次后根遍歷根的每棵子樹，然后訪問樹的根結(jié)點。,層次遍歷：若樹非空，則從樹的根結(jié)點起按層從左到右依次訪問各結(jié)點。,6.5.3 樹和森林的遍歷,96,2. 森林的遍歷,先序遍歷：若森林非空，則：訪問森林中第一棵樹根結(jié)點；先序遍歷第一棵樹中根結(jié)點的子樹森林；先序遍歷除去第一棵樹后剩余的樹構(gòu)成的森林。,中序遍歷：若森林非空，則：中序遍歷第一棵樹中根結(jié)點的子樹森林；訪問森林中第一棵樹根結(jié)點；中序遍歷除去第一棵樹后剩余的樹構(gòu)成的森林。,層次遍歷：若森林非空，則：對第一棵樹從根結(jié)點起按層從左到右依次訪問結(jié)點；按層訪問森林中除第一棵樹外剩余的樹構(gòu)成的森林。,森林,先序遍歷森林,對應(yīng)的二叉樹,先序遍歷二叉樹 A B C D E F G H I J,97,A,B,C,D,E,F,G,H,I,J,赫夫曼 (Huffman) 樹，又稱最優(yōu)二叉樹，它是 n 個帶權(quán)葉子結(jié)點構(gòu)成的所有二叉樹中，帶權(quán)路徑長度最短的二叉樹，有著廣泛的應(yīng)用。因為構(gòu)造這種樹的算法最早由赫夫曼 (Huffman) 于 1952 年提出的，所以被稱為赫夫曼樹。,98,6.6 赫夫曼樹及其應(yīng)用,基本概念,99,赫夫曼算法,赫夫曼編碼,赫夫曼樹和赫夫曼編碼的存儲表示,赫夫曼編碼的算法,示例,100,在赫夫曼樹及其應(yīng)用中經(jīng)常會用到一些基本術(shù)語。例如：,路徑,路徑長度,樹的路徑長度,結(jié)點的帶權(quán)路徑長度,樹的帶權(quán)路徑長度,赫夫曼樹,6.6.1 基本概念,101,路徑：從樹中一個結(jié)點到另一個結(jié)點之間的分支構(gòu)成兩個結(jié)點之間的路徑。,路徑長度：路徑上的分支數(shù)目稱為路徑長度,樹的路徑長度：從樹根到每一個結(jié)點的路徑長度之和稱為樹的路徑長度。完全二叉樹就是這種路徑長度最短的二叉樹。,結(jié)點的帶權(quán)路徑長度：從該結(jié)點到樹根之間的路徑長度與結(jié)點上權(quán)的乘積稱為結(jié)點的帶權(quán)路徑長度。,樹的帶權(quán)路徑長度：樹中所有葉子結(jié)點的帶權(quán)路徑長度之和稱為樹的帶權(quán)路徑長度。通常記作,例如：此樹的帶權(quán)路徑長度為 24373512 = 46,赫夫曼樹的定義： 假設(shè)有 n 個權(quán)值 w1, w2, , wn ，構(gòu)造一棵有 n 個葉子結(jié)點的二叉樹，每個葉子結(jié)點帶權(quán)為 wi ，則其中帶權(quán)路徑長度 WPL 最小的二叉樹稱為最優(yōu)二叉樹或赫夫曼樹。,102,圖 (a) 的帶權(quán)路徑長度為 WPL = 72522242 = 36,(a),(b),(c),圖 (b) 的帶權(quán)路徑長度為 WPL = 73532142 = 46,圖 (c) 的帶權(quán)路徑長度為 WPL = 71522343 = 35,103,下面所示的 3 棵二叉樹都含有 4 個葉子結(jié)點 A、B、C、D，分別帶權(quán) 7、5、2、4。,1. 赫夫曼算法思想 構(gòu)造赫夫曼樹的算法稱之為赫夫曼算法，其具體步驟如下：,104, 根據(jù)給定的 n 個權(quán)值 w1, w2, , wn ，構(gòu)成 n 棵二叉樹的集合 F = T1, T2, , Tn ，其中每棵二叉樹 Ti 中只有一個帶權(quán) wi 的根結(jié)點，其左子樹和右子樹均為空。,6.6.2 赫夫曼算法, 在 F 中選取兩棵根結(jié)點的權(quán)值最小的樹作為左子樹和右子樹，構(gòu)造一棵新的二叉樹，并且置新的二叉樹的根結(jié)點的權(quán)值為其左子樹和右子樹上根結(jié)點的權(quán)值