第6章 樹和二叉樹

1、數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法 作作 者：胡明者：胡明 王紅梅王紅梅 出版社：電子工業(yè)出版社出版社：電子工業(yè)出版社 郵郵 箱：箱：數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社樹的邏輯結(jié)構(gòu)樹的邏輯結(jié)構(gòu)樹的存儲(chǔ)結(jié)構(gòu)樹的存儲(chǔ)結(jié)構(gòu)二叉樹的邏輯結(jié)構(gòu)二叉樹的邏輯結(jié)構(gòu)二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)二叉樹遍歷的非遞歸算法二叉樹遍歷的非遞歸算法 樹、森林與二叉樹的轉(zhuǎn)換樹、森林與二叉樹的轉(zhuǎn)換哈夫曼樹和哈夫曼編碼哈夫曼樹和哈夫曼編碼第第 6 章章 樹和二叉樹樹和二叉樹本章的主要內(nèi)容是本章的主要內(nèi)容是數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出

2、版社電子工業(yè)出版社例例6-1 文件系統(tǒng)文件系統(tǒng)6.1 引言引言如何存儲(chǔ)這個(gè)文件目錄結(jié)構(gòu)并統(tǒng)計(jì)大小呢？如何存儲(chǔ)這個(gè)文件目錄結(jié)構(gòu)并統(tǒng)計(jì)大小呢？數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社例例6-2 二叉表示樹二叉表示樹6.1 引言引言如何建立二叉表示樹并進(jìn)行計(jì)算呢？如何建立二叉表示樹并進(jìn)行計(jì)算呢？一個(gè)算術(shù)表達(dá)式可以用二叉樹來表示，這樣的二叉樹稱為一個(gè)算術(shù)表達(dá)式可以用二叉樹來表示，這樣的二叉樹稱為二叉表示樹。表達(dá)式二叉表示樹。表達(dá)式(A+B)*(C+D*E) 的二叉表示樹如下：的二叉表示樹如下： 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社樹的定義樹的定義樹：樹：n（n0）個(gè)

3、個(gè)結(jié)點(diǎn)結(jié)點(diǎn)的有限的有限集合集合。當(dāng)。當(dāng)n0時(shí)，稱為時(shí)，稱為空樹；任意一棵非空樹滿足以下條件：空樹；任意一棵非空樹滿足以下條件： 有且僅有一個(gè)特定的稱為有且僅有一個(gè)特定的稱為根根的結(jié)點(diǎn)；的結(jié)點(diǎn)； 當(dāng)當(dāng)n1時(shí)，除根結(jié)點(diǎn)之外的其余結(jié)點(diǎn)被分成時(shí)，除根結(jié)點(diǎn)之外的其余結(jié)點(diǎn)被分成m（m0）個(gè)個(gè)互不相交互不相交的有限集合的有限集合T1, ,T2, , ,Tm，其中其中每個(gè)集合又是一棵樹，并稱為這個(gè)根結(jié)點(diǎn)的每個(gè)集合又是一棵樹，并稱為這個(gè)根結(jié)點(diǎn)的子樹子樹。6.2 樹的邏輯結(jié)構(gòu)樹的邏輯結(jié)構(gòu)樹的定義是采用遞歸方法樹的定義是采用遞歸方法數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社(a) 一棵樹結(jié)構(gòu)一棵樹結(jié)構(gòu)

4、 (b)一個(gè)非樹結(jié)構(gòu)一個(gè)非樹結(jié)構(gòu) (c)一個(gè)非樹結(jié)構(gòu)一個(gè)非樹結(jié)構(gòu) 樹的定義樹的定義ACBGFEDHIACBGFDACBGFDE6.2 樹的邏輯結(jié)構(gòu)樹的邏輯結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社樹的應(yīng)用舉例樹的應(yīng)用舉例文件結(jié)構(gòu)文件結(jié)構(gòu)My ComputerC:D:E:etcWINDOWSProgram FilesPictureMusic6.2 樹的邏輯結(jié)構(gòu)樹的邏輯結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社樹的基本術(shù)語樹的基本術(shù)語p 結(jié)點(diǎn)的度：結(jié)點(diǎn)的度：結(jié)點(diǎn)所擁有的子樹的個(gè)數(shù)。結(jié)點(diǎn)所擁有的子樹的個(gè)數(shù)。p 樹的度：樹的度：樹中各結(jié)點(diǎn)度的最大值。樹中各結(jié)點(diǎn)度的最

5、大值。CGBDEFKLHMIJA6.2 樹的邏輯結(jié)構(gòu)樹的邏輯結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社p 葉子結(jié)點(diǎn)：葉子結(jié)點(diǎn)：度為度為0的結(jié)點(diǎn)，也稱為終端結(jié)點(diǎn)。的結(jié)點(diǎn)，也稱為終端結(jié)點(diǎn)。p 分支結(jié)點(diǎn)：分支結(jié)點(diǎn)：度不為度不為0的結(jié)點(diǎn)，也稱為非終端結(jié)點(diǎn)。的結(jié)點(diǎn)，也稱為非終端結(jié)點(diǎn)。CGBDEFKLHMIJA樹的基本術(shù)語樹的基本術(shù)語6.2 樹的邏輯結(jié)構(gòu)樹的邏輯結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社p 孩子、雙親：孩子、雙親：樹中某結(jié)點(diǎn)子樹的根結(jié)點(diǎn)稱為這個(gè)結(jié)點(diǎn)的樹中某結(jié)點(diǎn)子樹的根結(jié)點(diǎn)稱為這個(gè)結(jié)點(diǎn)的孩孩子結(jié)點(diǎn)子結(jié)點(diǎn)，這個(gè)結(jié)點(diǎn)稱為它孩子結(jié)點(diǎn)的，這個(gè)結(jié)點(diǎn)稱為它孩子結(jié)點(diǎn)的雙

6、親結(jié)點(diǎn)雙親結(jié)點(diǎn)；p 兄弟：兄弟：具有同一個(gè)雙親的孩子結(jié)點(diǎn)互稱為兄弟。具有同一個(gè)雙親的孩子結(jié)點(diǎn)互稱為兄弟。 CGBDEFKLHMIJA樹的基本術(shù)語樹的基本術(shù)語6.2 樹的邏輯結(jié)構(gòu)樹的邏輯結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社p 路徑：路徑：如果樹的結(jié)點(diǎn)序列如果樹的結(jié)點(diǎn)序列n1, n2, , nk有如下關(guān)系：結(jié)點(diǎn)有如下關(guān)系：結(jié)點(diǎn)ni是是ni+1的雙親（的雙親（1=idata); /訪問根結(jié)點(diǎn)的數(shù)據(jù)域訪問根結(jié)點(diǎn)的數(shù)據(jù)域 PreOrder(root-lchild); /前序遞歸遍歷前序遞歸遍歷root的左子樹的左子樹 PreOrder(root-rchild); /前序遞歸遍歷前

7、序遞歸遍歷root的右子樹的右子樹 6.5 二叉樹的存儲(chǔ)結(jié)構(gòu)二叉樹的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社中序遍歷中序遍歷遞歸算法遞歸算法 void InOrder (BiNode *root) if (root = NULL) return; /遞歸調(diào)用的結(jié)束條件遞歸調(diào)用的結(jié)束條件 else InOrder(root-lchild); /中序遞歸遍歷中序遞歸遍歷root的左子樹的左子樹 printf(root-data); /訪問根結(jié)點(diǎn)的數(shù)據(jù)域訪問根結(jié)點(diǎn)的數(shù)據(jù)域 InOrder(root-rchild); /中序遞歸遍歷中序遞歸遍歷root的右子樹的右子樹 6.5

8、二叉樹的存儲(chǔ)結(jié)構(gòu)二叉樹的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社后序遍歷后序遍歷遞歸算法遞歸算法void PostOrder(BiNode *root) if (root = NULL) return; /遞歸調(diào)用的結(jié)束條件遞歸調(diào)用的結(jié)束條件 else PostOrder(root-lchild); /后序遞歸遍歷后序遞歸遍歷root的左子樹的左子樹 PostOrder(root-rchild); /后序遞歸遍歷后序遞歸遍歷root的右子樹的右子樹 printf(root-data); /訪問根結(jié)點(diǎn)的數(shù)據(jù)域訪問根結(jié)點(diǎn)的數(shù)據(jù)域 6.5 二叉樹的存儲(chǔ)結(jié)構(gòu)二叉樹的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)

9、結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社層序遍歷層序遍歷ABCDEFG遍歷序列：遍歷序列：AAB CBDCE F GD E F G6.5 二叉樹的存儲(chǔ)結(jié)構(gòu)二叉樹的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社層序遍歷層序遍歷 隊(duì)列隊(duì)列Q初始化；初始化； 2. 如果二叉樹非空，將根指針入隊(duì)；如果二叉樹非空，將根指針入隊(duì)；3. 循環(huán)直到隊(duì)列循環(huán)直到隊(duì)列Q為空為空 3.1 q=隊(duì)列隊(duì)列Q的隊(duì)頭元素出隊(duì)；的隊(duì)頭元素出隊(duì)； 3.2 訪問結(jié)點(diǎn)訪問結(jié)點(diǎn)q的數(shù)據(jù)域；的數(shù)據(jù)域； 3.3 若結(jié)點(diǎn)若結(jié)點(diǎn)q存在左孩子，則將左孩子指針入隊(duì)；存在左孩子，則將左孩子指針入隊(duì)； 3.4 若結(jié)點(diǎn)若

10、結(jié)點(diǎn)q存在右孩子，則將右孩子指針入隊(duì)；存在右孩子，則將右孩子指針入隊(duì)；6.5 二叉樹的存儲(chǔ)結(jié)構(gòu)二叉樹的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社建立二叉樹建立二叉樹6.5 二叉樹的存儲(chǔ)結(jié)構(gòu)二叉樹的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社建立二叉樹：建立二叉樹：i1為前序序列的起始下標(biāo)，為前序序列的起始下標(biāo)，i2為中序序列的為中序序列的起始下標(biāo)，起始下標(biāo)，k為序列長度為序列長度6.5 二叉樹的存儲(chǔ)結(jié)構(gòu)二叉樹的存儲(chǔ)結(jié)構(gòu)BiNode *Creat(BiNode *root, int i1, int i2, int k) if (k data = prei

11、1; /根結(jié)點(diǎn)為前序序列的第根結(jié)點(diǎn)為前序序列的第1個(gè)元素個(gè)元素 m = pos(prei1, pin, i2); /查找根結(jié)點(diǎn)在中序序列中的位置查找根結(jié)點(diǎn)在中序序列中的位置 leftlen = m - i2; /左子樹的長度左子樹的長度 rightlen = k -(leftlen + 1); /右子樹的長度右子樹的長度 root-lchild = Creat(root-lchild, i1+1, i2, leftlen); root-rchild = Creat(root-rchild, i1+leftlen+1, m+1, rightlen); return root;數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)

12、構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社二叉樹算法設(shè)計(jì)練習(xí)二叉樹算法設(shè)計(jì)練習(xí) 遍歷二叉樹是二叉樹各種操作的基礎(chǔ)，遍歷算法遍歷二叉樹是二叉樹各種操作的基礎(chǔ)，遍歷算法中對(duì)每個(gè)結(jié)點(diǎn)的訪問操作可以是多種形式及多個(gè)操中對(duì)每個(gè)結(jié)點(diǎn)的訪問操作可以是多種形式及多個(gè)操作，根據(jù)遍歷算法的框架，適當(dāng)修改訪問操作的內(nèi)作，根據(jù)遍歷算法的框架，適當(dāng)修改訪問操作的內(nèi)容，可以派生出很多關(guān)于二叉樹的應(yīng)用算法。容，可以派生出很多關(guān)于二叉樹的應(yīng)用算法。 void InOrder ( (BiNode *root) ) if ( (root=NULL) ) return; else InOrder( (root-lchild) ); co

13、ut-data; InOrder( (root-rchild) ); 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社二叉樹算法設(shè)計(jì)練習(xí)二叉樹算法設(shè)計(jì)練習(xí)設(shè)計(jì)算法求二叉樹的結(jié)點(diǎn)個(gè)數(shù)。設(shè)計(jì)算法求二叉樹的結(jié)點(diǎn)個(gè)數(shù)。 void Count(BiNode *root) /count為全局量并已初始化為為全局量并已初始化為0 if (root = NULL) return; else Count(root-lchild); count+; Count(root-rchild); 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社二叉樹算法設(shè)計(jì)練習(xí)二叉樹算法設(shè)計(jì)練習(xí)設(shè)計(jì)算法按前序次序打印二叉

14、樹中的葉子結(jié)點(diǎn)。設(shè)計(jì)算法按前序次序打印二叉樹中的葉子結(jié)點(diǎn)。 void PreOrder(BiNode *root) if (root = NULL) return; else if (!root-lchild & !root-rchild) coutdata; PreOrder(root-lchild); PreOrder(root-rchild); 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社二叉樹算法設(shè)計(jì)練習(xí)二叉樹算法設(shè)計(jì)練習(xí)設(shè)計(jì)算法求二叉樹的深度。設(shè)計(jì)算法求二叉樹的深度。 int Depth(BiNode *root) if (root = NULL) return

15、0; else hl= Depth(root-lchild); hr= Depth(root -rchild); return max(hl, hr)+1; 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社二叉樹算法設(shè)計(jì)練習(xí)二叉樹算法設(shè)計(jì)練習(xí)設(shè)計(jì)算法求樹中結(jié)點(diǎn)設(shè)計(jì)算法求樹中結(jié)點(diǎn) x 的第的第 i 個(gè)孩子。個(gè)孩子。 TNode *Search(TNode *root, DataType x, int i) if (root-data = x) j=1; p=root-firstchild; while (p!=NULL & jrightsib; if (p != NULL) re

16、turn p; else return NULL; Search(root-firstchild, x, i); Search(root-rightsib, x, i);數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社三叉鏈表三叉鏈表GFEDBAABCDEFGC在二叉鏈表中，如何求某結(jié)點(diǎn)的雙親？在二叉鏈表中，如何求某結(jié)點(diǎn)的雙親？6.5 二叉樹的存儲(chǔ)結(jié)構(gòu)二叉樹的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社三叉鏈表三叉鏈表 lchild dataparent rchild在二叉鏈表的基礎(chǔ)上增加了一個(gè)指向雙親的指針域。在二叉鏈表的基礎(chǔ)上增加了一個(gè)指向雙親的指針域。結(jié)點(diǎn)結(jié)構(gòu)

17、結(jié)點(diǎn)結(jié)構(gòu)其中：其中：data、lchild和和rchild三個(gè)域的含義同二叉鏈表三個(gè)域的含義同二叉鏈表的結(jié)點(diǎn)結(jié)構(gòu)；的結(jié)點(diǎn)結(jié)構(gòu)；parent域?yàn)橛驗(yàn)橹赶蛟摻Y(jié)點(diǎn)的雙親結(jié)點(diǎn)的指針。指向該結(jié)點(diǎn)的雙親結(jié)點(diǎn)的指針。 6.5 二叉樹的存儲(chǔ)結(jié)構(gòu)二叉樹的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社ABCDEFGABDEFCG三叉鏈表三叉鏈表6.5 二叉樹的存儲(chǔ)結(jié)構(gòu)二叉樹的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社ABCDEFG三叉鏈表的靜態(tài)鏈表形式三叉鏈表的靜態(tài)鏈表形式0123456data parent lchild rchildABCDEFG-1 0 0 1 2 2

