了解樹(shù)的定義和基本術(shù)語(yǔ)

1、1第6章 樹(shù)n了解樹(shù)的定義和基本術(shù)語(yǔ)；n掌握二叉樹(shù)的定義、性質(zhì)和表示；n算法設(shè)計(jì)（層次3）：遍歷二叉樹(shù)及應(yīng)用（先/中/后序遍歷的遞歸算法，層次遍歷）；（靈活應(yīng)用，非遞歸不要求）n理解樹(shù)和森林的定義、表示，掌握森林與二叉樹(shù)的轉(zhuǎn)換以及森林的遍歷；（重點(diǎn)是孩子兄弟鏈表）n了解哈夫曼樹(shù)的定義、構(gòu)造（算法思想）及其應(yīng)用（即哈夫曼編碼）。2第6章 樹(shù) 樹(shù)是一類(lèi)重要的非線性數(shù)據(jù)結(jié)構(gòu)，是以分支關(guān)系定義的層次結(jié)構(gòu)n6.1 樹(shù)的定義n定義 定義：樹(shù)(tree)是n(n=0)個(gè)結(jié)點(diǎn)的有限集T，其中： 有且僅有一個(gè)特定的結(jié)點(diǎn)，稱(chēng)為樹(shù)的根(root) 當(dāng)n1時(shí)，其余結(jié)點(diǎn)可分為m(m0)個(gè)互不相交的有限集T1,T2,Tm

2、，其中每一個(gè)集合本身又是一棵樹(shù)，稱(chēng)為根的子樹(shù)(subtree) 特點(diǎn)： 樹(shù)中至少有一個(gè)結(jié)點(diǎn)根 樹(shù)中各子樹(shù)是互不相交的集合3A只有根結(jié)點(diǎn)的樹(shù)ABCDEFGHIJKLM有子樹(shù)的樹(shù)根子樹(shù)4n基本術(shù)語(yǔ) 結(jié)點(diǎn)(node)表示樹(shù)中的元素，包括數(shù)據(jù)項(xiàng)及若干指向其子樹(shù)的分支 結(jié)點(diǎn)的度(degree)結(jié)點(diǎn)擁有的子樹(shù)數(shù) 葉子(leaf)度為0的結(jié)點(diǎn) 孩子(child)結(jié)點(diǎn)子樹(shù)的根稱(chēng)為該結(jié)點(diǎn)的孩子 雙親(parents)孩子結(jié)點(diǎn)的上層結(jié)點(diǎn)叫該結(jié)點(diǎn)的 兄弟(sibling)同一雙親的孩子 樹(shù)的度一棵樹(shù)中最大的結(jié)點(diǎn)度數(shù) 結(jié)點(diǎn)的層次(level)從根結(jié)點(diǎn)算起，根為第一層，它的孩子為第二層 深度(depth)樹(shù)中結(jié)點(diǎn)的最大

3、層次數(shù) 森林(forest)m(m0)棵互不相交的樹(shù)的集合5ABCDEFGHIJKLM結(jié)點(diǎn)A的度：3結(jié)點(diǎn)B的度：2結(jié)點(diǎn)M的度：0葉子：K，L，F(xiàn)，G，M，I，J結(jié)點(diǎn)A的孩子：B，C，D結(jié)點(diǎn)B的孩子：E，F(xiàn)結(jié)點(diǎn)I的雙親：D結(jié)點(diǎn)L的雙親：E結(jié)點(diǎn)B，C，D為兄弟結(jié)點(diǎn)K，L為兄弟樹(shù)的度：3結(jié)點(diǎn)A的層次：1結(jié)點(diǎn)M的層次：4樹(shù)的深度：4結(jié)點(diǎn)F，G為堂兄弟結(jié)點(diǎn)A是結(jié)點(diǎn)F，G的祖先6n6.2 二叉樹(shù)n定義 定義：二叉樹(shù)是n(n0)個(gè)結(jié)點(diǎn)的有限集，它或?yàn)榭諛?shù)(n=0)，或由一個(gè)根結(jié)點(diǎn)和兩棵分別稱(chēng)為左子樹(shù)和右子樹(shù)的互不相交的二叉樹(shù)構(gòu)成 特點(diǎn) 每個(gè)結(jié)點(diǎn)至多有二棵子樹(shù)(即不存在度大于2的結(jié)點(diǎn)) 二叉樹(shù)的子樹(shù)有左、右之

