內容提要樹的定義樹的性質根樹有序根樹的遍歷樹的定義定義：不包含簡單回路的連通無向圖稱為樹。森林（連通分支為樹）樹葉/分支點（度為1？）互不同構的6個頂點的樹樹中的通路設T是樹，則u,vVT,T中存在唯一的uv-簡單通路。證明：T是連通圖，u,vVT,T中存在uv-簡單通路。假設T中有兩條不同的uv-簡單通路P1,P2。不失一般性，存在e=(x,y)滿足：eP1但eP2，且在路徑P1上x比y靠近u。令

T*=T-{e}，則T*中包含P2,

于是(P1中的xu-段)+P2+(

P1中的

vy-段)是T*中的xy-通路，T*中含xy-簡單通路(記為P’)，則

P’+e是T中的簡單回路，與樹的定義

。uxyvP2P1有關樹的幾個等價命題設T是簡單無向圖，下列四個命題等價：T是不包含簡單回路的連通圖。//樹的定義T中任意兩點之間有唯一簡單通路。T連通，但刪除任意一條邊則不再連通。T不包含簡單回路，但在任意不相鄰的頂點對之間加一條邊則產生唯一的簡單回路。備注：樹是邊最少的連通圖樹是邊最多的無簡單回路的圖樹中邊和點的數量關系設T是樹，令n=|VT|,m=|ET|,

則m=n-1。證明.對n進行歸納證明。當n=1,

T是平凡樹，結論顯然成立。假設當nk是結論成立。若n=k+1。因為T中每條邊都是割邊，任取eET,T-{e}含兩個連通分支，設其為T1,T2,并設它們邊數分別是m1,m2,頂點數分別是n1,n2,根據歸納假設：m1=n1-1,m2=n2-1。注意：n1+n2=n,

m1+m2=m-1。m=m1+m2+1=n-1。連通圖邊數的下限頂點數為n（

n2）的連通圖，其邊數mn-1。(對于樹，m=n-1,“樹是邊最少的連通圖”)證明：對n進行一般歸納。當n=2時結論顯然成立。設G是邊數為m的連通圖，且|VG|=n>2。任取vVG

，令

G’=G-v,設G’有(1)個連通分支G1,G2,…,G，且Gi的邊數和頂點數分別是mi和ni。有n=n1+n2+…+n+1,

mm1+m2+…+m+

(每個連通分支中至少有一個頂點在G中與刪除的v相鄰)。由歸納假設，mini-1(i=1,2,…)。所以：m

m1+m2+…+m+n1+n2+…+n-+=n-1。與邊點數量關系有關的等價命題設T是簡單無向圖，下列三個命題等價：T是樹。T不含簡單回路，且m=n-1。T連通，且m=n-1。(1)(2),

已證。(2)(3),

若不連通，分支數2，各分支為樹（無簡單回路、連通），則m=n-<n-1，

。(3)(1),

設e是T中任意一條邊，令T’=T-e,

且其邊數和頂點數分別是m’和n,

則m’=m-1=n-2<n-1,

T’是非連通圖。因此，G的任意邊均不在簡單回路中，G中無簡單回路。根樹的定義定義：底圖為樹的有向圖稱為有向樹。定義：若有向樹恰含一個入度為0的頂點，其它頂點入度均為1，則該有向樹稱為根樹，那個入度為

0的頂點稱為根。根樹中的有向通路若v0是根樹T的根,則對T中任意其它頂點vn

,存在唯一的有向v0vn-通路,但不存在vnv0-通路。viv0假設v0

vn-通路p多于１條(b)v0vn假設從

v

到

v0n也有通路(c)v0vkw1入度>1(a)vnvn根樹的圖形表示邊上的方向用約定的位置關系表示根內點（有）樹葉（無）第0層第1層第2層第3層樹高=3（最大的通路長度）根也是內點，除非它是圖中唯一頂點。根樹與

關系關系術語被用于描用根樹容易描述

關系，反之，述根樹中頂點之間的關系。JohnJohn's

ancestorsJohn's

parentJohn's

childJohn's

descendantsJohn’s

siblings根樹的幾個術語m元樹：每個內點至多有m個2元樹也稱為二叉樹完全m元樹(full

m-ary

tree)每個內點恰好有m個平衡：樹葉都在h層或(h-1)層,h為樹高。有序：同層中每個頂點排定次序有序二叉樹通常也簡稱為二叉樹根樹的幾個術語（續）定義：設T是根樹，T中任一頂點v及其所有后代的導出子圖顯然也是根樹(以v為根)，稱為T的根子樹。有序二叉樹的子樹分為左子樹和右子樹即使不是完全二叉數，也可以分左、右，必須注意頂點位置左子樹右子樹根樹（舉例）樹的高度、各頂點所處的層數完全、平衡完全m元樹的頂點數設T是完全m元樹，若T有n個頂點,則有i=(n-1)/m個內點和l=[(m-1)n+1]/m個樹葉.若T有i個內點，則有n=mi+1頂點和l=(m-1)i+1個樹葉.若T有l個樹葉，則有n=(ml-1)/(m-1)

個頂點和i=(l-1))/(m-1)

個內點.n-1=mi

（入度總數=出度總數）n=i+l

（頂點分為內點和樹葉）高度為h的m元樹的頂點數高度為h的m元樹最多有個mh個樹葉。按照高度h進行歸納證明。（第1層頂點最多為m個）若高度為h的m元樹有l個樹葉，則h

logml.如果這棵樹是完全的且平衡的，則有h=logml.mh-1

l

mh有序根樹的遍歷前序遍歷（preorder）T只包含根r，則為r；T的子樹為T1,…,Tn,則為r,preorder(T1),…,preorder(Tn)rT1Tn…有序根樹的遍歷前序遍歷（preorder）akidcgjfebh有序根樹的遍歷后序遍