18、 3 1 3 4-1-1-1-1 2-1 5 6-1-1-16.5 二叉樹的存儲(chǔ)結(jié)構(gòu)二叉樹的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社線索鏈表線索鏈表如何保存二叉樹的某種遍歷序列？如何保存二叉樹的某種遍歷序列？ABCDEFG中序遍歷序列：中序遍歷序列：D G B A F C F如果二叉樹如果二叉樹不不改變，如何保存？改變，如何保存？順順序序存存儲(chǔ)儲(chǔ)D G B A F C F6.5 二叉樹的存儲(chǔ)結(jié)構(gòu)二叉樹的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社線索鏈表線索鏈表如何保存二叉樹的某種遍歷序列？如何保存二叉樹的某種遍歷序列？ABCDEFG中序遍歷序列：中

19、序遍歷序列：D G B A F C F如果二叉樹改變，如何保存？如果二叉樹改變，如何保存？鏈鏈接接存存儲(chǔ)儲(chǔ) D F 6.5 二叉樹的存儲(chǔ)結(jié)構(gòu)二叉樹的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社線索鏈表線索鏈表如何保存二叉樹的某種遍歷序列？如何保存二叉樹的某種遍歷序列？ABCDEFG中序遍歷序列：中序遍歷序列：D G B A F C F如何將二叉鏈表與中序鏈表結(jié)合？如何將二叉鏈表與中序鏈表結(jié)合？鏈接鏈接存儲(chǔ)存儲(chǔ) D F 6.5 二叉樹的存儲(chǔ)結(jié)構(gòu)二叉樹的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社線索鏈表線索鏈表p線索：線索：將二叉鏈表中的空指針域指向前驅(qū)結(jié)

20、點(diǎn)和后將二叉鏈表中的空指針域指向前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)的指針被稱為線索；繼結(jié)點(diǎn)的指針被稱為線索；p線索化：線索化：使二叉鏈表中結(jié)點(diǎn)的空鏈域存放其前驅(qū)或使二叉鏈表中結(jié)點(diǎn)的空鏈域存放其前驅(qū)或后繼信息的過程稱為線索化；后繼信息的過程稱為線索化；p線索鏈表：線索鏈表：加上線索的二叉鏈表稱為線索鏈表。加上線索的二叉鏈表稱為線索鏈表。如何保存二叉樹的某種遍歷序列？如何保存二叉樹的某種遍歷序列？將二叉鏈表中的空指針域指向其前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)將二叉鏈表中的空指針域指向其前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)6.5 二叉樹的存儲(chǔ)結(jié)構(gòu)二叉樹的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社 ltag lchild dat

21、a child rtag0: lchild指向該結(jié)點(diǎn)的左孩子指向該結(jié)點(diǎn)的左孩子1: lchild指向該結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)指向該結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)0: rchild指向該結(jié)點(diǎn)的右孩子指向該結(jié)點(diǎn)的右孩子1: rchild指向該結(jié)點(diǎn)的后繼結(jié)點(diǎn)指向該結(jié)點(diǎn)的后繼結(jié)點(diǎn)ltag=rtag=結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu)線索鏈表線索鏈表6.5 二叉樹的存儲(chǔ)結(jié)構(gòu)二叉樹的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社enum flag Child, Thread; /枚舉類型枚舉類型typedef int DataType; / DataType為二叉樹的數(shù)據(jù)類型為二叉樹的數(shù)據(jù)類型typedef struct Thr

22、Node /定義線索鏈表的結(jié)點(diǎn)結(jié)構(gòu)定義線索鏈表的結(jié)點(diǎn)結(jié)構(gòu) DataType data; ThrNode *lchild, *rchild; flag ltag, rtag; ThrNode, *root; /root為指向線索鏈表的頭指針為指向線索鏈表的頭指針線索鏈表線索鏈表 ltag lchild data child rtag結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu)6.5 二叉樹的存儲(chǔ)結(jié)構(gòu)二叉樹的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社二叉樹的遍歷方式有二叉樹的遍歷方式有4種，故有種，故有4種意義下的前驅(qū)和后種意義下的前驅(qū)和后繼，相應(yīng)的有繼，相應(yīng)的有4種線索二叉樹：種線索二叉樹： 前序線索

23、二叉樹前序線索二叉樹 中序線索二叉樹中序線索二叉樹 后序線索二叉樹后序線索二叉樹 層序線索二叉樹層序線索二叉樹線索二叉樹線索二叉樹6.5 二叉樹的存儲(chǔ)結(jié)構(gòu)二叉樹的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社FABDCEG中序線索二叉樹中序線索二叉樹線索二叉樹線索二叉樹中序序列：中序序列：D G B A E C F6.5 二叉樹的存儲(chǔ)結(jié)構(gòu)二叉樹的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社分析：分析：建立線索鏈表，實(shí)質(zhì)上就是將二叉鏈表中的空建立線索鏈表，實(shí)質(zhì)上就是將二叉鏈表中的空指針改為指向前驅(qū)或后繼的線索，而前驅(qū)或后繼的信指針改為指向前驅(qū)或后繼的線索，而

24、前驅(qū)或后繼的信息只有在遍歷該二叉樹時(shí)才能得到。息只有在遍歷該二叉樹時(shí)才能得到。建立二叉鏈表建立二叉鏈表遍歷二叉樹，將遍歷二叉樹，將空指針改為線索空指針改為線索建立線索鏈表建立線索鏈表6.5 二叉樹的存儲(chǔ)結(jié)構(gòu)二叉樹的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社A頭指針頭指針BCDEFG00000000000000中序線索鏈表中序線索鏈表的建立過程的建立過程已經(jīng)建立起二叉鏈表已經(jīng)建立起二叉鏈表6.5 二叉樹的存儲(chǔ)結(jié)構(gòu)二叉樹的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社A頭指針頭指針BCDEFG00000000000000中序線索鏈表中序線索鏈表的建立過程的建

25、立過程中序遍歷二叉鏈表中序遍歷二叉鏈表p為正在訪問的結(jié)點(diǎn)為正在訪問的結(jié)點(diǎn)pre為剛訪問的結(jié)點(diǎn)為剛訪問的結(jié)點(diǎn)p16.5 二叉樹的存儲(chǔ)結(jié)構(gòu)二叉樹的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社A頭指針頭指針BCDEFG00000000000000中序線索鏈表中序線索鏈表的建立過程的建立過程中序遍歷二叉鏈表中序遍歷二叉鏈表p為正在訪問的結(jié)點(diǎn)為正在訪問的結(jié)點(diǎn)pre為剛訪問的結(jié)點(diǎn)為剛訪問的結(jié)點(diǎn)pre1p16.5 二叉樹的存儲(chǔ)結(jié)構(gòu)二叉樹的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社A頭指針頭指針BCDEFG00000000000000中序線索鏈表中序線索鏈表的建立過程

26、的建立過程中序遍歷二叉鏈表中序遍歷二叉鏈表p為正在訪問的結(jié)點(diǎn)為正在訪問的結(jié)點(diǎn)pre為剛訪問的結(jié)點(diǎn)為剛訪問的結(jié)點(diǎn)pre11p16.5 二叉樹的存儲(chǔ)結(jié)構(gòu)二叉樹的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社A頭指針頭指針BCDEFG00000000000000中序線索鏈表中序線索鏈表的建立過程的建立過程中序遍歷二叉鏈表中序遍歷二叉鏈表p為正在訪問的結(jié)點(diǎn)為正在訪問的結(jié)點(diǎn)pre為剛訪問的結(jié)點(diǎn)為剛訪問的結(jié)點(diǎn)pre11p116.5 二叉樹的存儲(chǔ)結(jié)構(gòu)二叉樹的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社A頭指針頭指針BCDEFG00000000000000中序線索鏈表中序

27、線索鏈表的建立過程的建立過程中序遍歷二叉鏈表中序遍歷二叉鏈表p為正在訪問的結(jié)點(diǎn)為正在訪問的結(jié)點(diǎn)pre為剛訪問的結(jié)點(diǎn)為剛訪問的結(jié)點(diǎn)pre11p1116.5 二叉樹的存儲(chǔ)結(jié)構(gòu)二叉樹的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社A頭指針頭指針BCDEFG00000000000000中序線索鏈表中序線索鏈表的建立過程的建立過程中序遍歷二叉鏈表中序遍歷二叉鏈表p為正在訪問的結(jié)點(diǎn)為正在訪問的結(jié)點(diǎn)pre為剛訪問的結(jié)點(diǎn)為剛訪問的結(jié)點(diǎn)pre11p11116.5 二叉樹的存儲(chǔ)結(jié)構(gòu)二叉樹的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社A頭指針頭指針BCDEFG000000000

28、00000中序線索鏈表中序線索鏈表的建立過程的建立過程中序遍歷二叉鏈表中序遍歷二叉鏈表p為正在訪問的結(jié)點(diǎn)為正在訪問的結(jié)點(diǎn)pre為剛訪問的結(jié)點(diǎn)為剛訪問的結(jié)點(diǎn)pre11p111116.5 二叉樹的存儲(chǔ)結(jié)構(gòu)二叉樹的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社A頭指針頭指針BCDEFG00000000000000中序線索鏈表中序線索鏈表的建立過程的建立過程中序遍歷二叉鏈表中序遍歷二叉鏈表p為正在訪問的結(jié)點(diǎn)為正在訪問的結(jié)點(diǎn)pre為剛訪問的結(jié)點(diǎn)為剛訪問的結(jié)點(diǎn)pre111111116.5 二叉樹的存儲(chǔ)結(jié)構(gòu)二叉樹的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社在遍歷過程中

29、，訪問當(dāng)前結(jié)點(diǎn)在遍歷過程中，訪問當(dāng)前結(jié)點(diǎn)root的操作為：的操作為：如果如果root的左、右指針域?yàn)榭?，則將相應(yīng)標(biāo)志置的左、右指針域?yàn)榭?，則將相應(yīng)標(biāo)志置1；若若root的左指針域?yàn)榭?，則令其指向它的前驅(qū)，這的左指針域?yàn)榭?，則令其指向它的前驅(qū)，這需要設(shè)指針需要設(shè)指針pre始終指向剛剛訪問過的結(jié)點(diǎn)，顯然始終指向剛剛訪問過的結(jié)點(diǎn)，顯然pre的初值為的初值為NULL；若若pre的右指針域?yàn)榭?，則令其指向的右指針域?yàn)榭眨瑒t令其指向它的后繼，即當(dāng)前訪問的結(jié)點(diǎn)它的后繼，即當(dāng)前訪問的結(jié)點(diǎn)root; 令令pre指向剛剛訪問過的結(jié)點(diǎn)指向剛剛訪問過的結(jié)點(diǎn)root；6.5 二叉樹的存儲(chǔ)結(jié)構(gòu)二叉樹的存儲(chǔ)結(jié)構(gòu)建立線索鏈表

30、建立線索鏈表數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社1. 建立二叉鏈表，將每個(gè)結(jié)點(diǎn)的左右標(biāo)志置為建立二叉鏈表，將每個(gè)結(jié)點(diǎn)的左右標(biāo)志置為0；2. 遍歷二叉鏈表，建立線索；遍歷二叉鏈表，建立線索； 2.1 如果二叉鏈表如果二叉鏈表root為空，則空操作返回；為空，則空操作返回； 2.2 對(duì)對(duì)root的左子樹建立線索；的左子樹建立線索； 2.3 對(duì)根結(jié)點(diǎn)對(duì)根結(jié)點(diǎn)root建立線索；建立線索； 2.3.1 若若root沒有左孩子，則為沒有左孩子，則為root加上前驅(qū)線索加上前驅(qū)線索; 2.3.2 若若root沒有右孩子沒有右孩子，則將則將root右標(biāo)志置為右標(biāo)志置為1； 2.3.3 若結(jié)

31、點(diǎn)若結(jié)點(diǎn)pre右標(biāo)志為右標(biāo)志為1，則為，則為pre加上后繼線索；加上后繼線索； 2.3.4 令令pre指向剛剛訪問的結(jié)點(diǎn)指向剛剛訪問的結(jié)點(diǎn)root； 2.4 對(duì)對(duì)root的右子樹建立線索。的右子樹建立線索。6.5 二叉樹的存儲(chǔ)結(jié)構(gòu)二叉樹的存儲(chǔ)結(jié)構(gòu)建立線索鏈表建立線索鏈表數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社void inThrBiTree(ThrNode *root) /pre是全局變量，初始化為空是全局變量，初始化為空 if (root = NULL) return; inThrBiTree(root-lchild); /遞歸處理遞歸處理root的左子樹的左子樹 if (r

32、oot-lchild = NULL) /對(duì)對(duì)root的左指針進(jìn)行處理的左指針進(jìn)行處理 root-ltag = 1; root-lchild = pre; /設(shè)置設(shè)置pre的前驅(qū)線索的前驅(qū)線索 if (root-rchild = NULL) /對(duì)對(duì)root的右指針進(jìn)行處理的右指針進(jìn)行處理 root-rtag = 1; if (pre-rtag = 1) pre-rchild = root; /設(shè)置設(shè)置pre的后繼線索的后繼線索 pre = root; inThrBiTree(root-rchild); /遞歸處理遞歸處理root的右子樹的右子樹6.5 二叉樹的存儲(chǔ)結(jié)構(gòu)二叉樹的存儲(chǔ)結(jié)構(gòu)建立線索鏈表

