2007年2月2日 星期五

Tree and Binary Tree

樹與二元樹

樹的定義:數不允許沒有節點,最少需含有一個樹根節點(Root),含有多個互斥集合(子樹)。
利用鏈結表示樹
Data+Link1+Link2+…
計算樹葉子數演算法
count leaf number algorithm
void countleaf(T)
{
if (T==null) return 0;
else
if (T->Lchild==null) && (T->Rchild==null)
return 1;
else
return(countleaf(T->Lchild)+countleaf(T->Rchild));
}

每個節點擁有的Link數目等於Degree
Binary Tree(二元樹,別名Ordered Tree)
定義:二元樹允許沒有節點,每個節點僅允許Degree介於0-2之間。

二元樹的定理
i level的NODE各數最多為2^(i-1)個
利用數學歸納法證明
樹高為K的二元樹,NODE各數最多有2^k-1個
利用NODE計算式證明
二元樹利用資料結構法來表示
左子樹(指向左子樹樹根) + Data + 右子樹(指向右子樹樹根)
優:刪除與加入節點容易.缺:約浪費掉一半Link空間.對父節點無法得知
二元樹利用陣列表示
將任何二元樹想成完滿二元樹依照編號順序逐步存入陣列中。需耗費一個K維陣列

優:不需要額外的連結空間,找左右節點與父節點均容易。
缺:插入刪除節點不易,對斜曲樹不適用,過於浪費空間。

二元樹的追蹤與走訪:前序(preorder)、中序(inorder)、後序(postorder)
給與中序及任一個前序或後序繪出二元樹技巧。
二元樹追蹤遞迴演算法虛擬碼
範例前序:(採用遞廻方式寫法)
Procedure preorder(T:pointer to B.T. Root)
Begin
If(T!=nul)then begin
Print(T->.Data);
Preorder(T->L.child);
Preorder(T->R.child);
End.
End.
自撰中序:(非recursive)
Inorder(T)
{
Create an empty stack s;
Done=flase;
While(!done)
If(T!=NULL)
s.push(T);
T=T->lchild;
Else
If(!s.isempty())
s.gotTop(T);
printf(T->data);
s.pop();
T=T->rchild;
Else
Done=True;
}
自撰前序:
Preorder(T)
{
Create an empty stack s;
Done=flase;
While(!done)
If(T!=NULL)
Printf(T->data);
s.Push(T);
T=T->lchild;
Else
If(!s.isempty())
s.gotTop();
s.pop();
T=T->Rchild;
Else
Done=True;
}
自撰後序:
Postorder(T)
{
Create an empty stack s;
Done=flase;
While(!done)
If(T!=NULL);
s.push(T);
T=T->lchild;
Else
If(!s.isempty())
s.gotTop();
printf(T->data);
s.pop();
T=T->rchild;
Else
Done=true;
}

二元樹中的應用
Count計算NODE數
計算樹結點數演算法
count node number algorithm
void count(T)
{
if (T==null) return 0;
else
return(count(T->Lchild)+count(T->Rchild)+1);
}
計算樹高:Return(Max(L.child,R.child)+1)
計算樹高度演算法
count height algorithm
void height(T)
{
int Lheight,Rheight;
if (T==null) return 0;
else
Lheight:=height(T->Lchild);
Rheight:=height(T->Rchild);
return(Max(Lheight,Rheight)+1);
}
SWAP二元樹:每個NODE左右子點互換;虛擬碼需用temp暫存元素
交換左右子樹演算法
void SWAP(T)
{
if (T!=null)
SWAP(T->Lchild);
SWAP(T->Rchild);
temp=T->Lchild;
T->Lchild=T->Rchild;
T->Rchild=temp;
}

排序(Sort)二元樹:利用二元搜尋樹(Binary Search Tree)。

二元搜尋樹的定義:
1. 左子樹資料 < Root < 右子樹資料
2. 左右子樹均為二元搜尋樹
特性:使用中序輸出必能將資料數值由小到大排序
搜尋:平均比較次數為O(n);最佳比較次數為O(logn)à當為完滿二元搜尋樹時
TreeàBinary Tree:所有同階元素連結,刪除所有與父親之聯結,僅保留最左連結,所有連結順時針轉45度完成。
ForestàBinary Tree:各Forest的層級子節點互相連接,刪除所有與父親連結,僅保留最左邊連接,各連結順時針轉45度,將所有Forest Root串接。
Binary TreeàForest:將右邊兒子連結逆時針轉45度拉起,打斷所有水平連結。
轉完,前序、中序會相同,後序不會相同!
N個NODE所能畫出幾種不同的二元樹?ANS:組合2N取N除以N+1
4個NODE可以排出14棵二元樹

何謂動態平衡樹?若增刪節點,有可能影響整棵樹的節點變化稱之動態平衡樹。
AVL Tree
不一定是平衡的Binary Search Tree(動態平衡樹)
Balance Tree = All Terminal Node(leafs)in same level
滿足左子樹高度與右子樹高度差不能超過1;左右子樹亦為AVL Tree;平衡係數必為-1,0,1。
需動態調整不平衡狀態!
調整方式:中間鍵值往上拉;左兒子給左;右兒子給右。
新增元素較Root為大往右掛,較小則往左掛。

AVL TREE的insert、delete、search之時間複雜度皆為O(log n)
形成高度h的AVL TREE最少需要幾個NODE?
需要的個數為F(n+2)-1;F意指費柏納西數列函數

Heap Tree
堆積樹(於下面有堆積樹的補充說明)也是動態平衡樹的一種
滿足左子樹高度與右子樹高度差不能超過1;最後加入的元素於該階層的尾部,透過比較大小的方式進行元素互換維持動態平衡。
兩種堆積樹調整模式:
Max Root(Max-Min Heap):根目錄值為樹中最大值,新增元素值必須與他的父親重複比較,較大值階層上升,位置互換。
Min Root(Min-Max Heap):根目錄值為樹中最小值,新增元素值必須與他的父親重複比較,較小值階層上升,位置互換。 - 未說明之堆積樹指的是這種
確定動態平衡時,為同兩個相鄰階層確認數值比較及交換。

Thread Binary Tree
引線二元樹

利用Link List表示具有N個NODE的二元樹,浪費n+1個Links。
將空的Links視為”引線”指標
常用中序引線二元樹

樹在資料結構與演算法中佔有非常重要的地位。這邊的介紹還未包含高等樹!

沒有留言: