第6章樹和二叉樹new

1、數(shù)數(shù) 據(jù)據(jù) 結結 構構 一、教學內(nèi)容：一、教學內(nèi)容： 1、樹和森林的概念（樹的定義、樹的術語、性質(zhì)及運算）；樹和森林的概念（樹的定義、樹的術語、性質(zhì)及運算）； 2、二叉樹的定義、性質(zhì)及運算；二叉樹的定義、性質(zhì)及運算； 3、二叉樹的存儲結構（順序、鏈式表示）；二叉樹的存儲結構（順序、鏈式表示）； 4、遍歷二叉樹遍歷二叉樹 5、樹的存儲結構；樹、森林與二叉樹的轉換；遍歷樹；遍歷森林樹的存儲結構；樹、森林與二叉樹的轉換；遍歷樹；遍歷森林 6、哈夫曼樹、哈夫曼編碼。哈夫曼樹、哈夫曼編碼。 二、教學要求：二、教學要求： 1、了解樹和森林的概念。包括樹的定義、樹的術語和性質(zhì)；、了解樹和森林的概念。包括樹的

2、定義、樹的術語和性質(zhì)； 2、熟練掌握二叉樹的結構特性，熟悉二叉樹的各種存儲結構的特點及適、熟練掌握二叉樹的結構特性，熟悉二叉樹的各種存儲結構的特點及適 用范圍；用范圍； 3、熟練掌握二叉樹的遍歷方法及遍歷算法；、熟練掌握二叉樹的遍歷方法及遍歷算法； 4、熟悉樹的各種存儲結構及其特點，掌握樹、森林與二叉樹的轉換方法、熟悉樹的各種存儲結構及其特點，掌握樹、森林與二叉樹的轉換方法 5、掌握建立哈夫曼樹和哈夫曼編碼的方法及帶權路徑長度的計算。、掌握建立哈夫曼樹和哈夫曼編碼的方法及帶權路徑長度的計算。 數(shù)數(shù) 據(jù)據(jù) 結結 構構 樹是一類重要的非線性數(shù)據(jù)結構，是以分支關系定義的層樹是一類重要的非線性數(shù)據(jù)結構

3、，是以分支關系定義的層 次結構次結構 6.1 樹的定義樹的定義 定義定義 定義：樹定義：樹(tree)是是n(n0)個結點的有限集個結點的有限集T，其中：，其中： 有且僅有一個特定的結點，稱為樹的根有且僅有一個特定的結點，稱為樹的根(root) 當當n1時，其余結點可分為時，其余結點可分為m(m0)個互不相交的有個互不相交的有 限集限集T1,T2,Tm，其中每一個集合本身又是一棵，其中每一個集合本身又是一棵 樹，稱為根的子樹樹，稱為根的子樹(subtree) 特點：特點： 樹中至少有一個結點樹中至少有一個結點根根 樹中各子樹是互不相交的集合樹中各子樹是互不相交的集合 數(shù)數(shù) 據(jù)據(jù) 結結 構構 A

4、 只有根結點的樹只有根結點的樹 A BCD EFGHIJ KLM 有子樹的樹有子樹的樹根根 子樹子樹 數(shù)數(shù) 據(jù)據(jù) 結結 構構 基本術語基本術語 結點結點(node)表示樹中的元素，包括數(shù)據(jù)項及若干表示樹中的元素，包括數(shù)據(jù)項及若干 指向其子樹的分支指向其子樹的分支 結點的度結點的度(degree)結點擁有的子樹數(shù)結點擁有的子樹數(shù) 葉子葉子(leaf)度為度為0的結點的結點 孩子孩子(child)結點子樹的根稱為該結點的孩子結點子樹的根稱為該結點的孩子 雙親雙親(parents)孩子結點的上層結點叫該結點的孩子結點的上層結點叫該結點的 兄弟兄弟(sibling)同一雙親的孩子同一雙親的孩子 樹的度

5、樹的度一棵樹中最大的結點度數(shù)一棵樹中最大的結點度數(shù) 結點的層次結點的層次(level)從根結點算起，根為第一層，從根結點算起，根為第一層， 它的孩子為第二層它的孩子為第二層 深度深度(depth)樹中結點的最大層次數(shù)樹中結點的最大層次數(shù) 森林森林(forest)m(m 0)棵互不相交的樹的集合棵互不相交的樹的集合 數(shù)數(shù) 據(jù)據(jù) 結結 構構 A BCD EFGHIJ KLM 結點結點A的度：的度：3 結點結點B的度：的度：2 結點結點M的度：的度：0 葉子：葉子：K，L，F(xiàn)，G，M，I，J 結點結點A的孩子：的孩子：B，C，D 結點結點B的孩子：的孩子：E，F(xiàn) 結點結點I的雙親：的雙親：D 結點結

