第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)樹的存儲結(jié)構(gòu)樹的存儲結(jié)構(gòu)二叉樹的邏輯結(jié)構(gòu)二叉樹的邏輯結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu)及實現(xiàn)二叉樹的存儲結(jié)構(gòu)及實現(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 引言引言如何存儲這個文件目錄結(jié)構(gòu)并統(tǒng)計大小呢？如何存儲這個文件目錄結(jié)構(gòu)并統(tǒng)計大小呢？數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社例例6-2 二叉表示樹二叉表示樹6.1 引言引言如何建立二叉表示樹并進行計算呢？如何建立二叉表示樹并進行計算呢？一個算術(shù)表達式可以用二叉樹來表示，這樣的二叉樹稱為一個算術(shù)表達式可以用二叉樹來表示，這樣的二叉樹稱為二叉表示樹。表達式二叉表示樹。表達式(A+B)*(C+D*E) 的二叉表示樹如下：的二叉表示樹如下： 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社樹的定義樹的定義樹：樹：n（n0）個

3、個結(jié)點結(jié)點的有限的有限集合集合。當。當n0時，稱為時，稱為空樹；任意一棵非空樹滿足以下條件：空樹；任意一棵非空樹滿足以下條件： 有且僅有一個特定的稱為有且僅有一個特定的稱為根根的結(jié)點；的結(jié)點； 當當n1時，除根結(jié)點之外的其余結(jié)點被分成時，除根結(jié)點之外的其余結(jié)點被分成m（m0）個個互不相交互不相交的有限集合的有限集合T1, ,T2, , ,Tm，其中其中每個集合又是一棵樹，并稱為這個根結(jié)點的每個集合又是一棵樹，并稱為這個根結(jié)點的子樹子樹。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)一個非樹結(jié)構(gòu)一個非樹結(jié)構(gòu) (c)一個非樹結(jié)構(gòu)一個非樹結(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é)點的度：結(jié)點的度：結(jié)點所擁有的子樹的個數(shù)。結(jié)點所擁有的子樹的個數(shù)。p 樹的度：樹的度：樹中各結(jié)點度的最大值。樹中各結(jié)點度的最

5、大值。CGBDEFKLHMIJA6.2 樹的邏輯結(jié)構(gòu)樹的邏輯結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社p 葉子結(jié)點：葉子結(jié)點：度為度為0的結(jié)點，也稱為終端結(jié)點。的結(jié)點，也稱為終端結(jié)點。p 分支結(jié)點：分支結(jié)點：度不為度不為0的結(jié)點，也稱為非終端結(jié)點。的結(jié)點，也稱為非終端結(jié)點。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é)點子樹的根結(jié)點稱為這個結(jié)點的樹中某結(jié)點子樹的根結(jié)點稱為這個結(jié)點的孩孩子結(jié)點子結(jié)點，這個結(jié)點稱為它孩子結(jié)點的，這個結(jié)點稱為它孩子結(jié)點的雙

6、親結(jié)點雙親結(jié)點；p 兄弟：兄弟：具有同一個雙親的孩子結(jié)點互稱為兄弟。具有同一個雙親的孩子結(jié)點互稱為兄弟。 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é)點序列如果樹的結(jié)點序列n1, n2, , nk有如下關(guān)系：結(jié)點有如下關(guān)系：結(jié)點ni是是ni+1的雙親（的雙親（1=idata); /訪問根結(jié)點的數(shù)據(jù)域訪問根結(jié)點的數(shù)據(jù)域 PreOrder(root-lchild); /前序遞歸遍歷前序遞歸遍歷root的左子樹的左子樹 PreOrder(root-rchild); /前序遞歸遍歷前

7、序遞歸遍歷root的右子樹的右子樹 6.5 二叉樹的存儲結(jié)構(gòu)二叉樹的存儲結(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é)點的數(shù)據(jù)域訪問根結(jié)點的數(shù)據(jù)域 InOrder(root-rchild); /中序遞歸遍歷中序遞歸遍歷root的右子樹的右子樹 6.5

