資源描述：
《離散數(shù)學第8章+圖論8樹》由會員上傳分享，免費在線閱讀，更多相關內容在教育資源-天天文庫。
1、第八章圖論-28.1Euler圖與Hamilton圖8.2樹8.2.1樹的概念和基本性質8.2.2幾類常用樹根樹有序樹最優(yōu)二叉樹8.2.3生成樹8.3平面圖8.2樹樹的術語起源于植物學和家譜學。早在1857年，英國數(shù)學ArthurCayley(1821—1895)就發(fā)現(xiàn)了樹，當時他正在試圖列舉形為CnH2n+2的化合物的同分異構體。樹具有廣泛的應用，特別在計算機科學與管理科學中。如用樹構造存儲和傳輸數(shù)據的有效編碼，用樹構造最便宜的電話線連接分布式計算機網絡，用樹模擬一系列決策完成的過程等。8.2.1樹的概念和基本性質在圖論中：1、連通的無環(huán)圖稱為樹。2、除根之外，度＝1的頂
2、點稱為葉子，度＞1的頂點稱為分支點或者內點。葉子分支點根8.2.1樹的概念和基本性質3、多個樹稱為森林；4、孤立頂點叫做平凡樹。123456789101512131114平凡樹8.2.1樹的概念和基本性質[定理]T=(V,E)是結點數(shù)n=
3、V
4、?1的樹，則下述命題等價：（1）T是無回路的連通圖；（2）T是連通的，且有n?1條邊；（3）T有n?1條邊，且T中無回路；（4）T的任意兩點間有且只有唯一的通路；（5）T中無回路，但若在T的任一對不相鄰的頂點之間增加一條邊，則構成T中的唯一回路。根樹8.2.2幾類常用樹[有向樹]一個弱連通有向圖，若去掉方向后得到一棵樹，則稱此有向圖為
5、一棵有向樹，記為T。[根樹]一棵有向樹T，若其中有且僅有一個結點v0的入度為0，其余結點的入度為1，則稱T是一棵以v0為根的根樹或外向樹。其中出度為0的結點稱為有根樹的葉子。把外向樹之定向反過來，得到的有向樹叫內向樹。v0v08.2.2幾類常用樹根樹通常畫成倒長的；一個結點的子結點畫在它的下一層，邊的方向省略；“同輩兄弟”畫在同一層。8.2.2幾類常用樹[樹的高度]設有根樹T=(V,A)，v0為樹根。u?V的深度是從v0開始到達u的有向路的長度，T的高度是從v0到T的葉子的最長路的長度。根結點深度為0，稱為第0層；深度同為i的結點構成樹的第i層；具有最大深度的結點的深度稱為
6、樹的深度（高度）。8.2.2幾類常用樹TreeNodeLevelandPathLength8.2.2幾類常用樹有序樹[定義]對有向樹T=(V,A)，若u,v?V且?A，則稱u為v的父親，v為u的兒子。若從u到v存在有向道路，則稱u是v的祖先，v是u的后代（子孫）[有序樹]將各樹的每個結點的所有兒子按次序排列，稱這樣的根樹為有序樹。有序樹的每個結點的出度小于或等于m時，稱為m叉有序樹。有序樹的每個結點的出度只為0或m時，稱為m叉正則有序樹。8.2.2幾類常用樹例設有4個銀幣，已知其中3個一定是真的，真假的區(qū)別在于銀幣的重量，現(xiàn)用一天平設法找出假幣。解：用a、b、c、
7、d分別表示銀幣，a:b表示在天平上作比較。a:b＜＞＝a:cc重c輕＜＞＝a:dd重全真d輕＜＞＝a:ca輕b重＜＝a:cb輕a重＞＝8.2.2幾類常用樹容易看出，上例中方法并不唯一。a,b:c,d＜＞＝a:c＜＞＝d:cc輕a重＞＝a:c＝＜全真d:cb重d輕＜＞＝a輕c重＜＝a:b＝a:bb輕d重＜8.2.2幾類常用樹三、最優(yōu)二叉樹[二叉樹]除樹葉外，每個結點的最多有兩個子結點，分別稱為左子結點和右子結點的根樹稱為二叉樹二叉樹的另外一個定義：二叉樹或者是空樹，或者有一個根結點和兩個分別稱為左右子樹的二叉樹構成。[二叉樹的性質]第i層的結點數(shù)最多為2i；深度為k的二叉樹最
8、多有2k+1-1個結點；記二叉樹出度為2的結點數(shù)目為n2，葉子數(shù)目為n0，則有：n0=n2+1多元樹與二叉樹的對應關系：以結點的最左兒子為對應二叉樹中該結點的左兒子；以結點的右兄弟為對應二叉樹中該結點的右兒子。8.2.2幾類常用樹[滿二叉樹]二叉樹的每個結點的出度或者是0或者是2。滿二叉樹也稱正則二叉樹[完美二叉樹]滿二叉樹且所有結點在同一層。對完美二叉樹的結點按從上到下，同層結點從左到右的原則編號，得到結點從1~2k+1-1的編號序列。得到上述結點編號的二叉樹稱為編號二叉樹。[完全二叉樹]若設二叉樹的高度為h，除第h層外，其它各層(1～h-1)的結點數(shù)都達到最大個數(shù)，第h
9、層從右向左連續(xù)缺若干結點，這就是完全二叉樹。。8.2.2幾類常用樹高度為k的完全二叉樹，其k-1層以上結點構成一棵高度為k-1的完美二叉樹。完全二叉樹的葉結點或者在同一層或者在相鄰的兩層。1671213141511109584231211109876543211671415958423滿二叉樹完美二叉樹完全二叉樹8.2.2幾類常用樹三、最優(yōu)二叉樹[定義]設T是有t片葉子的二叉樹，其中t片葉子分別帶有非負實權，則稱T為加權二叉樹。稱W(T)＝為二叉樹T的權，其中hi為帶權wi的樹葉vi的層數(shù)。在所有的帶權的二叉樹中，