33、建立線索鏈表數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社中序線索鏈表查找后繼中序線索鏈表查找后繼FABDCEG 如果結(jié)點(diǎn)如果結(jié)點(diǎn)p的右標(biāo)志為的右標(biāo)志為1，則表明該結(jié)點(diǎn)的右指針是線索；則表明該結(jié)點(diǎn)的右指針是線索； 如果結(jié)點(diǎn)如果結(jié)點(diǎn)p的右標(biāo)志為的右標(biāo)志為0，則表明該結(jié)點(diǎn)有右孩子。根據(jù)則表明該結(jié)點(diǎn)有右孩子。根據(jù)中序遍歷的操作定義，它的后中序遍歷的操作定義，它的后繼結(jié)點(diǎn)應(yīng)該是遍歷其右子樹時(shí)繼結(jié)點(diǎn)應(yīng)該是遍歷其右子樹時(shí)第一個(gè)訪問的結(jié)點(diǎn)，即右子樹第一個(gè)訪問的結(jié)點(diǎn)，即右子樹中的最左下結(jié)點(diǎn)。中的最左下結(jié)點(diǎn)。6.5 二叉樹的存儲(chǔ)結(jié)構(gòu)二叉樹的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版

34、社ThrNode *Next(ThrNode *p) if (p-rtag = 1) /右標(biāo)志為右標(biāo)志為1，可直接得到后繼結(jié)點(diǎn)，可直接得到后繼結(jié)點(diǎn) q = p-rchild; else q = p-rchild; /工作指針工作指針q指向結(jié)點(diǎn)指向結(jié)點(diǎn)p的右孩子的右孩子 while (q-ltag = 0) /查找最左下結(jié)點(diǎn)查找最左下結(jié)點(diǎn) q = q-lchild; return q;中序線索鏈表查找后繼中序線索鏈表查找后繼6.5 二叉樹的存儲(chǔ)結(jié)構(gòu)二叉樹的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社二叉樹前序遍歷的非遞歸算法的二叉樹前序遍歷的非遞歸算法的關(guān)鍵關(guān)鍵：在前序遍歷過

35、：在前序遍歷過某結(jié)點(diǎn)的整個(gè)左子樹后，如何找到該結(jié)點(diǎn)的某結(jié)點(diǎn)的整個(gè)左子樹后，如何找到該結(jié)點(diǎn)的右子樹右子樹的的根指針。根指針。解決辦法：解決辦法：在訪問完該結(jié)點(diǎn)后，將該結(jié)點(diǎn)的指針保存在訪問完該結(jié)點(diǎn)后，將該結(jié)點(diǎn)的指針保存在在棧棧中，以便以后能通過它找到該結(jié)點(diǎn)的右子樹。中，以便以后能通過它找到該結(jié)點(diǎn)的右子樹。 在前序遍歷中，設(shè)要遍歷二叉樹的根指針為在前序遍歷中，設(shè)要遍歷二叉樹的根指針為root，則則有兩種可能：有兩種可能： 若若root!=NULL，則表明？如何處理？則表明？如何處理？ 若若root=NULL，則表明？如何處理？則表明？如何處理？前序遍歷前序遍歷非遞歸算法非遞歸算法6.5 二叉樹遍歷的

36、非遞歸算法二叉樹遍歷的非遞歸算法數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社訪問結(jié)點(diǎn)序列訪問結(jié)點(diǎn)序列:A棧棧S內(nèi)容內(nèi)容:B D A B前序遍歷的前序遍歷的非遞歸非遞歸實(shí)現(xiàn)實(shí)現(xiàn) ADBC6.5 二叉樹遍歷的非遞歸算法二叉樹遍歷的非遞歸算法數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社訪問結(jié)點(diǎn)序列訪問結(jié)點(diǎn)序列:A棧棧S內(nèi)容內(nèi)容:B D A前序遍歷的前序遍歷的非遞歸非遞歸實(shí)現(xiàn)實(shí)現(xiàn) ADBC D6.5 二叉樹遍歷的非遞歸算法二叉樹遍歷的非遞歸算法數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社訪問結(jié)點(diǎn)序列訪問結(jié)點(diǎn)序列:A棧棧S內(nèi)容內(nèi)容:B D C前序遍歷的前序遍歷的非遞歸

37、非遞歸實(shí)現(xiàn)實(shí)現(xiàn) ADBCC6.5 二叉樹遍歷的非遞歸算法二叉樹遍歷的非遞歸算法數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社1.棧棧s初始化；初始化；2.循環(huán)直到循環(huán)直到root為空且棧為空且棧s為空為空 2.1 當(dāng)當(dāng)root不空時(shí)循環(huán)不空時(shí)循環(huán)2.1.1 輸出輸出root-data; 2.1.2 將指針將指針root的值保存到棧中；的值保存到棧中； 2.1.3 繼續(xù)遍歷繼續(xù)遍歷root的左子樹的左子樹2.2 如果棧如果棧s不空，則不空，則2.2.1 將棧頂元素彈出至將棧頂元素彈出至root；2.2.2 準(zhǔn)備遍歷準(zhǔn)備遍歷root的右子樹；的右子樹； 前序遍歷前序遍歷非遞歸算法（偽代碼

38、）非遞歸算法（偽代碼）6.5 二叉樹遍歷的非遞歸算法二叉樹遍歷的非遞歸算法數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社前序遍歷前序遍歷非遞歸算法（偽代碼）非遞歸算法（偽代碼）void PreOrder(BiNode *root) top = -1; /采用順序棧，并假定不會(huì)發(fā)生上溢采用順序棧，并假定不會(huì)發(fā)生上溢 bt = root; while (bt != NULL | top != -1) while (bt != NULL) printf(bt-data); S+top = bt; /將根指針將根指針bt入棧入棧 bt = bt-lchild; if (top != -1)

39、/棧非空棧非空 bt = Stop-; bt = bt-rchild; 6.5 二叉樹遍歷的非遞歸算法二叉樹遍歷的非遞歸算法數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社中序遍歷中序遍歷非遞歸算法非遞歸算法在二叉樹的中序遍歷中，訪問結(jié)點(diǎn)的操作發(fā)生在該結(jié)點(diǎn)的在二叉樹的中序遍歷中，訪問結(jié)點(diǎn)的操作發(fā)生在該結(jié)點(diǎn)的左子樹遍歷完畢并準(zhǔn)備遍歷右子樹時(shí)，所以，在遍歷過程左子樹遍歷完畢并準(zhǔn)備遍歷右子樹時(shí)，所以，在遍歷過程中遇到某結(jié)點(diǎn)時(shí)并不能立即訪問它，而是將它壓棧，等到中遇到某結(jié)點(diǎn)時(shí)并不能立即訪問它，而是將它壓棧，等到它的左子樹遍歷完畢后，再從棧中彈出并訪問之。中序遍它的左子樹遍歷完畢后，再從棧中彈出

40、并訪問之。中序遍歷的非遞歸算法只需將前序遍歷的非遞歸算法中的輸出語歷的非遞歸算法只需將前序遍歷的非遞歸算法中的輸出語句句coutdata移到移到bt = stop-之后即可。之后即可。 6.5 二叉樹遍歷的非遞歸算法二叉樹遍歷的非遞歸算法數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社中序遍歷中序遍歷非遞歸算法非遞歸算法void InOrder(BiNode *root) top = -1; /采用順序棧，并假定不會(huì)發(fā)生上溢采用順序棧，并假定不會(huì)發(fā)生上溢 bt = root; while (bt != NULL | top != -1) while (bt != NULL) S+top