4、分，且其次序不能任意顛倒 基本形態(tài)A只有根結(jié)點(diǎn)的二叉樹(shù)空二叉樹(shù)AB右子樹(shù)為空AB左子樹(shù)為空ABC左、右子樹(shù)均非空7n二叉樹(shù)性質(zhì)v性質(zhì)1：) 1(21iii個(gè)結(jié)點(diǎn)層上至多有在二叉樹(shù)的第證明：用歸納法證明之 i=1時(shí)，只有一個(gè)根結(jié)點(diǎn)， 是對(duì)的 假設(shè)對(duì)所有j(1j1，則其雙親是i/2 (2) 如果2in，則結(jié)點(diǎn)i無(wú)左孩子；如果2in，則其左孩子是2i (3) 如果2i+1n，則結(jié)點(diǎn)i無(wú)右孩子；如果2i+1n，則其右孩子是2i+112n6.3 樹(shù)的存儲(chǔ)結(jié)構(gòu)n樹(shù)的存儲(chǔ)結(jié)構(gòu)雙親表示法 實(shí)現(xiàn)：定義結(jié)構(gòu)數(shù)組存放樹(shù)的結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)含兩個(gè)域：數(shù)據(jù)域：存放結(jié)點(diǎn)本身信息雙親域：指示本結(jié)點(diǎn)的雙親結(jié)點(diǎn)在數(shù)組中位置 特點(diǎn)：

5、找雙親容易，找孩子難typedef struct node datatype data; int parent;JD;JD tM;13abcdefhgiacdefghib012235551096012345789dataparent0號(hào)單元不用或存結(jié)點(diǎn)個(gè)數(shù)如何找孩子結(jié)點(diǎn)14 孩子表示法 多重鏈表：每個(gè)結(jié)點(diǎn)有多個(gè)指針域，分別指向其子樹(shù)的根結(jié)點(diǎn)同構(gòu)：結(jié)點(diǎn)的指針個(gè)數(shù)相等，為樹(shù)的度D結(jié)點(diǎn)不同構(gòu)：結(jié)點(diǎn)指針個(gè)數(shù)不等，為該結(jié)點(diǎn)的度ddata child1 child2 . childDdata degree child1 child2 . childd 孩子鏈表：每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)用單鏈表存儲(chǔ)，再用含n個(gè)元

6、素的結(jié)構(gòu)數(shù)組指向每個(gè)孩子鏈表孩子結(jié)點(diǎn)：typedef struct node int child; /該結(jié)點(diǎn)在表頭數(shù)組中下標(biāo) struct node *next; /指向下一孩子結(jié)點(diǎn) JD;表頭結(jié)點(diǎn)：typedef struct tnode datatype data; /數(shù)據(jù)域 struct node *fc; /指向第一個(gè)孩子結(jié)點(diǎn) TD; TD tM; /t0不用15abcdefhgi6012345789acdefghibdatafc 2 3 4 5 9 7 8 6如何找雙親結(jié)點(diǎn)16 帶雙親的孩子鏈表612345789acdefghibdatafc 2 3 4 5 9 7 8 601223