6、點L的雙親：的雙親：E 結點結點B，C，D為兄弟為兄弟 結點結點K，L為兄弟為兄弟 樹的度：樹的度：3 結點結點A的層次：的層次：1 結點結點M的層次：的層次：4 樹的深度：樹的深度：4 結點結點F，G為堂兄弟為堂兄弟 結點結點A是結點是結點F，G的祖先的祖先 數(shù)數(shù) 據(jù)據(jù) 結結 構構 b a c ghdef ij 數(shù)數(shù) 據(jù)據(jù) 結結 構構 教師教師學生學生其他人員其他人員 99級級 2000級級 2001級級 2002級級 泰山醫(yī)學院泰山醫(yī)學院 信工學院信工學院醫(yī)學系醫(yī)學系外語系外語系 葉子葉子 根根 子樹子樹 數(shù)數(shù) 據(jù)據(jù) 結結 構構 a b d e i j f c g h 數(shù)數(shù) 據(jù)據(jù) 結結 構

7、構 ijdfgh a bce a ( b ( d, e ( i, j ), c ( g, h ) ) ) 數(shù)數(shù) 據(jù)據(jù) 結結 構構 6.2 二叉樹二叉樹 定義定義 定義：二叉樹是定義：二叉樹是n(n 0)個結點的有限集，它或為空樹個結點的有限集，它或為空樹(n=0)，或由，或由 一個根結點和兩棵分別稱為左子樹和右子樹的互不相交的二叉樹一個根結點和兩棵分別稱為左子樹和右子樹的互不相交的二叉樹 構成構成 特點特點 每個結點至多有二棵子樹每個結點至多有二棵子樹(即不存在度大于即不存在度大于2的結點的結點) 二叉樹的子樹有左、右之分，且其次序不能任意顛倒二叉樹的子樹有左、右之分，且其次序不能任意顛倒 基