41、 = bt; /將根指針將根指針bt入棧入棧 bt = bt-lchild; if (top != -1) /棧非空棧非空 bt = Stop-; printf(root-data); bt = bt-rchild; 6.5 二叉樹遍歷的非遞歸算法二叉樹遍歷的非遞歸算法數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社后序遍歷后序遍歷非遞歸算法非遞歸算法在后序遍歷過程中，結(jié)點(diǎn)要入兩次棧，出兩次棧：在后序遍歷過程中，結(jié)點(diǎn)要入兩次棧，出兩次棧： 第一次出棧：只遍歷完左子樹，該結(jié)點(diǎn)不出棧，利用棧頂?shù)谝淮纬鰲＃褐槐闅v完左子樹，該結(jié)點(diǎn)不出棧，利用棧頂結(jié)點(diǎn)找到它的右子樹，準(zhǔn)備遍歷它的右子樹；結(jié)點(diǎn)找到

42、它的右子樹，準(zhǔn)備遍歷它的右子樹； 第二次出棧：遍歷完右子樹，將該結(jié)點(diǎn)出棧，并訪問它。第二次出棧：遍歷完右子樹，將該結(jié)點(diǎn)出棧，并訪問它。因此，為了區(qū)別同一個(gè)結(jié)點(diǎn)的兩次出棧，設(shè)置標(biāo)志因此，為了區(qū)別同一個(gè)結(jié)點(diǎn)的兩次出棧，設(shè)置標(biāo)志flag。棧元素類型定義如下：棧元素類型定義如下：typedef struct BiNode *ptr; int flag; element; /1表示第表示第1次出棧，次出棧，2表示第表示第2次出棧次出棧6.5 二叉樹遍歷的非遞歸算法二叉樹遍歷的非遞歸算法數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社后序遍歷后序遍歷非遞歸算法非遞歸算法設(shè)根指針為設(shè)根指針為bt，則

43、可能有以下兩種情況：，則可能有以下兩種情況： 若若bt不等于不等于NULL，則，則bt及標(biāo)志及標(biāo)志flag（置為（置為1）入棧，遍歷）入棧，遍歷其左子樹；其左子樹； 若若bt等于等于NULL，此時(shí)若?？眨瑒t整個(gè)遍歷結(jié)束；若棧不，此時(shí)若?？?，則整個(gè)遍歷結(jié)束；若棧不空，則表明棧頂結(jié)點(diǎn)的左子樹或右子樹已遍歷完畢。若棧頂空，則表明棧頂結(jié)點(diǎn)的左子樹或右子樹已遍歷完畢。若棧頂結(jié)點(diǎn)的標(biāo)志結(jié)點(diǎn)的標(biāo)志flag = 1，則表明棧頂結(jié)點(diǎn)的左子樹已遍歷完畢，則表明棧頂結(jié)點(diǎn)的左子樹已遍歷完畢，將將flag修改為修改為2，并遍歷棧頂結(jié)點(diǎn)的右子樹；若棧頂結(jié)點(diǎn)的標(biāo)，并遍歷棧頂結(jié)點(diǎn)的右子樹；若棧頂結(jié)點(diǎn)的標(biāo)志志flag = 2，

44、則表明棧頂結(jié)點(diǎn)的右子樹也遍歷完畢，輸出棧頂，則表明棧頂結(jié)點(diǎn)的右子樹也遍歷完畢，輸出棧頂結(jié)點(diǎn)。結(jié)點(diǎn)。6.5 二叉樹遍歷的非遞歸算法二叉樹遍歷的非遞歸算法數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社后序遍歷后序遍歷非遞歸算法非遞歸算法void PostOrder(BiNode *root) element Sn, top = -1; bt = root; while (bt != NULL | top != -1) while (bt != NULL) top+; Stop.ptr = bt; Stop.flag = 1; /root連同標(biāo)志連同標(biāo)志flag入棧入棧 bt = bt-l

45、child; while (top != -1 & Stop.flag = 2) bt = Stop-.ptr; printf(bt-data); if (top != -1) Stop.flag = 2; bt = stop.ptr-rchild; 6.5 二叉樹遍歷的非遞歸算法二叉樹遍歷的非遞歸算法數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社是哪些樹結(jié)構(gòu)的是哪些樹結(jié)構(gòu)的存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)? ?樹和二叉樹之間具有對(duì)應(yīng)關(guān)系樹和二叉樹之間具有對(duì)應(yīng)關(guān)系A(chǔ)EBCFDGA BCED F GABCDEFG6.6 樹、森林與二叉樹的轉(zhuǎn)換樹、森林與二叉樹的轉(zhuǎn)換數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電

46、子工業(yè)出版社電子工業(yè)出版社樹和二叉樹之間的對(duì)應(yīng)關(guān)系樹和二叉樹之間的對(duì)應(yīng)關(guān)系 樹：兄弟關(guān)系樹：兄弟關(guān)系二叉樹：雙親和右孩子二叉樹：雙親和右孩子 樹：雙親和長子樹：雙親和長子二叉樹：雙親和左孩子二叉樹：雙親和左孩子AEBCFDGABCDEFG6.6 樹、森林與二叉樹的轉(zhuǎn)換樹、森林與二叉樹的轉(zhuǎn)換數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社6.6 樹、森林與二叉樹的轉(zhuǎn)換樹、森林與二叉樹的轉(zhuǎn)換 1.兄弟加線兄弟加線.樹和二叉樹之間的對(duì)應(yīng)關(guān)系樹和二叉樹之間的對(duì)應(yīng)關(guān)系A(chǔ)BCDEFG數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社2.保留雙親與第一保留雙親與第一孩子連線孩子連線,刪去與刪去

47、與其他孩子的連線其他孩子的連線.ABCDEFG樹和二叉樹之間的對(duì)應(yīng)關(guān)系樹和二叉樹之間的對(duì)應(yīng)關(guān)系 1.兄弟加線兄弟加線.6.6 樹、森林與二叉樹的轉(zhuǎn)換樹、森林與二叉樹的轉(zhuǎn)換數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社3.順時(shí)針轉(zhuǎn)動(dòng)順時(shí)針轉(zhuǎn)動(dòng),使之使之層次分明層次分明.樹和二叉樹之間的對(duì)應(yīng)關(guān)系樹和二叉樹之間的對(duì)應(yīng)關(guān)系2.保留雙親與第一保留雙親與第一孩子連線孩子連線,刪去與刪去與其他孩子的連線其他孩子的連線. 1.兄弟加線兄弟加線.ABCDEFG6.6 樹、森林與二叉樹的轉(zhuǎn)換樹、森林與二叉樹的轉(zhuǎn)換數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社3.順時(shí)針轉(zhuǎn)動(dòng)順時(shí)針轉(zhuǎn)動(dòng),使之使之層