8、二叉樹的存儲結(jié)構(gòu)二叉樹的存儲結(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é)點的數(shù)據(jù)域訪問根結(jié)點的數(shù)據(jù)域 6.5 二叉樹的存儲結(jié)構(gòu)二叉樹的存儲結(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 二叉樹的存儲結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社層序遍歷層序遍歷 隊列隊列Q初始化；初始化； 2. 如果二叉樹非空，將根指針入隊；如果二叉樹非空，將根指針入隊；3. 循環(huán)直到隊列循環(huán)直到隊列Q為空為空 3.1 q=隊列隊列Q的隊頭元素出隊；的隊頭元素出隊； 3.2 訪問結(jié)點訪問結(jié)點q的數(shù)據(jù)域；的數(shù)據(jù)域； 3.3 若結(jié)點若結(jié)點q存在左孩子，則將左孩子指針入隊；存在左孩子，則將左孩子指針入隊； 3.4 若結(jié)點若

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

11、1; /根結(jié)點為前序序列的第根結(jié)點為前序序列的第1個元素個元素 m = pos(prei1, pin, i2); /查找根結(jié)點在中序序列中的位置查找根結(jié)點在中序序列中的位置 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è)計練習二叉樹算法設(shè)計練習 遍歷二叉樹是二叉樹各種操作的基礎(chǔ)，遍歷算法遍歷二叉樹是二叉樹各種操作的基礎(chǔ)，遍歷算法中對每個結(jié)點的訪問操作可以是多種形式及多個操中對每個結(jié)點的訪問操作可以是多種形式及多個操作，根據(jù)遍歷算法的框架，適當修改訪問操作的內(nèi)作，根據(jù)遍歷算法的框架，適當修改訪問操作的內(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è)計練習二叉樹算法設(shè)計練習設(shè)計算法求二叉樹的結(jié)點個數(shù)。設(shè)計算法求二叉樹的結(jié)點個數(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è)計練習二叉樹算法設(shè)計練習設(shè)計算法按前序次序打印二叉

14、樹中的葉子結(jié)點。設(shè)計算法按前序次序打印二叉樹中的葉子結(jié)點。 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è)計練習二叉樹算法設(shè)計練習設(shè)計算法求二叉樹的深度。設(shè)計算法求二叉樹的深度。 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è)計練習二叉樹算法設(shè)計練習設(shè)計算法求樹中結(jié)點設(shè)計算法求樹中結(jié)點 x 的第的第 i 個孩子。個孩子。 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é)點的雙親？在二叉鏈表中，如何求某結(jié)點的雙親？6.5 二叉樹的存儲結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社三叉鏈表三叉鏈表 lchild dataparent rchild在二叉鏈表的基礎(chǔ)上增加了一個指向雙親的指針域。在二叉鏈表的基礎(chǔ)上增加了一個指向雙親的指針域。結(jié)點結(jié)構(gòu)

