離散數學英文DMAv7-11.1-2

1、樹/Trees 11.1 樹的概念/Introduction of Trees 11.2 樹的應用/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) 無回路,但增加一條新邊,得一個且僅一個回路;,5) 連通但刪去后便不連通;,6) 每一對結點間有一條且僅有一條路.,給定圖T,以下關于樹的定義是等價的:,1) 無回

3、路的連通圖;,2) 無回路且, 樹的概念,定義樹： 一個無簡單回路的連通無向圖稱為一棵樹/Tree。記為。,定義林： 無簡單回路的無向圖是林/Forests。,定理1樹的基本性質： (1）樹是平面圖。,(2）樹中任二頂點間都有唯一道路。,(3) 去掉樹的任一邊，成了林。,(4)在樹上任添一條邊，產生唯一回路。,(5)設（，），則。 樹是平面圖，且無回路，區(qū)域數，滿足歐拉公式，即。,也可用強歸納法證：（對歸納） (1），顯然成立 (2）假設時成立，時，先移去一條邊，成了兩棵樹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.,定義有向樹：如果有向圖（，）對應的無向圖是樹，稱為有向樹/directed tree。,

5、定義有根樹：如果有向樹存在唯一一個入次為的頂點，其余頂點入次均為，稱此有向樹為有根樹/rooted tree。,定義 根：有根樹中入次為的頂點稱為根/root。,定義 葉：有根樹中出次為的頂點稱為葉/leaf。,定義枝點：有根樹中除葉以外的頂點均為枝點/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。,定義子樹：有根樹（，），是的枝點，a是及其后裔的集合，a是到各后裔道路上邊的集合，則a（a，a）稱為的以為根的子樹/subtree。,注: 以為根的子樹,包含根頂點. 的子樹:以的兒子為根的子樹。,定義有序樹：對枝點的兒子規(guī)定一個次序，如長子，次子等，則此有根樹稱為有序樹/ordered tree。,定義有序樹中的 左兒子/left child：枝點的左邊兒

7、子 右兒子/right child ：枝點的右邊兒子 左子樹/left subtree ：左兒子為根的子樹 右子樹/right subtree ：右兒子為根的子樹,如下圖 作為有根樹：同構 作為有序樹：不同構,定義n元樹：每個枝點最多有n個兒子的有根樹稱為n元樹/n-ary tree。,定義n元正規(guī)樹：每個枝點恰有n個兒子的有根樹稱為n元正規(guī)樹/full n-ary tree。,定義n元樹n=2時稱為二元樹或二叉樹/binary tree。,例: 算術表達式的樹表示(二元樹)： （）（）,+,-,+,*,*,*,+,*,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叉 樹:,每個結點的出度小,于或等于n的根樹.,完全n叉樹:,每個結點的出,度恰好等于n或零的根樹.,正則n叉樹:,所有樹葉層次,相同的完全n叉樹.,定義頂點道路長度和層：頂點的道路長或頂點的層/level是指從根到的邊的條數，記為l（）。,定

9、義樹高：有根樹的樹高/height指到根最遠的頂點的道路長度。 即 l() 性質：n元樹高度為，最多能有nh片葉。,定義n元完全樹：如果樹高為的n元樹有nh片葉，稱此樹為n元完全樹/complete n-ary tree。 注： 完全樹當然是正規(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?,樹:連通且無回路的無向圖.,樹葉:樹中度數為1的結點.,分枝或內點:度數

11、大于1的結點.,森林:每個連通分支是樹的無向,圖.,化學同分異構物,甲烷,乙烷,丙烷,丁烷,異丁烷,家族樹,圖書十進制分類,一,個組織結構的層次體系,各種運,算表達式,判斷樹.,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,分支點nonleaves數為i,則,例 28盞燈擬用一個電源插,座,問需要多少塊四插座接線板?,需要9個接線板.,定理： 若為元樹，則（），其中為枝點數，為葉數。,例：一臺三地址計算機，用一個加法指令可求三個數之和，現要計算個數之

14、和，至少要幾次加法指令？ 解: （） （） 11/2 i=6,但這種樹不唯一，見圖示。,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 硬幣問題 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 硬幣問題,前綴碼/Prefix Codes,1. 計算機是用和序列來表示和存儲信息。通訊編碼也是這樣處理的。 如個英文字母(a-z)，用v位則可表示 v,由于4=165=32，故要用

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

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