8、本形態(tài)基本形態(tài) A 只有根結點只有根結點 的二叉樹的二叉樹 空二叉樹空二叉樹 A B 右子樹為空右子樹為空 A B 左子樹為空左子樹為空 A BC 左、右子樹左、右子樹 均非空均非空 數(shù)數(shù) 據(jù)據(jù) 結結 構構 二叉樹性質(zhì)二叉樹性質(zhì) 性質(zhì)性質(zhì)1： 1)(i點個結2層上至多有i在二叉樹 1i 數(shù)點，結 證明：用歸納法證明之證明：用歸納法證明之 i=1時，只有一個根結點，時，只有一個根結點， 是對的是對的 假設對所有假設對所有j(1 j1，則其雙親是，則其雙親是 i/2 (2) 如果如果2in，則結點，則結點i無左孩子；如果無左孩子；如果2i n ，則其左孩子是，則其左孩子是2i (3) 如果如果2i

9、+1n，則結點，則結點i無右孩子；如果無右孩子；如果 2i+1 n，則其右孩子是，則其右孩子是2i+1 1log2nn深度為個結點的完全二叉樹的具有 數(shù)數(shù) 據(jù)據(jù) 結結 構構 二叉樹的存儲結構二叉樹的存儲結構 順序存儲結構順序存儲結構 實現(xiàn)：按滿二叉樹的結點層次編號，依次存放二叉實現(xiàn)：按滿二叉樹的結點層次編號，依次存放二叉 樹中的數(shù)據(jù)元素樹中的數(shù)據(jù)元素 特點：特點： 結點間關系蘊含在其存儲位置中結點間關系蘊含在其存儲位置中 浪費空間，適于存滿二叉樹和完全二叉樹浪費空間，適于存滿二叉樹和完全二叉樹 a bc de fg a b c d e 0 0 0 0 f g 1 2 3 4 5 6 7 8 9

10、 10 11 數(shù)數(shù) 據(jù)據(jù) 結結 構構 鏈式存儲結構鏈式存儲結構 二叉鏈表二叉鏈表 typedef struct node datatype data; struct node *lchild, *rchild; JD; lchild data rchild A B CD EF G 在n個結點的二叉鏈表中，有n+1個空指針域 A B C D E F G 空指針個數(shù)：2*n0+1*n1+0*n2 =2n0+n1 =n0+n1+n0 =n0+n1+n2+1 =n+1 數(shù)數(shù) 據(jù)據(jù) 結結 構構 三叉鏈表三叉鏈表 typedef struct node datatype data; struct node

11、 *lchild, *rchild, *parent; JD; lchild data parent rchild A B CD EF G A B C D E F G 數(shù)數(shù) 據(jù)據(jù) 結結 構構 6.3 遍歷二叉樹和線索二叉樹遍歷二叉樹和線索二叉樹 二叉樹的遍歷二叉樹的遍歷 方法方法 先序遍歷：先訪問根結點先序遍歷：先訪問根結點,然后分別先序遍歷左子樹、右子樹然后分別先序遍歷左子樹、右子樹 中序遍歷：先中序遍歷左子樹，然后訪問根結點，最后中序中序遍歷：先中序遍歷左子樹，然后訪問根結點，最后中序 遍歷右子樹遍歷右子樹 后序遍歷：先后序遍歷左、右子樹，然后訪問根結點后序遍歷：先后序遍歷左、右子樹，然后

12、訪問根結點 按層次遍歷：從上到下、從左到右訪問各結點按層次遍歷：從上到下、從左到右訪問各結點 D LR LDR、LRD、DLR RDL、RLD、DRL 數(shù)數(shù) 據(jù)據(jù) 結結 構構 A D B C D L R A D L R D L R B D C D L R 先序遍歷序列：先序遍歷序列：A B D C 先序遍歷先序遍歷: 數(shù)數(shù) 據(jù)據(jù) 結結 構構 A D B C L D R B L D R L D R A D C L D R 中序遍歷序列：中序遍歷序列：B D A C 中序遍歷中序遍歷: 數(shù)數(shù) 據(jù)據(jù) 結結 構構 A D B C L R D L R D L R D A D C L R D 后序遍歷序列

13、：后序遍歷序列： D B C A 后序遍歷后序遍歷: B 數(shù)數(shù) 據(jù)據(jù) 結結 構構 - + / a* b- ef cd 先序遍歷先序遍歷： 中序遍歷：中序遍歷： 后序遍歷：后序遍歷： 層次遍歷層次遍歷： - + a * b - c d / e f -+a*b-cd/ef - +a *b - c d/e f -+a*b-c d/e f 數(shù)數(shù) 據(jù)據(jù) 結結 構構 void preorder(JD *bt) if(bt!=NULL) printf(%dt,bt-data); preorder(bt-lchild); preorder(bt-rchild); 主程序主程序 Pre( T ) 返回 返回 p

14、re(T R); 返回 返回 pre(T R); A CB D T B printf(B); pre(T L); B T A printf(A); pre(T L); A T D printf(D); pre(T L); D T C printf(C); pre(T L); C 返回 T 左是空返回 pre(T R); T 左是空返回 T 右是空返回 T 左是空返回 T 右是空返回 pre(T R); 先序序列：A B D C 數(shù)數(shù) 據(jù)據(jù) 結結 構構 非遞歸算法 A B CD EF G p i P-A (1) A B CD EF G p i P-A P-B (2) A B CD EF G pi

15、 P-A P-B P-C (3) p=NUL L A B CD EF G i P-A P-B 訪問：C(4) 數(shù)數(shù) 據(jù)據(jù) 結結 構構 p A B CD EF G i P-A 訪問：C B (5) A B CD EF G i P-A P-D 訪問：C B p (6) A B CD EF G i P-A P-D P-E 訪問：C B p (7) A B CD EF G i P-A P-D 訪問：C B E p (8) 數(shù)數(shù) 據(jù)據(jù) 結結 構構 A B CD EF G i P-A P-D P-G 訪問：C B E P=NULL (9) A B CD EF G i P-A 訪問：C B E G D p

16、(11) A B CD EF G i P-A P-F 訪問：C B E G D p (12) A B CD EF G i P-A P-D 訪問：C B E G p (10) 數(shù)數(shù) 據(jù)據(jù) 結結 構構 A B CD EF G i P-A 訪問：C B E G D F p=NULL (13) A B CD EF G i 訪問：C B E G D F A p (14) A B CD EF G i 訪問：C B E G D F A p=NULL (15) 后序遍歷非遞歸算法 數(shù)數(shù) 據(jù)據(jù) 結結 構構 遍歷算法應用 按先序遍歷序列建立二叉樹的二叉鏈表，已知先序 序列為： A B C D E G F 求二叉樹

17、深度算法 A B CD EF G A B C D E F G 統(tǒng)計二叉樹中葉子結點個數(shù)算法 數(shù)數(shù) 據(jù)據(jù) 結結 構構 用隊列實現(xiàn)層次遍歷用隊列實現(xiàn)層次遍歷 下面的下面的C語言函數(shù)是實現(xiàn)對給定的二叉樹語言函數(shù)是實現(xiàn)對給定的二叉樹T的層次遍歷。函數(shù)使用一個順序的層次遍歷。函數(shù)使用一個順序 存儲的隊列存儲的隊列q100,存放還沒有處理的子樹的根結點的地址。注意存放還沒有處理的子樹的根結點的地址。注意,隊首和隊尾隊首和隊尾 指針分別指向隊首結點和下次進隊結點的存放位置。指針分別指向隊首結點和下次進隊結點的存放位置。 void lev_ traverse(T) NODE *T; NODE *q100,p;

18、 int head,tai l, i; q0=T;head=0;tail=1; while(headdata); if(p-lchild!=NULL) qtail+=p-lchild; if(p-rchild!=NULL) qtail+=p-rchild; 數(shù)數(shù) 據(jù)據(jù) 結結 構構 線索二叉樹線索二叉樹 定義：定義： 前驅(qū)與后繼：在二叉樹的先序、中序或后序遍歷序列中前驅(qū)與后繼：在二叉樹的先序、中序或后序遍歷序列中 兩個相鄰的結點互稱為兩個相鄰的結點互稱為 線索：指向前驅(qū)或后繼結點的指針稱為線索：指向前驅(qū)或后繼結點的指針稱為 線索二叉樹：加上線索的二叉鏈表表示的二叉樹叫線索二叉樹：加上線索的二叉鏈

19、表表示的二叉樹叫 線索化：對二叉樹按某種遍歷次序使其變?yōu)榫€索二叉樹線索化：對二叉樹按某種遍歷次序使其變?yōu)榫€索二叉樹 的過程叫的過程叫 實現(xiàn)實現(xiàn) 在有在有n個結點的二叉鏈表中必定有個結點的二叉鏈表中必定有n+1個空鏈域個空鏈域 在線索二叉樹的結點中增加兩個標志域在線索二叉樹的結點中增加兩個標志域 ltag :若若 ltag=0, lchild 域指向左孩子；域指向左孩子； 若若 ltar=1, lchild域指向其前驅(qū)域指向其前驅(qū) rtag :若若 rtag =0, rchild 域指向右孩子；域指向右孩子； 若若 rtag=1, rchild域指向其后繼域指向其后繼 數(shù)數(shù) 據(jù)據(jù) 結結 構構 A

