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視為”引線”指標
常用中序引線二元樹

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