48、次分明層次分明.樹和二叉樹之間的對(duì)應(yīng)關(guān)系樹和二叉樹之間的對(duì)應(yīng)關(guān)系2.保留雙親與第一保留雙親與第一孩子連線孩子連線,刪去與刪去與其他孩子的連線其他孩子的連線. 1.兄弟加線兄弟加線.GDABECF6.6 樹、森林與二叉樹的轉(zhuǎn)換樹、森林與二叉樹的轉(zhuǎn)換數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社樹轉(zhuǎn)換為二叉樹樹轉(zhuǎn)換為二叉樹 加線加線樹中所有相鄰兄弟之間加一條連線。樹中所有相鄰兄弟之間加一條連線。 去線去線對(duì)樹中的每個(gè)結(jié)點(diǎn)，只保留它與第一個(gè)對(duì)樹中的每個(gè)結(jié)點(diǎn)，只保留它與第一個(gè)孩子結(jié)點(diǎn)之間的連線，刪去它與其它孩子結(jié)點(diǎn)之間孩子結(jié)點(diǎn)之間的連線，刪去它與其它孩子結(jié)點(diǎn)之間的連線。的連線。 層次調(diào)整層次

49、調(diào)整以根結(jié)點(diǎn)為軸心，將樹順時(shí)針轉(zhuǎn)動(dòng)以根結(jié)點(diǎn)為軸心，將樹順時(shí)針轉(zhuǎn)動(dòng)一定的角度，使之層次分明。一定的角度，使之層次分明。 6.6 樹、森林與二叉樹的轉(zhuǎn)換樹、森林與二叉樹的轉(zhuǎn)換數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社CBEDFGAABEFCDG前序遍歷前序遍歷AEBCFDGABEFCDG前序遍歷前序遍歷6.6 樹、森林與二叉樹的轉(zhuǎn)換樹、森林與二叉樹的轉(zhuǎn)換數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社EFBCGDA后序遍歷后序遍歷EFBCGDA中序遍歷中序遍歷CBEDFGAAEBCFDG6.6 樹、森林與二叉樹的轉(zhuǎn)換樹、森林與二叉樹的轉(zhuǎn)換數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出

50、版社電子工業(yè)出版社森林轉(zhuǎn)換為二叉樹森林轉(zhuǎn)換為二叉樹 將森林中的每棵樹轉(zhuǎn)換成二叉樹；將森林中的每棵樹轉(zhuǎn)換成二叉樹； 從第二棵二叉樹開始，依次把后一棵二叉樹的根從第二棵二叉樹開始，依次把后一棵二叉樹的根結(jié)點(diǎn)作為前一棵二叉樹根結(jié)點(diǎn)結(jié)點(diǎn)作為前一棵二叉樹根結(jié)點(diǎn)的右孩子，當(dāng)所有二的右孩子，當(dāng)所有二叉樹連起來后，此時(shí)所得到的二叉樹就是由森林轉(zhuǎn)叉樹連起來后，此時(shí)所得到的二叉樹就是由森林轉(zhuǎn)換得到的二叉樹換得到的二叉樹。6.6 樹、森林與二叉樹的轉(zhuǎn)換樹、森林與二叉樹的轉(zhuǎn)換數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社FEDCBAGHIJBAFEDCGHIKKIFEHABCGD6.6 樹、森林與二叉樹的轉(zhuǎn)

51、換樹、森林與二叉樹的轉(zhuǎn)換數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社二叉樹轉(zhuǎn)換為樹或森林二叉樹轉(zhuǎn)換為樹或森林 加線加線若某結(jié)點(diǎn)若某結(jié)點(diǎn)x是其雙親是其雙親y的左孩子，則把結(jié)點(diǎn)的左孩子，則把結(jié)點(diǎn)x的右孩子、右孩子的右孩子、的右孩子、右孩子的右孩子、，都與結(jié)點(diǎn)，都與結(jié)點(diǎn)y用線連用線連起來；起來； 去線去線刪去原二叉樹中所有的雙親結(jié)點(diǎn)與右孩子結(jié)刪去原二叉樹中所有的雙親結(jié)點(diǎn)與右孩子結(jié)點(diǎn)的連線；點(diǎn)的連線； 層次調(diào)整層次調(diào)整整理由、兩步所得到的樹或森林，整理由、兩步所得到的樹或森林，使之層次分明。使之層次分明。 6.6 樹、森林與二叉樹的轉(zhuǎn)換樹、森林與二叉樹的轉(zhuǎn)換數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子

52、工業(yè)出版社電子工業(yè)出版社FHGEAICDBFHGDCEBAIFEDCBAHGI加線加線去線去線層次調(diào)整層次調(diào)整IHGBCDAFE6.6 樹、森林與二叉樹的轉(zhuǎn)換樹、森林與二叉樹的轉(zhuǎn)換數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社森林的遍歷森林的遍歷森林有兩種遍歷方法：森林有兩種遍歷方法：前序（根）遍歷：前序遍歷森林即為前序遍歷森前序（根）遍歷：前序遍歷森林即為前序遍歷森林中的每一棵樹。林中的每一棵樹。 后序（根）遍歷：后序遍歷森林即為后序遍歷森后序（根）遍歷：后序遍歷森林即為后序遍歷森林中的每一棵樹。林中的每一棵樹。 6.6 樹、森林與二叉樹的轉(zhuǎn)換樹、森林與二叉樹的轉(zhuǎn)換數(shù)據(jù)結(jié)構(gòu)與算法數(shù)

53、據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社【問題問題】已知已知Windows操作系統(tǒng)的文件目錄結(jié)構(gòu)，請(qǐng)統(tǒng)計(jì)每個(gè)操作系統(tǒng)的文件目錄結(jié)構(gòu)，請(qǐng)統(tǒng)計(jì)每個(gè)文件和文件夾的大小。文件和文件夾的大小。【算法算法】可以用樹結(jié)構(gòu)表示這種文件目錄結(jié)構(gòu)，輸出即是對(duì)樹可以用樹結(jié)構(gòu)表示這種文件目錄結(jié)構(gòu)，輸出即是對(duì)樹進(jìn)行后序遍歷的結(jié)果，括號(hào)內(nèi)的數(shù)字代表文件大小，其中文件進(jìn)行后序遍歷的結(jié)果，括號(hào)內(nèi)的數(shù)字代表文件大小，其中文件的大小即是文件本身的大小，文件夾的大小是本身大小和目錄的大小即是文件本身的大小，文件夾的大小是本身大小和目錄下所有文件的大小之和。下所有文件的大小之和。設(shè)樹用孩子兄弟表示法存儲(chǔ)，存儲(chǔ)結(jié)構(gòu)定義如下：設(shè)樹用孩子

54、兄弟表示法存儲(chǔ)，存儲(chǔ)結(jié)構(gòu)定義如下：typedef struct FSNode char name32; /文件（或文件夾）名文件（或文件夾）名 int size; /文件（或文件夾）大小文件（或文件夾）大小 FSNode *firstchild, *rightsib; /指向最左孩子和右兄弟指向最左孩子和右兄弟 FSNode;6.7 應(yīng)用舉例應(yīng)用舉例文件系統(tǒng)文件系統(tǒng)數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社【算法算法】首先需建立一棵樹。這里采用按層次序建立樹的孩子首先需建立一棵樹。這里采用按層次序建立樹的孩子兄弟表示法存儲(chǔ)結(jié)構(gòu)，算法如下：兄弟表示法存儲(chǔ)結(jié)構(gòu)，算法如下：6.7 應(yīng)用

