1、樹/Trees 11.1 樹的概念/Introduction of Trees 11.2 樹的應(yīng)用/Applications of Trees 11.3 樹的遍歷/Tree Traversal 11.4 生成樹Spanning Trees 11.5 最小生成樹 minimum Spanning Trees,11.1: Introduction to Trees,A tree is a connected undirected graph with no simple circuits. Theorem: There is a unique simple path between any two

2、 of its nodes. An undirected graph without simple circuits is called a forest. You can think of it as a set of trees having disjoint sets of nodes.,G1,G2,G3,G4,Examples of Trees and Graphs that are not Trees,3) 連通且,4) 無(wú)回路,但增加一條新邊,得一個(gè)且僅一個(gè)回路;,5) 連通但刪去后便不連通;,6) 每一對(duì)結(jié)點(diǎn)間有一條且僅有一條路.,給定圖T,以下關(guān)于樹的定義是等價(jià)的:,1) 無(wú)回

3、路的連通圖;,2) 無(wú)回路且, 樹的概念,定義樹： 一個(gè)無(wú)簡(jiǎn)單回路的連通無(wú)向圖稱為一棵樹/Tree。記為。,定義林： 無(wú)簡(jiǎn)單回路的無(wú)向圖是林/Forests。,定理1樹的基本性質(zhì)： (1）樹是平面圖。,(2）樹中任二頂點(diǎn)間都有唯一道路。,(3) 去掉樹的任一邊，成了林。,(4)在樹上任添一條邊，產(chǎn)生唯一回路。,(5)設(shè)（，），則。 樹是平面圖，且無(wú)回路，區(qū)域數(shù)，滿足歐拉公式，即。,也可用強(qiáng)歸納法證：（對(duì)歸納） (1），顯然成立 (2）假設(shè)時(shí)成立，時(shí)，先移去一條邊，成了兩棵樹1和2，有1 1，22，且12，故1212（12）。,Rooted Trees,A rooted tree is a tr

4、ee in which one node has been designated the root. Every edge is (implicitly or explicitly) directed away from the root. You should know the following terms about rooted trees: Parent, child, siblings, ancestors, descendents, leaf, internal node, subtree.,定義有向樹：如果有向圖（，）對(duì)應(yīng)的無(wú)向圖是樹，稱為有向樹/directed tree。,

5、定義有根樹：如果有向樹存在唯一一個(gè)入次為的頂點(diǎn)，其余頂點(diǎn)入次均為，稱此有向樹為有根樹/rooted tree。,定義 根：有根樹中入次為的頂點(diǎn)稱為根/root。,定義 葉：有根樹中出次為的頂點(diǎn)稱為葉/leaf。,定義枝點(diǎn)：有根樹中除葉以外的頂點(diǎn)均為枝點(diǎn)/internal vertices。,樹根root,樹葉 leave,孩子offspring,雙親Parent,Level 0,Level 2,Level 1,Level 3,Level 4,兄弟 sibling,Height（高度）:the largest level number of the tree,定義 父親，兒子，兄弟： 有根樹（,

6、），若（，），則稱是的父親/parent，是的兒子/child。 若（，1），（，2），稱1與2互為兄弟/siblings。,定義 祖先，后裔： 有根樹中，若到有道路存在，則稱是的祖先/ancestors，是的后裔descendants。,定義子樹：有根樹（，），是的枝點(diǎn)，a是及其后裔的集合，a是到各后裔道路上邊的集合，則a（a，a）稱為的以為根的子樹/subtree。,注: 以為根的子樹,包含根頂點(diǎn). 的子樹:以的兒子為根的子樹。,定義有序樹：對(duì)枝點(diǎn)的兒子規(guī)定一個(gè)次序，如長(zhǎng)子，次子等，則此有根樹稱為有序樹/ordered tree。,定義有序樹中的 左兒子/left child：枝點(diǎn)的左邊兒

7、子 右兒子/right child ：枝點(diǎn)的右邊兒子 左子樹/left subtree ：左兒子為根的子樹 右子樹/right subtree ：右兒子為根的子樹,如下圖 作為有根樹：同構(gòu) 作為有序樹：不同構(gòu),定義n元樹：每個(gè)枝點(diǎn)最多有n個(gè)兒子的有根樹稱為n元樹/n-ary tree。,定義n元正規(guī)樹：每個(gè)枝點(diǎn)恰有n個(gè)兒子的有根樹稱為n元正規(guī)樹/full n-ary tree。,定義n元樹n=2時(shí)稱為二元樹或二叉樹/binary tree。,例: 算術(shù)表達(dá)式的樹表示(二元樹)： （）（）,+,-,+,*,*,*,+,*,a,b,c,d,e,f,g,h,i,j,n-ary trees,A roo

8、ted tree is called n-ary if every internal vertex has no more than n children. It is full if every internal vertex has exactly n children. A 2-ary tree is called a binary tree.,n叉 樹:,每個(gè)結(jié)點(diǎn)的出度小,于或等于n的根樹.,完全n叉樹:,每個(gè)結(jié)點(diǎn)的出,度恰好等于n或零的根樹.,正則n叉樹:,所有樹葉層次,相同的完全n叉樹.,定義頂點(diǎn)道路長(zhǎng)度和層：頂點(diǎn)的道路長(zhǎng)或頂點(diǎn)的層/level是指從根到的邊的條數(shù)，記為l（）。,定

9、義樹高：有根樹的樹高/height指到根最遠(yuǎn)的頂點(diǎn)的道路長(zhǎng)度。 即 l() 性質(zhì)：n元樹高度為，最多能有nh片葉。,定義n元完全樹：如果樹高為的n元樹有nh片葉，稱此樹為n元完全樹/complete n-ary tree。 注： 完全樹當(dāng)然是正規(guī)的。,Ordered Rooted Tree,A rooted tree where the children of each internal node are ordered. In ordered binary trees, we can define: left child, right child left subtree, right su

10、btree For n-ary trees with n2, can use terms like “l(fā)eftmost”, “rightmost,” etc.,Trees as Models,Can use trees to model the following: Saturated hydrocarbons Organizational structures Computer file systems In each case, would you use a rooted or a non-rooted tree?,樹:連通且無(wú)回路的無(wú)向圖.,樹葉:樹中度數(shù)為1的結(jié)點(diǎn).,分枝或內(nèi)點(diǎn):度數(shù)

11、大于1的結(jié)點(diǎn).,森林:每個(gè)連通分支是樹的無(wú)向,圖.,化學(xué)同分異構(gòu)物,甲烷,乙烷,丙烷,丁烷,異丁烷,家族樹,圖書十進(jìn)制分類,一,個(gè)組織結(jié)構(gòu)的層次體系,各種運(yùn),算表達(dá)式,判斷樹.,Some Tree Theorems,A tree with n nodes has n1 edges. A full m-ary tree with i internal nodes has n=mi+1 nodes, and =(m1)i+1 leaves. Proof: There are mi children of internal nodes, plus the root. And, = ni = (m1)

12、i+1. Thus, given m, we can compute any of i, n, and from any of the others.,More Theorems,Definition: The level of a node is the length of the simple path from the root to the node. The height of a tree is maximum node level. A rooted m-ary tree with height h is balanced if all leaves are at levels

13、h or h1. Theorem: There are at most mh leaves in an m-ary tree of height h. Corollary: An m-ary tree with leaves has height hlogm . If m is full and balanced then h=logm,定理,其樹葉leaves為t,分支點(diǎn)nonleaves數(shù)為i,則,例 28盞燈擬用一個(gè)電源插,座,問(wèn)需要多少塊四插座接線板?,需要9個(gè)接線板.,定理： 若為元樹，則（），其中為枝點(diǎn)數(shù)，為葉數(shù)。,例：一臺(tái)三地址計(jì)算機(jī)，用一個(gè)加法指令可求三個(gè)數(shù)之和，現(xiàn)要計(jì)算個(gè)數(shù)之

14、和，至少要幾次加法指令？ 解: （） （） 11/2 i=6,但這種樹不唯一，見(jiàn)圖示。,balanced,A rooted m-ary tree of height h is balanced if all leaves are at levels h or h-1.,11.2: Applications of Trees,Binary search trees Decision trees Minimum comparisons in sorting algorithms 8 硬幣問(wèn)題 Prefix codes Huffman coding Game trees,Binary search

15、trees,Form a binary tree for the words: Mathematics,physics,geography,zoology,meteorology,geology,psychology,and chemistry (using alphabetical order),Decision trees,Minimum comparisons in sorting algorithms 8 硬幣問(wèn)題,前綴碼/Prefix Codes,1. 計(jì)算機(jī)是用和序列來(lái)表示和存儲(chǔ)信息。通訊編碼也是這樣處理的。 如個(gè)英文字母(a-z)，用v位則可表示 v,由于4=165=32，故要用

16、位二進(jìn)制才能區(qū)分個(gè)字母。 2. 是否能用不同位數(shù)的二進(jìn)制數(shù)來(lái)表示信息，盡量縮短通訊時(shí)序列的長(zhǎng)度。這是可行的，但要注意:如表示，表示，表示，那么收到是代表還是？ 怎樣避免二義性？,定義前綴：，均為二進(jìn)制序列，如果并列，不是空序列，則稱是的前綴/prefix。即是的前面一部分。,定義 前綴碼：一個(gè)二進(jìn)制序列集合，如果這些二進(jìn)制序列互不為前綴，則稱此集合為前綴碼/prefix code。,例：二元有序加權(quán)樹,每枝點(diǎn)左邊對(duì)應(yīng)權(quán)為0，右邊對(duì)應(yīng)權(quán)1，葉對(duì)應(yīng)一個(gè)碼（即每片葉都有一條從根到葉的路徑，路徑上的權(quán)排成序即為葉的碼，也稱作葉的名。,二元前綴碼,定理,任意一棵二叉樹都可產(chǎn)生一 個(gè)前綴碼。,定理,任何一

17、個(gè)前綴碼都對(duì)應(yīng)一棵二叉樹。,由于枝點(diǎn)才可能是葉的前綴，而枝點(diǎn)不對(duì)應(yīng)一個(gè)碼，故這樣一棵樹所有葉對(duì)應(yīng)的碼構(gòu)成前綴碼。 二元完全樹的葉只有h片（為樹高），用二元樹的前綴碼，最長(zhǎng)碼長(zhǎng)是樹高，最多不超過(guò)h片。,如上例個(gè)字母，就可構(gòu)造樹高為5的二元樹,然后用相應(yīng)的前綴碼分別表示各個(gè)字母，將常用的字母用較短的編碼表示，可縮短整個(gè)通訊序列的長(zhǎng)度，提高效率，即：,目標(biāo):構(gòu)造一個(gè)適當(dāng)?shù)亩行蚣訖?quán)樹，使總長(zhǎng)達(dá)到最小。(對(duì)任何標(biāo)識(shí)符及文字的集合均可采用).,最優(yōu)樹問(wèn)題,帶權(quán)二叉樹: 每片樹葉都帶,權(quán)的二叉樹.,帶權(quán)二叉樹的權(quán):,其中 為,帶權(quán) 的樹葉的通路長(zhǎng)度.,最優(yōu)樹: 在所有帶權(quán),的二叉樹中,最小的那棵樹.,定理 為帶權(quán),的最優(yōu)樹, 則,a) 帶權(quán) 的樹葉,是兄弟.,b) 以樹葉 為兒子的分枝,點(diǎn),其通路長(zhǎng)最長(zhǎng).,的最優(yōu)樹,若將以帶,權(quán) 的樹葉為兒子的分,枝點(diǎn)該為帶權(quán) 的樹葉,得到一新樹 ,也是最優(yōu)樹.,定理 為帶權(quán),解,求解過(guò)程如下,有權(quán) 2,3,5,7,11,13,17,19,23,29,31,37,41求相應(yīng)的最優(yōu)樹.,例,例,3)設(shè)樹葉 帶權(quán) 求 處的符號(hào)串表示出 現(xiàn)頻率為 的字母,2)求T所對(duì)應(yīng)的前綴碼,定義最優(yōu)樹：對(duì)于確定的權(quán)1，2，t，若中取到合適的1，2，t，使（）達(dá)到最小，則稱為關(guān)于權(quán)1，2，t