20、 B C D E A B D C E T 先序序列：先序序列：ABCDE 先序線索二叉樹先序線索二叉樹 00 0011 1 1 11 typedef struct node int data; int ltag, rtag; struct node *lchild, *rchild; JD; lchild ltag data rtag rchild 數(shù)數(shù) 據(jù)據(jù) 結結 構構 A B C D E A B D C E T 中序序列：中序序列：BCAED 中序線索二叉樹中序線索二叉樹 00 0011 11 11 數(shù)數(shù) 據(jù)據(jù) 結結 構構 A B C D E A B D C E T 后序序列：后序序列：C

21、BEDA 后序線索二叉樹后序線索二叉樹 00 0011 1111 數(shù)數(shù) 據(jù)據(jù) 結結 構構 A B C D E 0 A 0 1 B 0 0 D 1 1 C 1 1 E 1 T 中序序列：中序序列：BCAED 帶頭結點的中序線索二叉樹帶頭結點的中序線索二叉樹 0 1 頭結點：頭結點： ltag=0, lchild指向根結點指向根結點 rtag=1, rchild指向遍歷序列中最后一個結點指向遍歷序列中最后一個結點 遍歷序列中第一個結點的遍歷序列中第一個結點的lchild域和最后域和最后 一個結點的一個結點的rchild域都指向頭結點域都指向頭結點 A B D C E T 中序序列：中序序列：BCA

22、ED 中序線索二叉樹中序線索二叉樹 00 0011 11 11 數(shù)數(shù) 據(jù)據(jù) 結結 構構 目的：在依某種順序遍歷二叉樹時修改空指針，添加前驅(qū)或后繼。目的：在依某種順序遍歷二叉樹時修改空指針，添加前驅(qū)或后繼。 注解：為方便添加結點的前驅(qū)或后繼，需要設置兩個指針：注解：為方便添加結點的前驅(qū)或后繼，需要設置兩個指針： p指針指針當前結點之指針；當前結點之指針； pre指針指針前驅(qū)結點之指針。前驅(qū)結點之指針。 技巧：當結點技巧：當結點p的左的左/右域為空時，只改寫它的左域（裝入前驅(qū)右域為空時，只改寫它的左域（裝入前驅(qū) pre），而其右域（后繼）留給下一結點來填寫。），而其右域（后繼）留給下一結點來填寫。

23、 或者說，當前結點的指針或者說，當前結點的指針p應當送到前驅(qū)結點的空右域中。應當送到前驅(qū)結點的空右域中。 若若p-lchildNULL, ,則則p-Ltag=1;p-lchildp-Ltag=1;p-lchildpre;pre; /p /p的前驅(qū)結點指針的前驅(qū)結點指針prepre存入左空域存入左空域 若若pre-rchildNULL, 則則pre-Rtagpre-Rtag1;pre-rchild1;pre-rchild=p;=p; /p /p存入其前驅(qū)結點存入其前驅(qū)結點prepre的右空域的右空域 數(shù)數(shù) 據(jù)據(jù) 結結 構構 算法算法 遍歷中序線索二叉樹遍歷中序線索二叉樹 在中序線索二叉樹中找結點

