第6章 樹和二叉樹

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

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

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

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

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

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

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

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

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

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

11、1; /根結點為前序序列的第根結點為前序序列的第1個元素個元素 m = pos(prei1, pin, i2); /查找根結點在中序序列中的位置查找根結點在中序序列中的位置 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ù)結構與算法數(shù)據(jù)結

12、構與算法電子工業(yè)出版社電子工業(yè)出版社二叉樹算法設計練習二叉樹算法設計練習 遍歷二叉樹是二叉樹各種操作的基礎，遍歷算法遍歷二叉樹是二叉樹各種操作的基礎，遍歷算法中對每個結點的訪問操作可以是多種形式及多個操中對每個結點的訪問操作可以是多種形式及多個操作，根據(jù)遍歷算法的框架，適當修改訪問操作的內作，根據(jù)遍歷算法的框架，適當修改訪問操作的內容，可以派生出很多關于二叉樹的應用算法。容，可以派生出很多關于二叉樹的應用算法。 void InOrder ( (BiNode *root) ) if ( (root=NULL) ) return; else InOrder( (root-lchild) ); co

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

14、樹中的葉子結點。設計算法按前序次序打印二叉樹中的葉子結點。 void PreOrder(BiNode *root) if (root = NULL) return; else if (!root-lchild & !root-rchild) coutdata; PreOrder(root-lchild); PreOrder(root-rchild); 數(shù)據(jù)結構與算法數(shù)據(jù)結構與算法電子工業(yè)出版社電子工業(yè)出版社二叉樹算法設計練習二叉樹算法設計練習設計算法求二叉樹的深度。設計算法求二叉樹的深度。 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ù)結構與算法數(shù)據(jù)結構與算法電子工業(yè)出版社電子工業(yè)出版社二叉樹算法設計練習二叉樹算法設計練習設計算法求樹中結點設計算法求樹中結點 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ù)結構與算法數(shù)據(jù)結構與算法電子工業(yè)出版社電子工業(yè)出版社三叉鏈表三叉鏈表GFEDBAABCDEFGC在二叉鏈表中，如何求某結點的雙親？在二叉鏈表中，如何求某結點的雙親？6.5 二叉樹的存儲結構二叉樹的存儲結構數(shù)據(jù)結構與算法數(shù)據(jù)結構與算法電子工業(yè)出版社電子工業(yè)出版社三叉鏈表三叉鏈表 lchild dataparent rchild在二叉鏈表的基礎上增加了一個指向雙親的指針域。在二叉鏈表的基礎上增加了一個指向雙親的指針域。結點結構

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

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

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

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

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

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

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

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

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

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

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

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

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

