《樹(shù)與二叉樹(shù)整》PPT課件.ppt

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