7、5551parentabcdefhgi17 孩子兄弟表示法（二叉樹(shù)表示法） 實(shí)現(xiàn)：用二叉鏈表作樹(shù)的存儲(chǔ)結(jié)構(gòu)，鏈表中每個(gè)結(jié)點(diǎn)的兩個(gè)指針域分別指向其第一個(gè)孩子結(jié)點(diǎn)和下一個(gè)兄弟結(jié)點(diǎn) 特點(diǎn)操作容易破壞了樹(shù)的層次typedef struct node datatype data; struct node *fch, *nsib;JD;abcdefhgi a b c d e f g h i18n二叉樹(shù)的存儲(chǔ)結(jié)構(gòu) 順序存儲(chǔ)結(jié)構(gòu) 實(shí)現(xiàn)：按滿(mǎn)二叉樹(shù)的結(jié)點(diǎn)層次編號(hào)，依次存放二叉樹(shù)中的數(shù)據(jù)元素 特點(diǎn)：結(jié)點(diǎn)間關(guān)系蘊(yùn)含在其存儲(chǔ)位置中浪費(fèi)空間，適于存滿(mǎn)二叉樹(shù)和完全二叉樹(shù)abcdefga b c d e 0 0 0 0 f

8、 g 1 2 3 4 5 6 7 8 9 10 1119 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 二叉鏈表typedef struct node datatype data; struct node *lchild, *rchild;JD;lchild data rchild ABCDEFG在n個(gè)結(jié)點(diǎn)的二叉鏈表中，有n+1個(gè)空指針域 AB C D E F G20 三叉鏈表typedef struct node datatype data; struct node *lchild, *rchild, *parent;JD;lchild data parent rchildABCDEFG A B C D E F G21n樹(shù)

9、與二叉樹(shù)轉(zhuǎn)換ACBED樹(shù)ABCDE二叉樹(shù) A B C D E A B C D E A B C D E 對(duì)應(yīng)存儲(chǔ)存儲(chǔ)解釋解釋22 將樹(shù)轉(zhuǎn)換成二叉樹(shù) 加線：在兄弟之間加一連線 抹線：對(duì)每個(gè)結(jié)點(diǎn)，除了其左孩子外，去除其與其余孩子之間的關(guān)系 旋轉(zhuǎn)：以樹(shù)的根結(jié)點(diǎn)為軸心，將整樹(shù)順時(shí)針轉(zhuǎn)45ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI樹(shù)轉(zhuǎn)換成的二叉樹(shù)其根右子樹(shù)一定為空23 將二叉樹(shù)轉(zhuǎn)換成樹(shù) 加線：若p結(jié)點(diǎn)是雙親結(jié)點(diǎn)的左孩子，則將p的右孩子，右孩子的右孩子，沿分支找到的所有右孩子，都與p的雙親用線連起來(lái) 抹線：抹掉原二叉樹(shù)中雙親與右孩子之間的連線 調(diào)整：將結(jié)點(diǎn)按層

10、次排列，形成樹(shù)結(jié)構(gòu)ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI24 森林轉(zhuǎn)換成二叉樹(shù) 將各棵樹(shù)分別轉(zhuǎn)換成二叉樹(shù) 將每棵樹(shù)的根結(jié)點(diǎn)用線相連 以第一棵樹(shù)根結(jié)點(diǎn)為二叉樹(shù)的根，再以根結(jié)點(diǎn)為軸心，順時(shí)針旋轉(zhuǎn)，構(gòu)成二叉樹(shù)型結(jié)構(gòu)ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ25 二叉樹(shù)轉(zhuǎn)換成森林 抹線：將二叉樹(shù)中根結(jié)點(diǎn)與其右孩子連線，及沿右分支搜索到的所有右孩子間連線全部抹掉，使之變成孤立的二叉樹(shù) 還原：將孤立的二叉樹(shù)還原成樹(shù)ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ26n6.4 樹(shù)和二叉樹(shù)