24、后繼的方法：在中序線索二叉樹中找結點后繼的方法： （1）若）若rtag=1, 則則rchild域直接指向其后繼域直接指向其后繼 （2）若）若rtag=0, 則結點的后繼應是其右子樹的左鏈尾（則結點的后繼應是其右子樹的左鏈尾（ltag=1)的結點的結點 在中序線索二叉樹中找結點前驅(qū)的方法：在中序線索二叉樹中找結點前驅(qū)的方法： （1）若）若ltag=1, 則則lchild域直接指向其前驅(qū)域直接指向其前驅(qū) （2）若）若ltag=0, 則結點的前驅(qū)應是其左子樹的右鏈尾（則結點的前驅(qū)應是其左子樹的右鏈尾（rtag=1)的結點的結點 A B C D E 0 A 0 1 B 0 0 D 1 1 C 1 1

25、E 1 T 中序序列：中序序列：BCAED 帶頭結點的中序線索二叉樹帶頭結點的中序線索二叉樹 0 1 數(shù)數(shù) 據(jù)據(jù) 結結 構構 程序注解程序注解 (非遞歸，且不用棧非遞歸，且不用棧）： P=T-lchild; /從頭結點進入到根結點；從頭結點進入到根結點； while( p!=T) while(p-LTag=link)p=p-lchild; /先找到中序遍歷起點先找到中序遍歷起點 if(!visit(p-data) return ERROR; /若起點值為空則出錯告警若起點值為空則出錯告警 while(p-RTag=Thread ) p=p-rchild; Visit(p-data); /若有后

26、繼標志，則直接提取若有后繼標志，則直接提取p-rchild中線索并中線索并 訪問后繼結點；訪問后繼結點； p=p-rchild; /當前結點右域不空或已經(jīng)找好了后繼，則一律從當前結點右域不空或已經(jīng)找好了后繼，則一律從 結點的右子樹開始重復結點的右子樹開始重復 的全部過程。的全部過程。 Return OK; LTag=0 RTag=1 數(shù)數(shù) 據(jù)據(jù) 結結 構構 6.4 樹的存儲結構樹的存儲結構 樹的存儲結構樹的存儲結構 雙親表示法雙親表示法 實現(xiàn)：定義結構數(shù)組存放樹的結點，每個結點含兩實現(xiàn)：定義結構數(shù)組存放樹的結點，每個結點含兩 個域：個域： 數(shù)據(jù)域：存放結點本身信息數(shù)據(jù)域：存放結點本身信息 雙親

27、域：指示本結點的雙親結點在數(shù)組中位置雙親域：指示本結點的雙親結點在數(shù)組中位置 特點：找雙親容易，找孩子難特點：找雙親容易，找孩子難 typedef struct node datatype data; int parent; JD; JD tM; 數(shù)數(shù) 據(jù)據(jù) 結結 構構 a bc def hgi a c d e f g h i b 0 1 2 2 3 5 5 5 1 09 6 0 1 2 3 4 5 7 8 9 dataparent 0號單元不用或號單元不用或 存結點個數(shù)存結點個數(shù) 如何找孩子結點如何找孩子結點 數(shù)數(shù) 據(jù)據(jù) 結結 構構 孩子表示法孩子表示法 多重鏈表：每個結點有多個指針域，分別

28、指向其子樹的根多重鏈表：每個結點有多個指針域，分別指向其子樹的根 結點同構：結點的指針個數(shù)相等，為樹的結點同構：結點的指針個數(shù)相等，為樹的度度D 結點不同構：結點指針個數(shù)不等，為該結點的度結點不同構：結點指針個數(shù)不等，為該結點的度d data child1 child2 . childD data degree child1 child2 . childd 孩子鏈表：每個結點的孩子結點用單鏈表存儲，再孩子鏈表：每個結點的孩子結點用單鏈表存儲，再 用含用含n個元素的結構數(shù)組指向每個孩子鏈表個元素的結構數(shù)組指向每個孩子鏈表 數(shù)數(shù) 據(jù)據(jù) 結結 構構 孩子結點：孩子結點：typedef struct

29、node int child; /該結點在表頭數(shù)組中下標該結點在表頭數(shù)組中下標 struct node *next; /指向下一孩子結點指向下一孩子結點 JD; 表頭結點：表頭結點：typedef struct tnode datatype data; /數(shù)據(jù)域數(shù)據(jù)域 struct node *fc; /指向第一個孩子結點指向第一個孩子結點 TD; TD tM; /t0不用不用 數(shù)數(shù) 據(jù)據(jù) 結結 構構 a bc def hgi 6 0 1 2 3 4 5 7 8 9 a c d e f g h i b datafc 2 3 4 5 9 7 8 6 如何找雙親結點如何找雙親結點 數(shù)數(shù) 據(jù)據(jù) 結結

30、 構構 帶雙親的孩子鏈表帶雙親的孩子鏈表 6 1 2 3 4 5 7 8 9 a c d e f g h i b datafc 2 3 4 5 9 7 8 6 0 1 2 2 3 5 5 5 1 parent a bc def hgi 數(shù)數(shù) 據(jù)據(jù) 結結 構構 孩子兄弟表示法（二叉樹表示法）孩子兄弟表示法（二叉樹表示法） 實現(xiàn)：用二叉鏈表作樹的存儲結構，鏈表中每個結點實現(xiàn)：用二叉鏈表作樹的存儲結構，鏈表中每個結點 的兩個指針域分別指向其第一個孩子結點和下一個兄的兩個指針域分別指向其第一個孩子結點和下一個兄 弟結點弟結點 特點特點 操作容易操作容易 破壞了樹的層次破壞了樹的層次 typedef s

31、truct node datatype data; struct node *fch, *nsib; JD; a bc def hgi a b c d e f g h i 數(shù)數(shù) 據(jù)據(jù) 結結 構構 樹與二叉樹轉換樹與二叉樹轉換 A CBE D 樹樹 A B C DE 二叉樹二叉樹 A B C D E A B C D E A B C D E 對應對應 存儲存儲 存儲存儲 解釋解釋 解釋解釋 數(shù)數(shù) 據(jù)據(jù) 結結 構構 將樹轉換成二叉樹將樹轉換成二叉樹 加線：在兄弟之間加一連線加線：在兄弟之間加一連線 抹線：對每個結點，除了其左孩子外，去除其與其抹線：對每個結點，除了其左孩子外，去除其與其 余孩子之間的

32、關系余孩子之間的關系 旋轉：以樹的根結點為軸心，將整樹順時針轉旋轉：以樹的根結點為軸心，將整樹順時針轉45 A BCD EFGHI A BCD EFGHI A BCD EFGHI A BCD EFGHI A B C D E F GH I 樹轉換成的二叉樹其右子樹一定為空樹轉換成的二叉樹其右子樹一定為空 數(shù)數(shù) 據(jù)據(jù) 結結 構構 將二叉將二叉樹轉換成樹樹轉換成樹 加線：若加線：若p結點是雙親結點的左孩子，則將結點是雙親結點的左孩子，則將p的右的右 孩子，右孩子的右孩子，孩子，右孩子的右孩子，沿分支找到的所有右沿分支找到的所有右 孩子，都與孩子，都與p的雙親用線連起來的雙親用線連起來 抹線：抹掉原二

33、叉樹中雙親與右孩子之間的連線抹線：抹掉原二叉樹中雙親與右孩子之間的連線 調(diào)整：將結點按層次排列，形成樹結構調(diào)整：將結點按層次排列，形成樹結構 A B C D E F GH I A B C D E F GH I A B C D E F GH I A B C D E F GH I A BCD EFGHI 數(shù)數(shù) 據(jù)據(jù) 結結 構構 森林轉換成二叉樹森林轉換成二叉樹 將各棵樹分別轉換成二叉樹將各棵樹分別轉換成二叉樹 將每棵樹的根結點用線相連將每棵樹的根結點用線相連 以第一棵樹根結點為二叉樹的根，再以根結點為軸以第一棵樹根結點為二叉樹的根，再以根結點為軸 心，順時針旋轉，構成二叉樹型結構心，順時針旋轉，構

34、成二叉樹型結構 A BCD E F G HI J A B C D E F G H I J A B C D E F G H I J A B C D E F G H I J 數(shù)數(shù) 據(jù)據(jù) 結結 構構 二叉樹轉換成森林二叉樹轉換成森林 抹線：將二叉樹中根結點與其右孩子連線，及沿右抹線：將二叉樹中根結點與其右孩子連線，及沿右 分支搜索到的所有右孩子間連線全部抹掉，使之變分支搜索到的所有右孩子間連線全部抹掉，使之變 成孤立的二叉樹成孤立的二叉樹 還原：將孤立的二叉樹還原成樹還原：將孤立的二叉樹還原成樹 A B C D E F G H I J A B C D E F G H I J A B C D E F

35、G H I J A BCD E F G HI J 數(shù)數(shù) 據(jù)據(jù) 結結 構構 樹和森林的遍歷樹和森林的遍歷 樹的遍歷樹的遍歷 遍歷遍歷按一定規(guī)律走遍樹的各個頂點，且使每一頂點按一定規(guī)律走遍樹的各個頂點，且使每一頂點 僅被訪問一次，即找一個完整而有規(guī)律的走法，以得到僅被訪問一次，即找一個完整而有規(guī)律的走法，以得到 樹中所有結點的一個線性排列樹中所有結點的一個線性排列 常用方法常用方法 先根（序）遍歷：先訪問樹的根結點，然后依次先根先根（序）遍歷：先訪問樹的根結點，然后依次先根 遍歷根的每棵子樹遍歷根的每棵子樹 后根（序）遍歷：先依次后根遍歷每棵子樹，然后訪后根（序）遍歷：先依次后根遍歷每棵子樹，然后

36、訪 問根結點問根結點 按層次遍歷：先訪問第一層上的結點，然后依次遍歷按層次遍歷：先訪問第一層上的結點，然后依次遍歷 第二層，第二層，第第n層的結點層的結點 數(shù)數(shù) 據(jù)據(jù) 結結 構構 A BCD EFGH I JKLM NO 先序遍歷：先序遍歷： 后序遍歷：后序遍歷： 層次遍歷：層次遍歷： ABEF I GCDHJ KLNOM EIFGB CJKN OLMHD A AB CDE FGH I J KL MNO 數(shù)數(shù) 據(jù)據(jù) 結結 構構 討論：若采用討論：若采用“先轉換，后遍歷先轉換，后遍歷”方式，結果是否一樣？方式，結果是否一樣？ a b de c 先序遍歷：先序遍歷： 后序遍歷：后序遍歷： 中序遍歷

37、：中序遍歷： d e c b a a b d ec a b c d e b d c e a 1. 樹的先序遍歷二法相同；樹的先序遍歷二法相同； 2. 樹的樹的后序后序遍歷相當于對應二叉樹的遍歷相當于對應二叉樹的中序中序遍歷；遍歷； 3. 樹沒有中序遍歷，因為子樹無左右之分。樹沒有中序遍歷，因為子樹無左右之分。 結論：結論： 數(shù)數(shù) 據(jù)據(jù) 結結 構構 先序遍歷先序遍歷 F 若森林為空，返回；若森林為空，返回； F 訪問森林中第一棵樹的根結點；訪問森林中第一棵樹的根結點； F 先序遍歷第一棵樹中根結點的子樹森林；先序遍歷第一棵樹中根結點的子樹森林； F 先序遍歷除去第一棵樹之后剩余的樹構成的森林。先

38、序遍歷除去第一棵樹之后剩余的樹構成的森林。 中序遍歷中序遍歷 F 若森林為空，返回；若森林為空，返回； F 中序遍歷森林中第一棵樹的根結點的子樹森林；中序遍歷森林中第一棵樹的根結點的子樹森林； F 訪問第一棵樹的根結點；訪問第一棵樹的根結點； F 中序遍歷除去第一棵樹之后剩余的樹構成的森林。中序遍歷除去第一棵樹之后剩余的樹構成的森林。 A BCD E F G H J I 數(shù)數(shù) 據(jù)據(jù) 結結 構構 討論：討論：若采用若采用“先轉換，后遍歷先轉換，后遍歷”方式，結果是否相同？方式，結果是否相同？ 例如：例如： 先序序列：先序序列： 中序序列：中序序列： A B C D E F G H I J B C

39、 D A F E H J I G 先序序列：先序序列： 中序序列：中序序列： A B C D E F G H I J B C D A F E H J I G 結論：森林的先序和中序遍歷在結論：森林的先序和中序遍歷在 兩種方式下的結果相同。兩種方式下的結果相同。 數(shù)數(shù) 據(jù)據(jù) 結結 構構 結論：當以二叉鏈表做樹的存儲結構時，樹的先結論：當以二叉鏈表做樹的存儲結構時，樹的先 根序列和后根序列可借用二叉樹的先序遍歷和后根序列和后根序列可借用二叉樹的先序遍歷和后 序遍歷的算法實現(xiàn)之；對于森林也一樣。序遍歷的算法實現(xiàn)之；對于森林也一樣。 數(shù)數(shù) 據(jù)據(jù) 結結 構構 一、一、基本術語基本術語 1路徑和路徑長度路

40、徑和路徑長度 在一棵樹中，從一個結點往下可以達到的孩子或子孫結在一棵樹中，從一個結點往下可以達到的孩子或子孫結 點之間的通路，稱為路徑。通路中分支的數(shù)目稱為路徑點之間的通路，稱為路徑。通路中分支的數(shù)目稱為路徑 長度。長度。 若規(guī)定根結點的層數(shù)為若規(guī)定根結點的層數(shù)為1，則從根結點到第，則從根結點到第L層結點的路層結點的路 徑長度為徑長度為L-1。 2結點的權及帶權路徑長度結點的權及帶權路徑長度 若將樹中結點賦給一個有著某種含義的數(shù)值，則這個數(shù)若將樹中結點賦給一個有著某種含義的數(shù)值，則這個數(shù) 值稱為該結點的權。值稱為該結點的權。 結點的帶權路徑長度為：從根結點到該結點之間的路徑結點的帶權路徑長度為

41、：從根結點到該結點之間的路徑 長度與該結點的權的乘積。長度與該結點的權的乘積。 7.7 哈夫曼樹哈夫曼樹 數(shù)數(shù) 據(jù)據(jù) 結結 構構 3樹的帶權路徑長度樹的帶權路徑長度 樹的帶權路徑長度規(guī)定為所有葉子結點的帶權路徑長樹的帶權路徑長度規(guī)定為所有葉子結點的帶權路徑長 度之和，記為度之和，記為wpl= ， 其中其中n 為葉子結點數(shù)目，為葉子結點數(shù)目，wi為第為第i 個葉子結點的權值，個葉子結點的權值， li 為第為第i 個葉子結點的路徑長度。個葉子結點的路徑長度。 n i iil w 1 二、構造哈夫曼樹二、構造哈夫曼樹 1哈夫曼樹的定義哈夫曼樹的定義 在一棵二叉樹中，若帶權路徑長度達到最小，稱這在一棵

42、二叉樹中，若帶權路徑長度達到最小，稱這 樣 的 二 叉 樹 為 最 優(yōu) 二 叉 樹 ， 也 稱 為 哈 夫 曼 樹樣 的 二 叉 樹 為 最 優(yōu) 二 叉 樹 ， 也 稱 為 哈 夫 曼 樹 (Huffman tree)。 數(shù)數(shù) 據(jù)據(jù) 結結 構構 例例 有有4個結點，權值分別為個結點，權值分別為7，5，2，4，構造有，構造有4個葉子結點的二叉樹個葉子結點的二叉樹 abcd 7524 WPL=7*2+5*2+2*2+4*2=36 d c ab 2 4 75 WPL=7*3+5*3+2*1+4*2=46 a b cd 7 5 24 WPL=7*1+5*2+2*3+4*3=35 n k KKL WWP

43、L 1 數(shù)數(shù) 據(jù)據(jù) 結結 構構 2哈夫曼樹的構造哈夫曼樹的構造 假設有假設有n個權值，則構造出的哈夫曼樹有個權值，則構造出的哈夫曼樹有n個葉子結點。個葉子結點。 n個權值分別設為個權值分別設為 w1,w2,wn,則哈夫曼樹的構造規(guī)則為：則哈夫曼樹的構造規(guī)則為： (1) 將將w1,w2,wn看成是有看成是有n 棵樹的森林棵樹的森林(每棵樹僅有一每棵樹僅有一 個結點個結點)； (2) 在森林中選出兩個根結點的權值最小的樹合并，在森林中選出兩個根結點的權值最小的樹合并， 作為一棵新樹的左、右子樹，且新樹的根結點權值為作為一棵新樹的左、右子樹，且新樹的根結點權值為 其左、右子樹根結點權值之和；其左、右

44、子樹根結點權值之和； (3)從森林中刪除選取的兩棵樹，并將新樹加入森林；從森林中刪除選取的兩棵樹，并將新樹加入森林； (4)重復重復(2)、(3)步，直到森林中只剩一棵樹為止，該步，直到森林中只剩一棵樹為止，該 樹即為我們所求得的哈夫曼樹。樹即為我們所求得的哈夫曼樹。 數(shù)數(shù) 據(jù)據(jù) 結結 構構 下面給出哈夫曼樹的構造過程，假設給定的葉子結點的下面給出哈夫曼樹的構造過程，假設給定的葉子結點的 權分別為權分別為1,5,7,3，則構造哈夫曼樹過程如圖，則構造哈夫曼樹過程如圖7-24所示。所示。 3 7 5 1 5 7 1 3 4 (a) 初始森林 (b) 一次合并后的森林 5 9 1 3 4 7 5

45、9 1 3 4 7 16 (c) 二次合并后的森林 (d) 三合并后的森林 圖 7-24 哈夫曼樹的構造過程 數(shù)數(shù) 據(jù)據(jù) 結結 構構 從圖從圖7-24可知，可知，n 個權值構造哈夫曼樹需個權值構造哈夫曼樹需n-1次合并，每次合并，每 次合并，森林中的樹數(shù)目減次合并，森林中的樹數(shù)目減1，最后森林中只剩下一棵，最后森林中只剩下一棵 樹，即為我們求得的哈夫曼樹。樹，即為我們求得的哈夫曼樹。 數(shù)數(shù) 據(jù)據(jù) 結結 構構 3 3、哈夫曼樹構造程序、哈夫曼樹構造程序 一棵有一棵有n個葉子結點的個葉子結點的Huffman樹有樹有2n-1個結點個結點 采用順序存儲結構采用順序存儲結構一維結構數(shù)組存儲結點一維結構數(shù)

46、組存儲結點 信息信息 結點類型定義為：結點類型定義為： typedef struct int weight; int parent,lchild,rchild; JD; #define MAX 100 void huffman(int n,int w,JD t) int i,j,k,x1,x2,m1,m2; for(i=1;i(2*n);i+) ti.parent=ti.lchild=ti.rchild=-1; if(i=n) ti.weight=wi; else ti.weight=0; 數(shù)數(shù) 據(jù)據(jù) 結結 構構 for(i=1;in;i+) m1=m2=MAX; x1=x2=0; for(j=1;j(n+i);j+) if(tj.weightm1) x2=x1; m1=tj.weight; x