17、結(jié)點結(jié)構(gòu)其中：其中：data、lchild和和rchild三個域的含義同二叉鏈表三個域的含義同二叉鏈表的結(jié)點結(jié)構(gòu)；的結(jié)點結(jié)構(gòu)；parent域為域為指向該結(jié)點的雙親結(jié)點的指針。指向該結(jié)點的雙親結(jié)點的指針。 6.5 二叉樹的存儲結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社ABCDEFGABDEFCG三叉鏈表三叉鏈表6.5 二叉樹的存儲結(jié)構(gòu)二叉樹的存儲結(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 二叉樹的存儲結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社線索鏈表線索鏈表如何保存二叉樹的某種遍歷序列？如何保存二叉樹的某種遍歷序列？ABCDEFG中序遍歷序列：中序遍歷序列：D G B A F C F如果二叉樹如果二叉樹不不改變，如何保存？改變，如何保存？順順序序存存儲儲D G B A F C F6.5 二叉樹的存儲結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社線索鏈表線索鏈表如何保存二叉樹的某種遍歷序列？如何保存二叉樹的某種遍歷序列？ABCDEFG中序遍歷序列：中

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

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

21、a child rtag0: lchild指向該結(jié)點的左孩子指向該結(jié)點的左孩子1: lchild指向該結(jié)點的前驅(qū)結(jié)點指向該結(jié)點的前驅(qū)結(jié)點0: rchild指向該結(jié)點的右孩子指向該結(jié)點的右孩子1: rchild指向該結(jié)點的后繼結(jié)點指向該結(jié)點的后繼結(jié)點ltag=rtag=結(jié)點結(jié)構(gòu)結(jié)點結(jié)構(gòu)線索鏈表線索鏈表6.5 二叉樹的存儲結(jié)構(gòu)二叉樹的存儲結(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é)點結(jié)構(gòu)定義線索鏈表的結(jié)點結(jié)構(gòu) DataType data; ThrNode *lchild, *rchild; flag ltag, rtag; ThrNode, *root; /root為指向線索鏈表的頭指針為指向線索鏈表的頭指針線索鏈表線索鏈表 ltag lchild data child rtag結(jié)點結(jié)構(gòu)結(jié)點結(jié)構(gòu)6.5 二叉樹的存儲結(jié)構(gòu)二叉樹的存儲結(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 二叉樹的存儲結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社FABDCEG中序線索二叉樹中序線索二叉樹線索二叉樹線索二叉樹中序序列：中序序列：D G B A E C F6.5 二叉樹的存儲結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社分析：分析：建立線索鏈表，實質(zhì)上就是將二叉鏈表中的空建立線索鏈表，實質(zhì)上就是將二叉鏈表中的空指針改為指向前驅(qū)或后繼的線索，而前驅(qū)或后繼的信指針改為指向前驅(qū)或后繼的線索，而

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

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

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

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

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

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

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

31、點若結(jié)點pre右標志為右標志為1，則為，則為pre加上后繼線索；加上后繼線索； 2.3.4 令令pre指向剛剛訪問的結(jié)點指向剛剛訪問的結(jié)點root； 2.4 對對root的右子樹建立線索。的右子樹建立線索。6.5 二叉樹的存儲結(jié)構(gòu)二叉樹的存儲結(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) /對對root的左指針進行處理的左指針進行處理 root-ltag = 1; root-lchild = pre; /設(shè)置設(shè)置pre的前驅(qū)線索的前驅(qū)線索 if (root-rchild = NULL) /對對root的右指針進行處理的右指針進行處理 root-rtag = 1; if (pre-rtag = 1) pre-rchild = root; /設(shè)置設(shè)置pre的后繼線索的后繼線索 pre = root; inThrBiTree(root-rchild); /遞歸處理遞歸處理root的右子樹的右子樹6.5 二叉樹的存儲結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu)建立線索鏈表

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

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

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

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

37、非遞歸實現(xiàn)實現(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 當當root不空時循環(huán)不空時循環(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 準備遍歷準備遍歷root的右子樹；的右子樹； 前序遍歷前序遍歷非遞歸算法（偽代碼

38、）非遞歸算法（偽代碼）6.5 二叉樹遍歷的非遞歸算法二叉樹遍歷的非遞歸算法數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社前序遍歷前序遍歷非遞歸算法（偽代碼）非遞歸算法（偽代碼）void PreOrder(BiNode *root) top = -1; /采用順序棧，并假定不會發(fā)生上溢采用順序棧，并假定不會發(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é)點的操作發(fā)生在該結(jié)點的在二叉樹的中序遍歷中，訪問結(jié)點的操作發(fā)生在該結(jié)點的左子樹遍歷完畢并準備遍歷右子樹時，所以，在遍歷過程左子樹遍歷完畢并準備遍歷右子樹時，所以，在遍歷過程中遇到某結(jié)點時并不能立即訪問它，而是將它壓棧，等到中遇到某結(jié)點時并不能立即訪問它，而是將它壓棧，等到它的左子樹遍歷完畢后，再從棧中彈出并訪問之。中序遍它的左子樹遍歷完畢后，再從棧中彈出

40、并訪問之。中序遍歷的非遞歸算法只需將前序遍歷的非遞歸算法中的輸出語歷的非遞歸算法只需將前序遍歷的非遞歸算法中的輸出語句句coutdata移到移到bt = stop-之后即可。之后即可。 6.5 二叉樹遍歷的非遞歸算法二叉樹遍歷的非遞歸算法數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社中序遍歷中序遍歷非遞歸算法非遞歸算法void InOrder(BiNode *root) top = -1; /采用順序棧，并假定不會發(fā)生上溢采用順序棧，并假定不會發(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é)點要入兩次棧，出兩次棧：在后序遍歷過程中，結(jié)點要入兩次棧，出兩次棧： 第一次出棧：只遍歷完左子樹，該結(jié)點不出棧，利用棧頂?shù)谝淮纬鰲＃褐槐闅v完左子樹，該結(jié)點不出棧，利用棧頂結(jié)點找到它的右子樹，準備遍歷它的右子樹；結(jié)點找到

42、它的右子樹，準備遍歷它的右子樹； 第二次出棧：遍歷完右子樹，將該結(jié)點出棧，并訪問它。第二次出棧：遍歷完右子樹，將該結(jié)點出棧，并訪問它。因此，為了區(qū)別同一個結(jié)點的兩次出棧，設(shè)置標志因此，為了區(qū)別同一個結(jié)點的兩次出棧，設(shè)置標志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及標志及標志flag（置為（置為1）入棧，遍歷）入棧，遍歷其左子樹；其左子樹； 若若bt等于等于NULL，此時若?？眨瑒t整個遍歷結(jié)束；若棧不，此時若?？眨瑒t整個遍歷結(jié)束；若棧不空，則表明棧頂結(jié)點的左子樹或右子樹已遍歷完畢。若棧頂空，則表明棧頂結(jié)點的左子樹或右子樹已遍歷完畢。若棧頂結(jié)點的標志結(jié)點的標志flag = 1，則表明棧頂結(jié)點的左子樹已遍歷完畢，則表明棧頂結(jié)點的左子樹已遍歷完畢，將將flag修改為修改為2，并遍歷棧頂結(jié)點的右子樹；若棧頂結(jié)點的標，并遍歷棧頂結(jié)點的右子樹；若棧頂結(jié)點的標志志flag = 2，

44、則表明棧頂結(jié)點的右子樹也遍歷完畢，輸出棧頂，則表明棧頂結(jié)點的右子樹也遍歷完畢，輸出棧頂結(jié)點。結(jié)點。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連同標志連同標志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)的存儲結(jié)構(gòu)存儲結(jié)構(gòu)? ?樹和二叉樹之間具有對應(yīng)關(guān)系樹和二叉樹之間具有對應(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è)出版社樹和二叉樹之間的對應(yīng)關(guān)系樹和二叉樹之間的對應(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.兄弟加線兄弟加線.樹和二叉樹之間的對應(yīng)關(guān)系樹和二叉樹之間的對應(yīng)關(guān)系A(chǔ)BCDEFG數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社2.保留雙親與第一保留雙親與第一孩子連線孩子連線,刪去與刪去

47、與其他孩子的連線其他孩子的連線.ABCDEFG樹和二叉樹之間的對應(yīng)關(guān)系樹和二叉樹之間的對應(yīng)關(guān)系 1.兄弟加線兄弟加線.6.6 樹、森林與二叉樹的轉(zhuǎn)換樹、森林與二叉樹的轉(zhuǎn)換數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法電子工業(yè)出版社電子工業(yè)出版社3.順時針轉(zhuǎn)動順時針轉(zhuǎn)動,使之使之層次分明層次分明.樹和二叉樹之間的對應(yīng)關(guān)系樹和二叉樹之間的對應(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.順時針轉(zhuǎn)動順時針轉(zhuǎn)動,使之使之層

48、次分明層次分明.樹和二叉樹之間的對應(yīng)關(guān)系樹和二叉樹之間的對應(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)換為二叉樹 加線加線樹中所有相鄰兄弟之間加一條連線。樹中所有相鄰兄弟之間加一條連線。 去線去線對樹中的每個結(jié)點，只保留它與第一個對樹中的每個結(jié)點，只保留它與第一個孩子結(jié)點之間的連線，刪去它與其它孩子結(jié)點之間孩子結(jié)點之間的連線，刪去它與其它孩子結(jié)點之間的連線。的連線。 層次調(diào)整層次

49、調(diào)整以根結(jié)點為軸心，將樹順時針轉(zhuǎn)動以根結(jié)點為軸心，將樹順時針轉(zhuǎn)動一定的角度，使之層次分明。一定的角度，使之層次分明。 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é)點作為前一棵二叉樹根結(jié)點結(jié)點作為前一棵二叉樹根結(jié)點的右孩子，當所有二的右孩子，當所有二叉樹連起來后，此時所得到的二叉樹就是由森林轉(zhuǎn)叉樹連起來后，此時所得到的二叉樹就是由森林轉(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é)點若某結(jié)點x是其雙親是其雙親y的左孩子，則把結(jié)點的左孩子，則把結(jié)點x的右孩子、右孩子的右孩子、的右孩子、右孩子的右孩子、，都與結(jié)點，都與結(jié)點y用線連用線連起來；起來； 去線去線刪去原二叉樹中所有的雙親結(jié)點與右孩子結(jié)刪去原二叉樹中所有的雙親結(jié)點與右孩子結(jié)點的連線；點的連線； 層次調(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)，請統(tǒng)計每個操作系統(tǒng)的文件目錄結(jié)構(gòu)，請統(tǒng)計每個文件和文件夾的大小。文件和文件夾的大小?！舅惴ㄋ惴ā靠梢杂脴浣Y(jié)構(gòu)表示這種文件目錄結(jié)構(gòu)，輸出即是對樹可以用樹結(jié)構(gòu)表示這種文件目錄結(jié)構(gòu)，輸出即是對樹進行后序遍歷的結(jié)果，括號內(nèi)的數(shù)字代表文件大小，其中文件進行后序遍歷的結(jié)果，括號內(nèi)的數(shù)字代表文件大小，其中文件的大小即是文件本身的大小，文件夾的大小是本身大小和目錄的大小即是文件本身的大小，文件夾的大小是本身大小和目錄下所有文件的大小之和。下所有文件的大小之和。設(shè)樹用孩子兄弟表示法存儲，存儲結(jié)構(gòu)定義如下：設(shè)樹用孩子

54、兄弟表示法存儲，存儲結(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è)出版社【算法算法】首先需建立一棵樹。這里采用按層次序建立樹的孩子首先需建立一棵樹。這里采用按層次序建立樹的孩子兄弟表示法存儲結(jié)構(gòu)，算法如下：兄弟表示法存儲結(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é)點的權(quán)值：葉子結(jié)點的權(quán)值：對葉子結(jié)點賦予的一個有意義的對葉子結(jié)點賦予的一個有意義的數(shù)值量。數(shù)值量。 二叉樹的帶權(quán)路徑長度：二叉樹的帶權(quán)路徑長度：設(shè)二叉樹具有設(shè)二叉樹具有n個帶權(quán)值的個帶權(quán)值的葉子結(jié)點，從根結(jié)點到各個葉子結(jié)點的路徑長度與葉子結(jié)點，從根結(jié)點到各個葉子結(jié)點的路徑長度與相相應(yīng)葉子結(jié)點權(quán)值的乘積之和。應(yīng)葉子結(jié)點權(quán)值的乘積之和。 記為：記為：WPL=6.7 應(yīng)用舉例應(yīng)用舉例哈夫曼樹哈夫曼樹 nkkklw1第第k個葉子的權(quán)值；個葉子的權(quán)值；從根結(jié)點到第從根結(jié)點到第k個葉子的路徑長度個葉子

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

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

58、2，Tn； 選取與合并選取與合并：在：在F中選取根結(jié)點的權(quán)值中選取根結(jié)點的權(quán)值最小最小的兩的兩棵二叉樹分別作為左、右子樹構(gòu)造一棵新的二叉樹棵二叉樹分別作為左、右子樹構(gòu)造一棵新的二叉樹，這棵新二叉樹的根結(jié)點的權(quán)值為其左、右子樹根，這棵新二叉樹的根結(jié)點的權(quán)值為其左、右子樹根結(jié)點的權(quán)值之和；結(jié)點的權(quán)值之和； 刪除與加入刪除與加入：在：在F中刪除作為左、右子樹的兩棵中刪除作為左、右子樹的兩棵二叉樹，并將新建立的二叉樹加入到二叉樹，并將新建立的二叉樹加入到F中；中； 重復(fù)重復(fù)、兩步，當集合、兩步，當集合F中只剩下一棵二叉樹中只剩下一棵二叉樹時，這棵二叉樹便是哈夫曼樹。時，這棵二叉樹便是哈夫曼樹。 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è)出版社哈夫曼算法的存儲結(jié)構(gòu)哈夫曼算法的存儲結(jié)構(gòu) 1. 設(shè)置一個數(shù)組設(shè)置一個數(shù)組huffTree2n- -1保存哈夫曼樹中各保存哈夫曼樹中各點的點的信息，數(shù)組元素的結(jié)點結(jié)構(gòu)信息，數(shù)組元素的結(jié)點結(jié)構(gòu) 。 weight lchild rchild parent其中：其中：weight：權(quán)值域，保存該結(jié)點的權(quán)值；：權(quán)值域，保存該結(jié)點的權(quán)值； lchild：指針域，結(jié)點的左孩子結(jié)點在數(shù)組中的下標；：指針域，結(jié)點的左孩子結(jié)點在