11、的遍歷n樹(shù)的遍歷遍歷按一定規(guī)律走遍樹(shù)的各個(gè)頂點(diǎn)，且使每一頂點(diǎn)僅被訪問(wèn)一次，即找一個(gè)完整而有規(guī)律的走法，以得到樹(shù)中所有結(jié)點(diǎn)的一個(gè)線性排列常用方法 先根（序）遍歷：先訪問(wèn)樹(shù)的根結(jié)點(diǎn)，然后依次先根遍歷根的每棵子樹(shù) 后根（序）遍歷：先依次后根遍歷每棵子樹(shù)，然后訪問(wèn)根結(jié)點(diǎn) 按層次遍歷：先訪問(wèn)第一層上的結(jié)點(diǎn)，然后依次遍歷第二層，第n層的結(jié)點(diǎn)27ABCDEFGHIJKLMNO先序遍歷：后序遍歷：層次遍歷：ABE F I GCDHJ KL NOME I F G B C J K N O L M H D AAB C DE F GH I J KL MNO28n二叉樹(shù)的遍歷方法 先序遍歷：先訪問(wèn)根結(jié)點(diǎn),然后分別先序遍

12、歷左子樹(shù)、右子樹(shù) 中序遍歷：先中序遍歷左子樹(shù)，然后訪問(wèn)根結(jié)點(diǎn)，最后中序遍歷右子樹(shù) 后序遍歷：先后序遍歷左、右子樹(shù)，然后訪問(wèn)根結(jié)點(diǎn) 按層次遍歷：從上到下、從左到右訪問(wèn)各結(jié)點(diǎn)DLRLDR、LRD、DLRRDL、RLD、DRL29ADBCD L RAD L RD L RBDCD L R先序遍歷序列：A B D C先序遍歷:30ADBCL D RBL D RL D RADCL D R中序遍歷序列：B D A C中序遍歷:31ADBC L R DL R DL R DADCL R D后序遍歷序列： D B C A后序遍歷:B32-+/a*b-efcd先序遍歷：中序遍歷：后序遍歷：層次遍歷：- + a *

13、b - c d / e f-+a*b-cd/ef- +a *b - c d/e f-+a*b-c d/e f前綴表達(dá)式、波蘭中綴表達(dá)式（少括號(hào)）后綴表達(dá)式、逆波蘭算術(shù)表達(dá)式與二叉樹(shù)a+b*(c-d)-e/f33算法遞歸算法P129 算法6.1 先序遍歷簡(jiǎn)化算法PreOrderTraverse(BiTree T)if (T) /遞歸條件 T 非空 printf(T-data); PreOrderTraverse(T-lchild); PreOrderTraverse(T-rchild); 34void preorder(JD *bt) if(bt!=NULL) printf(%dt,bt-dat

14、a); preorder(bt-lchild); preorder(bt-rchild); 主程序主程序Pre( T )返回返回pre(T R);返回返回pre(T R);ACBDTBprintf(B);pre(T L);BTAprintf(A);pre(T L);ATDprintf(D);pre(T L);DTCprintf(C);pre(T L);C返回T左是空返回pre(T R);T左是空返回T右是空返回T左是空返回T右是空返回pre(T R);先序序列：A B D C35 非遞歸算法（了解即可） 中序 算法6.2 算法6.3ABCDEFGpiP-A(1)ABCDEFGpiP-AP-B(

15、2)ABCDEFGpiP-AP-BP-C(3)p=NULLABCDEFGiP-AP-B訪問(wèn)：C(4)36pABCDEFGiP-A訪問(wèn)：C B(5)ABCDEFGiP-AP-D訪問(wèn)：C Bp(6)ABCDEFGiP-AP-DP-E訪問(wèn)：C Bp(7)ABCDEFGiP-AP-D訪問(wèn)：C B Ep(8)37ABCDEFGiP-AP-DP-G訪問(wèn)：C B EP=NULL(9)ABCDEFGiP-A訪問(wèn)：C B E G Dp(11)ABCDEFGiP-AP-F訪問(wèn)：C B E G Dp(12)ABCDEFGiP-AP-D訪問(wèn)：C B E Gp(10)38ABCDEFGiP-A訪問(wèn)：C B E G D