31、點若結點pre右標志為右標志為1，則為，則為pre加上后繼線索；加上后繼線索； 2.3.4 令令pre指向剛剛訪問的結點指向剛剛訪問的結點root； 2.4 對對root的右子樹建立線索。的右子樹建立線索。6.5 二叉樹的存儲結構二叉樹的存儲結構建立線索鏈表建立線索鏈表數(shù)據(jù)結構與算法數(shù)據(jù)結構與算法電子工業(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; /設置設置pre的前驅線索的前驅線索 if (root-rchild = NULL) /對對root的右指針進行處理的右指針進行處理 root-rtag = 1; if (pre-rtag = 1) pre-rchild = root; /設置設置pre的后繼線索的后繼線索 pre = root; inThrBiTree(root-rchild); /遞歸處理遞歸處理root的右子樹的右子樹6.5 二叉樹的存儲結構二叉樹的存儲結構建立線索鏈表

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

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

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

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

37、非遞歸實現(xiàn)實現(xiàn) ADBCC6.5 二叉樹遍歷的非遞歸算法二叉樹遍歷的非遞歸算法數(shù)據(jù)結構與算法數(shù)據(jù)結構與算法電子工業(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ù)結構與算法數(shù)據(jù)結構與算法電子工業(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ù)結構與算法數(shù)據(jù)結構與算法電子工業(yè)出版社電子工業(yè)出版社中序遍歷中序遍歷非遞歸算法非遞歸算法在二叉樹的中序遍歷中，訪問結點的操作發(fā)生在該結點的在二叉樹的中序遍歷中，訪問結點的操作發(fā)生在該結點的左子樹遍歷完畢并準備遍歷右子樹時，所以，在遍歷過程左子樹遍歷完畢并準備遍歷右子樹時，所以，在遍歷過程中遇到某結點時并不能立即訪問它，而是將它壓棧，等到中遇到某結點時并不能立即訪問它，而是將它壓棧，等到它的左子樹遍歷完畢后，再從棧中彈出并訪問之。中序遍它的左子樹遍歷完畢后，再從棧中彈出

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

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

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

44、則表明棧頂結點的右子樹也遍歷完畢，輸出棧頂，則表明棧頂結點的右子樹也遍歷完畢，輸出棧頂結點。結點。6.5 二叉樹遍歷的非遞歸算法二叉樹遍歷的非遞歸算法數(shù)據(jù)結構與算法數(shù)據(jù)結構與算法電子工業(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ù)結構與算法數(shù)據(jù)結構與算法電子工業(yè)出版社電子工業(yè)出版社是哪些樹結構的是哪些樹結構的存儲結構存儲結構? ?樹和二叉樹之間具有對應關系樹和二叉樹之間具有對應關系AEBCFDGA BCED F GABCDEFG6.6 樹、森林與二叉樹的轉換樹、森林與二叉樹的轉換數(shù)據(jù)結構與算法數(shù)據(jù)結構與算法電

46、子工業(yè)出版社電子工業(yè)出版社樹和二叉樹之間的對應關系樹和二叉樹之間的對應關系 樹：兄弟關系樹：兄弟關系二叉樹：雙親和右孩子二叉樹：雙親和右孩子 樹：雙親和長子樹：雙親和長子二叉樹：雙親和左孩子二叉樹：雙親和左孩子AEBCFDGABCDEFG6.6 樹、森林與二叉樹的轉換樹、森林與二叉樹的轉換數(shù)據(jù)結構與算法數(shù)據(jù)結構與算法電子工業(yè)出版社電子工業(yè)出版社6.6 樹、森林與二叉樹的轉換樹、森林與二叉樹的轉換 1.兄弟加線兄弟加線.樹和二叉樹之間的對應關系樹和二叉樹之間的對應關系ABCDEFG數(shù)據(jù)結構與算法數(shù)據(jù)結構與算法電子工業(yè)出版社電子工業(yè)出版社2.保留雙親與第一保留雙親與第一孩子連線孩子連線,刪去與刪去

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

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

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

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

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

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

53、據(jù)結構與算法電子工業(yè)出版社電子工業(yè)出版社【問題問題】已知已知Windows操作系統(tǒng)的文件目錄結構，請統(tǒng)計每個操作系統(tǒng)的文件目錄結構，請統(tǒng)計每個文件和文件夾的大小。文件和文件夾的大小?！舅惴ㄋ惴ā靠梢杂脴浣Y構表示這種文件目錄結構，輸出即是對樹可以用樹結構表示這種文件目錄結構，輸出即是對樹進行后序遍歷的結果，括號內的數(shù)字代表文件大小，其中文件進行后序遍歷的結果，括號內的數(shù)字代表文件大小，其中文件的大小即是文件本身的大小，文件夾的大小是本身大小和目錄的大小即是文件本身的大小，文件夾的大小是本身大小和目錄下所有文件的大小之和。下所有文件的大小之和。設樹用孩子兄弟表示法存儲，存儲結構定義如下：設樹用孩子

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

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

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

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

58、2，Tn； 選取與合并選取與合并：在：在F中選取根結點的權值中選取根結點的權值最小最小的兩的兩棵二叉樹分別作為左、右子樹構造一棵新的二叉樹棵二叉樹分別作為左、右子樹構造一棵新的二叉樹，這棵新二叉樹的根結點的權值為其左、右子樹根，這棵新二叉樹的根結點的權值為其左、右子樹根結點的權值之和；結點的權值之和； 刪除與加入刪除與加入：在：在F中刪除作為左、右子樹的兩棵中刪除作為左、右子樹的兩棵二叉樹，并將新建立的二叉樹加入到二叉樹，并將新建立的二叉樹加入到F中；中； 重復重復、兩步，當集合、兩步，當集合F中只剩下一棵二叉樹中只剩下一棵二叉樹時，這棵二叉樹便是哈夫曼樹。時，這棵二叉樹便是哈夫曼樹。 6.7

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

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