Tree - 演算法筆記

樹根位於直徑的中央，能讓樹的高度最小。

演算法請自行參考程式碼，時間複雜度是兩次DFS 的時間。

bool adj[9][9]; // adjacency matrix; int p[9]; // DFS tree ... Tree Tree 「樹」。

樹是一種很特別的圖。

樹的定義是：任兩點之間都相通，並且沒有「環」的圖。

「環」是指繞圈子的循環路線。

樹的定義對初學者來說或許太過抽象。

換個說法吧：一棵樹可想做是由一個點開始，藉由許多條邊不斷地延伸拓展到其他點，而且點和邊都不會重複地被拓展到。

Node 「節點」。

進行延伸拓展的點、被延伸拓展到的點，稱作「節點」，也就是說樹上的點都是「節點」。

【註：為了方便，以下仍稱呼「點」。

】 Branch 「枝」。

延伸拓展所用到的邊稱作「枝」，也就是說樹上的邊都是「枝」。

一個點藉由邊往外延伸拓展，稱作「分枝Branching」。

【註：為了方便，以下仍稱呼「邊」。

】 Root 「根」。

方才提到，一棵樹可想做是由一個點開始分枝──這個點便是「根」。

一棵樹上的每一個點都可以作為根。

Leaf 「葉」。

在一棵樹上選定根後，由根開始不斷分枝，途中所有無法繼續分枝的點皆是「葉」。

也可以不選定根，這種情況下，只連著一條邊的點都是「葉」。

如果樹上總共只有一個點，那麼此點既是根、也是葉。

Level 「層」。

在一棵樹上選定根後，按照拓展的順序（也就是按照每個點離根的距離），可以將樹上的點分層次，使得樹上每一個點都擁有一個層數。

如果改變根，那麼分層的結果就會不同。

還有另一種比較少見的分層方式，是設定所有葉在同一層，由葉開始計算層數。

Parent&Child 「父親」與「小孩」。

在一棵樹上選定根後，以邊相連的任兩點，靠近樹根者相對地稱作「父親」，靠近樹葉者相對地稱作「小孩」。

一個點的父親，是指此點相鄰的點當中，比此點更靠近樹根者。

父親只會有一個，特例是：樹根沒有父親。

一個點的小孩，是指此點相鄰的點當中，比此點更靠近樹葉者。

小孩可以是任意多個，特例是：樹葉沒有小孩。

Ancestor&Descendant 「祖先」與「子孫」。

在一棵樹上選定根後，一個點的父親、父親的父親、……皆是此點的「祖先」。

一個點的小孩、小孩的小孩、……皆是此點的「子孫」。

DirectedTree 在一棵樹上選定樹根後，可以把邊的方向設定成分枝的方向、遠離樹根的方向；也可以把邊的方向設定成朝向樹根的方向，但是這種情況比較少。

Weight 一棵樹可以有權重。

當邊擁有權重時，一棵樹的權重等於樹上所有邊的權重總和。

Forest 「森林」。

很多棵樹稱作一叢「森林」。

只有一棵樹也是「森林」。

樹的特性 1.樹沒有環。

2.樹上所有點之間都相連通。

3.沒有環的圖，就是樹或森林。

沒有環的圖、連通的圖，就是樹。

4.任意兩點之間只有唯一一條路徑。

5.在樹上任意添加一條邊，就會產生環。

6.在樹上任意刪除一條邊，一顆樹就裂成兩棵樹。

7.邊數等於點數減一。

UVa615599 Tree資料結構 AdjacencyLists 樹是一種圖。

圖的資料結構AdjacencyMatrix、AdjacencyLists可以儲存一棵樹。

值得一提的是，一棵樹剛好V個點、V-1條邊，採用AdjacencyLists，空間複雜度O(V+E)=O(V)。

Array 有根樹（有根森林）可以用一條陣列儲存每個點的父親。

空間複雜度O(V)。

intparent[9]; //array TreeProperty 先看個圖片 圖片中省略了點的編號。

distance 一棵樹、兩點之間的「距離」，就是兩點之間的邊數。

由其中一個點開始進行BFS或DFS即可。

UVa1599 depth 一棵有根樹、每個點的「深度」，就是根到每個點的距離。

由根開始進行BFS或DFS即可。

booladj[9][9]; //adjacencymatrix intdepth[9]; //每個點的深度 voidDFS(intx,intpx) //px是x的父親 { for(inty=0;y<9;++y) if(adj[x][y]&&y!=px) { depth[y]=depth[x]+1; DFS(y,x); } } voidtree_depth(introot) { depth[root]=0; DFS(root,root); for(inti=0;i<9;++i) cout<h1)h2=h1,h1=h; elseif(h>h2)h2=h; } diameter=max(diameter,h1+h2); returnh1; } voidtree_diameter() { diameter=0; //初始化 introot=0; //隨便選一個樹根 DFS(root,root); cout<h1[x]) { h2[x]=h1[x];c2[x]=c1[x]; h1[x]=height;c1[x]=child; } elseif(height>h2[x]) { h2[x]=height;c2[x]=child; } } voidDFS1(intx) { h1[x]=h2[x]=0; for(inty=0;y<9;++y) if(adj[x][y]) if(y!=p[x]) { p[y]=x; DFS1(y); record(x,h1[y]+1,y); } else ; //由父親過來的高度，只能留待下一波解決。

} voidDFS2(intx) { if(p[x]!=x) //樹根沒有父親，不必算。

{ inty=p[x]; //上一波沒解決的部分 //之前記錄次高的高度，用意在於這裡！ //當y的最高高度來源是x， //此時y的次高高度，對x來說才是由y過來的高度。

if(c1[y]==x) record(x,h2[y]+1,y); else record(x,h1[y]+1,y); } for(inty=0;y<9;++y) if(adj[x][y]) if(y!=p[x]) DFS2(y); } voidtree_radius() { introot=0; //隨便挑一點當作樹根皆可 p[root]=root; DFS1(root); DFS2(root); intradius=1e9; intdiameter=0; //順便算直徑 for(intx=0;x<9;++x) { radius=min(b_height,h1[x]); diameter=max(diameter,h1[x]); } cout<>x>>y) if(x_is_parent_of_y(x,y)) cout<tout[y]; } voidancestor_descendant(introot) { t=0; for(inti=0;i<9;++i)tin[i]=0; DFS(root,root); intx,y; while(cin>>x>>y) if(x_is_ancestor_of_y(x,y)) cout<>x>>y) cout<=0;i--) if(!ancestor(a[x][i],y)) x=a[x][i]; returna[x][0]; } voiddemo() { t=0; DFS(0,0); //假設樹根為0。

令樹根的祖先是自己。

intx,y; while(cin>>x>>y) cout<