16、Fp=NULL(13)ABCDEFGi訪問(wèn)：C B E G D F Ap(14)ABCDEFGi訪問(wèn)：C B E G D F Ap=NULL(15)39n遍歷算法應(yīng)用 （重要）求結(jié)點(diǎn)雙親、孩子、層次，建樹(shù)等按先序遍歷序列建立二叉樹(shù)的二叉鏈表，已知先序序列為： A B C D E G F (其中表示空格字符) P131 算法6.4ABCDEFG A B C D E F G 統(tǒng)計(jì)二叉樹(shù)中葉子結(jié)點(diǎn)個(gè)數(shù)算法求二叉樹(shù)深度算法40BiTree CreateBiTree(BiTree &T) / 算法6.4 / 按先序次序輸入二叉樹(shù)中結(jié)點(diǎn)的值（一個(gè)字符），空格字符表示空樹(shù)， / 構(gòu)造二叉鏈表表示的二叉樹(shù)T。

17、 scanf(%c,&ch); if (ch=#) T = NULL; else if (!(T = (BiTNode *)malloc(sizeof(BiTNode) return ERROR; T-data = ch; / 生成根結(jié)點(diǎn) CreateBiTree(T-lchild); / 構(gòu)造左子樹(shù) CreateBiTree(T-rchild); / 構(gòu)造右子樹(shù) return T; / CreateBiTree41思考題：假設(shè)二叉樹(shù)中結(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu)定義如下：typedef struct BTNode ElemType data; struct BTNode*lchild, *rchild,

18、*next;BTNode, *BiTree;其中l(wèi)child和rchild用來(lái)保存結(jié)點(diǎn)的左、右孩子結(jié)點(diǎn)的指針，next保存結(jié)點(diǎn)在后序遍歷序列中的直接后繼結(jié)點(diǎn)的指針。初始時(shí)，二叉樹(shù)中各結(jié)點(diǎn)的next均為空。試編寫(xiě)一算法，為二叉樹(shù)中各結(jié)點(diǎn)的next填上合適的指針值，即其在后序遍歷序列中的直接后繼結(jié)點(diǎn)的指針。42n6.5 二叉樹(shù)的應(yīng)用n哈夫曼樹(shù)(Huffman)帶權(quán)路徑長(zhǎng)度最短的樹(shù) 定義 路徑：從樹(shù)中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的分支構(gòu)成這兩個(gè)結(jié)點(diǎn)間的 路徑長(zhǎng)度：路徑上的分支數(shù) 樹(shù)的路徑長(zhǎng)度：從樹(shù)根到每一個(gè)結(jié)點(diǎn)的路徑長(zhǎng)度之和 樹(shù)的帶權(quán)路徑長(zhǎng)度：樹(shù)中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和結(jié)點(diǎn)到根的路徑長(zhǎng)度權(quán)值其中

19、：記作：kknkkklwlwwpl1 Huffman樹(shù)設(shè)有n個(gè)權(quán)值w1,w2,wn，構(gòu)造一棵有n個(gè)葉子結(jié)點(diǎn)的二叉樹(shù)，每個(gè)葉子的權(quán)值為wi,則wpl最小的二叉樹(shù)叫43例 有4個(gè)結(jié)點(diǎn)，權(quán)值分別為7，5，2，4，構(gòu)造有4個(gè)葉子結(jié)點(diǎn)的二叉樹(shù)abcd7524WPL=7*2+5*2+2*2+4*2=36dcab2475WPL=7*3+5*3+2*1+4*2=46abcd7524WPL=7*1+5*2+2*3+4*3=35nkKKLWWPL144n構(gòu)造Huffman樹(shù)的方法Huffman算法n構(gòu)造Huffman樹(shù)步驟根據(jù)給定的n個(gè)權(quán)值w1,w2,wn，構(gòu)造n棵只有根結(jié)點(diǎn)的二叉樹(shù)，令起權(quán)值為wj在森林中選取兩

20、棵根結(jié)點(diǎn)權(quán)值最小的樹(shù)作左右子樹(shù)，構(gòu)造一棵新的二叉樹(shù)，置新二叉樹(shù)根結(jié)點(diǎn)權(quán)值為其左右子樹(shù)根結(jié)點(diǎn)權(quán)值之和在森林中刪除這兩棵樹(shù)，同時(shí)將新得到的二叉樹(shù)加入森林中重復(fù)上述兩步，直到只含一棵樹(shù)為止，這棵樹(shù)即哈夫曼樹(shù)45例a7b5c2d4a7b5c2d46a7b5c2d4611a7b5c2d46111846例 w=5, 29, 7, 8, 14, 23, 3, 1151429 7823 3111429 7823 1135887151429233581111358191429238715113581929 23148715292914871529113581923421135819234229148715295

21、81135819234229148715295810047Huffman算法實(shí)現(xiàn)一棵有n個(gè)葉子結(jié)點(diǎn)的Huffman樹(shù)有2n-1個(gè)結(jié)點(diǎn)采用順序存儲(chǔ)結(jié)構(gòu)一維結(jié)構(gòu)數(shù)組結(jié)點(diǎn)類(lèi)型定義typedef struct unsigned int weight; unsigned int parent,lchild,rchild;HTNode, *HuffmanTree;type def char *HuffmanCode;48lc data rc pa1 2 3 4 5 6 70 0 0 0 0 0 07 5 2 4 0 0 00 0 0 0 0 0 00 0 0 0 0 0 0(1)lc data rc pa

22、1 2 3 4 5 6 70 0 0 0 3 0 07 5 2 4 6 0 00 0 0 0 4 0 00 0 5 5 0 0 0kx1=3,x2=4m1=2,m2=4(2)lc data rc pa1 2 3 4 5 6 70 0 0 0 3 2 07 5 2 4 6 11 00 0 0 0 4 5 00 6 5 5 6 0 0kx1=2,x2=5m1=5,m2=6(3)lc data rc pa1 2 3 4 5 6 70 0 0 0 3 2 17 5 2 4 6 11 180 0 0 0 4 5 67 6 5 5 6 7 0kx1=1,x2=6m1=7,m2=11(4)a7b5c2d44

23、9nHuffman樹(shù)應(yīng)用 最佳判定樹(shù)等級(jí)分?jǐn)?shù)段比例ABCDE05960697079 8089 901000.050.150.400.300.10a60a90a80a70EYNDYNCYNBYNA70a80a60CYNBYNDYNEYNA80a9060a70EADECa80a70a60a根：編碼 完成指針數(shù)組HC 1n a.葉子-根 b.根-葉子：無(wú)棧非遞歸，算法6.13 例62哈夫曼編碼編程結(jié)果唯一， 左0)，構(gòu)造哈夫曼樹(shù)HT， / 并求出n個(gè)字符的哈夫曼編碼HC if (n=1) return; m = 2 * n - 1; HT = (HuffmanTree)malloc(m+1) * sizeof(HTNode); / 0號(hào)單元未用 for (i=1; i=n; i+) /初始化 HTi.weight=wi-1; HTi.parent=0; HTi.lchild=0; HTi.rchild=0; for (i=n+1; i=m; i+) /初始化 HTi.weight=0; HTi.parent=0; HTi.lchild=0; HTi.rchild=0; 54for (i=n+1; i=m; i+) / 建哈夫曼樹(shù) / 在HT1.i-1中選擇parent為0且weight最小的兩個(gè)結(jié)點(diǎn)， / 其序號(hào)分別為s1和s2。 Select(HT, i-1,