55、舉例應(yīng)用舉例文件系統(tǒng)文件系統(tǒng)數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社相關(guān)概念相關(guān)概念葉子結(jié)點(diǎn)的權(quán)值：葉子結(jié)點(diǎn)的權(quán)值：對(duì)葉子結(jié)點(diǎn)賦予的一個(gè)有意義的對(duì)葉子結(jié)點(diǎn)賦予的一個(gè)有意義的數(shù)值量。數(shù)值量。 二叉樹的帶權(quán)路徑長度：二叉樹的帶權(quán)路徑長度：設(shè)二叉樹具有設(shè)二叉樹具有n個(gè)帶權(quán)值的個(gè)帶權(quán)值的葉子結(jié)點(diǎn)，從根結(jié)點(diǎn)到各個(gè)葉子結(jié)點(diǎn)的路徑長度與葉子結(jié)點(diǎn)，從根結(jié)點(diǎn)到各個(gè)葉子結(jié)點(diǎn)的路徑長度與相相應(yīng)葉子結(jié)點(diǎn)權(quán)值的乘積之和。應(yīng)葉子結(jié)點(diǎn)權(quán)值的乘積之和。 記為：記為：WPL=6.7 應(yīng)用舉例應(yīng)用舉例哈夫曼樹哈夫曼樹 nkkklw1第第k個(gè)葉子的權(quán)值；個(gè)葉子的權(quán)值；從根結(jié)點(diǎn)到第從根結(jié)點(diǎn)到第k個(gè)葉子的路徑長度個(gè)葉子

56、的路徑長度數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社哈夫曼樹：哈夫曼樹：給定一組具有確定權(quán)值的給定一組具有確定權(quán)值的葉子葉子結(jié)點(diǎn)，帶權(quán)結(jié)點(diǎn)，帶權(quán)路徑路徑長度最小的二叉樹長度最小的二叉樹。例：給定例：給定4個(gè)葉子結(jié)點(diǎn)，其權(quán)值分別為個(gè)葉子結(jié)點(diǎn)，其權(quán)值分別為2，3，4，7，可以構(gòu)造出形狀不同的可以構(gòu)造出形狀不同的多個(gè)二叉樹。多個(gè)二叉樹。 WPL=32 WPL=41 WPL=302347234774236.7 應(yīng)用舉例應(yīng)用舉例哈夫曼樹哈夫曼樹數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社哈夫曼樹的特點(diǎn)：哈夫曼樹的特點(diǎn)：1. 權(quán)值越大的葉子結(jié)點(diǎn)越靠近根結(jié)點(diǎn)，而權(quán)值越小的權(quán)值越大的

57、葉子結(jié)點(diǎn)越靠近根結(jié)點(diǎn)，而權(quán)值越小的葉子結(jié)點(diǎn)越遠(yuǎn)離根結(jié)點(diǎn)。葉子結(jié)點(diǎn)越遠(yuǎn)離根結(jié)點(diǎn)。 2. 只有度為只有度為0（葉子結(jié)點(diǎn)）和度為（葉子結(jié)點(diǎn)）和度為2（分支結(jié)點(diǎn)）的結(jié)（分支結(jié)點(diǎn)）的結(jié)點(diǎn)，不存在度為點(diǎn)，不存在度為1的結(jié)點(diǎn)的結(jié)點(diǎn). 2347WPL=32 WPL=41 WPL=30234774236.7 應(yīng)用舉例應(yīng)用舉例哈夫曼樹哈夫曼樹數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社哈夫曼算法基本思想：哈夫曼算法基本思想： 初始化初始化：由給定的：由給定的n個(gè)權(quán)值個(gè)權(quán)值w1，w2，wn構(gòu)造構(gòu)造n棵只有一個(gè)根結(jié)點(diǎn)的二叉樹，從而得到一個(gè)二叉樹棵只有一個(gè)根結(jié)點(diǎn)的二叉樹，從而得到一個(gè)二叉樹集合集合FT1，T

58、2，Tn； 選取與合并選取與合并：在：在F中選取根結(jié)點(diǎn)的權(quán)值中選取根結(jié)點(diǎn)的權(quán)值最小最小的兩的兩棵二叉樹分別作為左、右子樹構(gòu)造一棵新的二叉樹棵二叉樹分別作為左、右子樹構(gòu)造一棵新的二叉樹，這棵新二叉樹的根結(jié)點(diǎn)的權(quán)值為其左、右子樹根，這棵新二叉樹的根結(jié)點(diǎn)的權(quán)值為其左、右子樹根結(jié)點(diǎn)的權(quán)值之和；結(jié)點(diǎn)的權(quán)值之和； 刪除與加入刪除與加入：在：在F中刪除作為左、右子樹的兩棵中刪除作為左、右子樹的兩棵二叉樹，并將新建立的二叉樹加入到二叉樹，并將新建立的二叉樹加入到F中；中； 重復(fù)重復(fù)、兩步，當(dāng)集合、兩步，當(dāng)集合F中只剩下一棵二叉樹中只剩下一棵二叉樹時(shí)，這棵二叉樹便是哈夫曼樹。時(shí)，這棵二叉樹便是哈夫曼樹。 6.7

59、 應(yīng)用舉例應(yīng)用舉例哈夫曼樹哈夫曼樹數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社第第1步：初始化步：初始化W2，4，5 ，3 哈夫曼樹的構(gòu)造過程哈夫曼樹的構(gòu)造過程3524第第2步：選取與合并步：選取與合并32 5第第3步：刪除與加入步：刪除與加入5432 56.7 應(yīng)用舉例應(yīng)用舉例哈夫曼樹哈夫曼樹數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社W2，4，5 ，3 哈夫曼樹的構(gòu)造過程哈夫曼樹的構(gòu)造過程重復(fù)第重復(fù)第2步步5432 554 9重復(fù)第重復(fù)第3步步 554 9326.7 應(yīng)用舉例應(yīng)用舉例哈夫曼樹哈夫曼樹數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社W2，3，4

60、，5 哈夫曼樹的構(gòu)造過程哈夫曼樹的構(gòu)造過程重復(fù)第重復(fù)第2步步重復(fù)第重復(fù)第3步步 554 932 554 932146.7 應(yīng)用舉例應(yīng)用舉例哈夫曼樹哈夫曼樹數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社哈夫曼算法的存儲(chǔ)結(jié)構(gòu)哈夫曼算法的存儲(chǔ)結(jié)構(gòu) 1. 設(shè)置一個(gè)數(shù)組設(shè)置一個(gè)數(shù)組huffTree2n- -1保存哈夫曼樹中各保存哈夫曼樹中各點(diǎn)的點(diǎn)的信息，數(shù)組元素的結(jié)點(diǎn)結(jié)構(gòu)信息，數(shù)組元素的結(jié)點(diǎn)結(jié)構(gòu) 。 weight lchild rchild parent其中：其中：weight：權(quán)值域，保存該結(jié)點(diǎn)的權(quán)值；：權(quán)值域，保存該結(jié)點(diǎn)的權(quán)值； lchild：指針域，結(jié)點(diǎn)的左孩子結(jié)點(diǎn)在數(shù)組中的下標(biāo)；：指針域，結(jié)點(diǎn)的左孩子結(jié)點(diǎn)在