# Binary Tree 二元樹
## 定義
二元樹是一種特殊的樹。在二元樹中，每個內部節點的最多只有兩個child，分別是左子樹和右子樹，而左子樹和右子樹也都是二元樹。此外，二元樹可以為空。
* 樹 (tree) 與二元樹 (binary tree) 的比較
|樹 tree|二元樹 binary tree|
|:----:|:----:|
|不可以為空|可以為空(空集合)|
|Node's degree $\geq$ 0即可|0 $\leq$ Node's degree $\leq$ 2|
|子樹之間無次序/方向之分|子樹有左右之分|
## 基本定理
**定理一 :** 令root level=1。二元樹中第 $i$ level 之最多node數 = ==$2^{i-1}$個==。($i\geq1$)
:::info
**<pf>**(數學歸納法)
1.當level=$1$時，最多只有root一個點，符合$2^{1-1}=2^0=1$，初值成立。
2.令level=$i-1$時，此定理成立。
3.當level=$i$時，其最多Node數必定是
=$(第i-1個$level$之最多$Node$數)×2=2^{(i-1)-1}×2=2^{i-1}$。
因此，由數學歸納法得證。
:::
**定理二 :** 令root level=1。高度為$K$之Binary Tree，其最多的Node數= ==$2^K-1$==。
:::info
**<pf>**
$\sum^k_{i=1}$(level $i$ 之Node數)
=2^0^+2^1^+2^2^+...+2^K-1^=(2^(K-1)+1^-2^0^)/(2-1)=2^K^-1
:::
**定理二(反向) :** 令root level=1。若Binary Tree 有$n$個node,則最小高度 = ==$\lceil\log_2(n+1)\rceil$== ，最大高度 = ==$n$==。
:::info
**<pf>**
$2^K-1=n\rightarrow2^K=n+1\rightarrow K=\log_2(n+1)$
:::
**定理三 :** 令root level=1。給定一個非空的Binary Tree，若Leaf的個數有$n_0$個，Degree=$2$的node個數有$n_2$個，則 ==$n_0=n_2+1$==。
:::info
**<pf>**
假設N代表Node總數，N~i~代表degree=i之Node數，B代表分支(Branch)總數。
$\rightarrow N=N_0+N_1+N_2=B+1=[N_1+2×N_2]+1$
$\rightarrow N_0+N_1+N_2=[N_1+2×N_2]+1$
$\rightarrow N_0=N_2+1$
:::
## 種類
### Skewed B.T. 歪斜樹
可分為兩種：
* **left-skewed B.T.**
每個non-leaf皆只有左子點，沒有右子點。
```graphviz
digraph skewed{
b1[label="A"]
b2[label="B"]
b3[label="NULL";color=none]
b4[label="C"]
b5[label="NULL";color=none]
b1->b2;
b1->b3[style=dashed];
b2->b4;
b2->b5[style=dashed];
}
```
* **right-skewed B.T.**
每個non-leaf皆只有左子點，沒有右子點。
```graphviz
digraph skewed{
b1[label="A"]
b2[label="NULL";color=none]
b3[label="B"]
b4[label="NULL";color=none]
b5[label="C"]
b1->b2[style=dashed];
b1->b3;
b3->b4[style=dashed];
b3->b5;
}
```
### Full B.T.
高度為K，具有最多Node數者(2^K^-1),稱之。
```graphviz
digraph{
a->b[weight=1]
a->c[weight=1]
b->d[weight=2]
b->e[weight=1]
c->f[weight=1]
c->g[weight=2]
}
```
### Complete B.T.
高度為K，Node數為N的二元樹，滿足
(1) 2^k-1^-1 < N < 2^K^-1
(2) Node的編號順序與==同高度的 Full B.T.== 的前N個Node編號一一對應。(即Node的增長順是由上至下，由左而右依序增長)
```graphviz
digraph{
a
b
c
d
e
f[style=dashed]
g[style=dashed]
a->b[weight=1]
a->c[weight=1]
b->d[weight=2]
b->e[weight=1]
c->f[weight=1;style=dashed]
c->g[weight=2;style=dashed]
}
```
:::info
* Complete B.T. 之定理:
一個Complete B.T.有N個Node編號:1~n，若某Node編號為 $i$，則
(1) 其左子點編號：$2i$ (若$2i>n$，則無左子點)
(2) 其右子點編號：$2i+1$ (若$2i+1>n$，則無右子點)
(3) 其父點編號：$[\frac{i}{2}]$ (取整數) (若$[\frac{i}{2}]<1$，則無父點)
<pf>(數學歸納法，只要證(1),(2)自然得證，再由(1)(2)，(3)自然得證)
(1)當$i=1$時，此點必為root，而root若有左子點，必為root的下一個Node，因此編號為 $2$，滿足$2×i=2×1=2$，初值成立。
(2)令編號$\geq i-1$時，此定理成立。
(3)當編號$=i$時，其左子點的編號必為編號$i-1$的Node的左子點編號$+2$，得到$2(i-1)+2=2$。
因此，由數學歸納法得證。
:::
## strict B.T. (嚴格的)
在B.T.中，任何的non-leaf必有兩個子點。
## Binary Tree Traversal (尋訪)
Binary Tree 的 Node具有指向兩個 child 的 pointer , traversal 以當前所在的 Node 為基準，所能做的事情有三種:
* V : Visiting，在當前所在的Node進行print out(顯示資料)、assign(賦值)、刪除資料等等。
* L : 移動到 left child。
* R : 移動到 right child。
```graphviz
digraph graphname{
subgraph cluster_visit{
label="V";
fontcolor=red;
color=none;
A[label="A"; color=red;];
}
subgraph{
B[label="B"];
C[label="C"];
}
A->B[label="L"; color=blue; fontcolor=blue]
A->C[label="R"; color=green; fontcolor=green]
}
```
以上面的圖為例，假設CurrentNode在A，leftchild和rightchild分別是B和C，加上一項限制:「L一定要在R之前」，便能產生三種尋訪的方式 :
* **前序走訪 pre-order(VLR)**
先對**A**進行Visiting，接著前往left child(**B**)進行Visiting，再前往right child (**C**)進行Visiting。
(若child指向NULL則忽略。)
* **中序走訪 in-order(LVR)**
先對A的left child(**B**)進行 Visiting，接著回到**A**進行Visiting，在前往right child(**C**)進行Visiting。
(若child指向NULL則忽略。)
* **後序走訪 post-order(LRV)**
先對A的left child(**B**)進行 Visiting，接著到A的right child(**C**)進行Visiting，再回到**A**進行Visiting。
(若child指向NULL則忽略。)
此外，還有一種尋訪的方式，照著「level由小到大」的順序，由上而下，並在同一個level「由左至右」依序Visiting每個node。我們稱為 **「Level-Order Traversal」**。
### 範例
```graphviz
digraph{
subgraph cluster{
A
B
C
}
D
E
A->B;
A->C;
B->D;
B->E;
}
```
```graphviz
digraph{
A
subgraph cluster{
label=V
B
D
E
}
C
A->B;
A->C;
B->D[weight=2];
B->E[weight=1];
}
```
```graphviz
digraph{
subgraph cluster{
label=V
fontcolor=red
D[color=red]
F[label=NULL;style=dashed]
G[label=NULL;style=dashed]
}
A->B;
A->C;
B->D[weight=2];
B->E[weight=2];
D->F[weight=3;label=L;color=green;fontcolor=green];
D->G[weight=1;label=R;color=green;fontcolor=green];
}
```
pre-order : A->B->D->E->C
in-order : D->B->E->A->C
post-order : D->E->B->C->A
level-order : A->B->C->D->E
### 程式碼
```C=
#include<stdio.h>
#include<stdlib.h>
typedef struct node
{
int data;
struct node *left;
struct node *right;
} node;
typedef struct QueueNode{
node *Q;
struct QueueNode *next;
} Queue;
Queue *front, *rear;
front = rear = NULL;
node *create()
{
node *p;
int x;
printf("Enter data(-1 for no node):");
scanf("%d",&x);
if(x==-1)
return NULL;
p=(node*)malloc(sizeof(node));
p->data=x;
printf("Enter left child of %d:\n",x);
p->left=create();
printf("Enter right child of %d:\n",x);
p->right=create();
return p;
}
int isEmpty(){
if (front == NULL){
return 1;
}
else{
return 0;
}
}
void enqueue(node *a){
Queue *newnode = (Queue*)malloc(sizeof(Queue));
newnode->Q = a;
newnode->next = NULL;
if (front==NULL){
front = newnode;
rear = newnode;
return;
}
rear->next = newnode;
rear = newnode;
}
node* dequeue(){
Queue *tmp;
node *address;
int value;
if (front == NULL){
printf("Queue error!");
return NULL;
}
else{
tmp = front;
address = front->Q;
front = front->next;
free(tmp);
return address;
}
}
void levelorder(node *t){
if (t == NULL){
return;
}
enqueue(t);
while (!isEmpty()){
node *current = front->Q;
printf(" %d",current->data);
if (current->left!=NULL){
enqueue(current->left);
}
if (current->right!=NULL){
enqueue(current->right);
}
dequeue();
}
}
void preorder(node *t)
{
if(t!=NULL)
{
printf(" %d",t->data);
preorder(t->left);
preorder(t->right);
}
}
void inorder(node *t)
{
if(t!=NULL)
{
inorder(t->left);
printf(" %d",t->data);
inorder(t->right);
}
}
void postorder(node *t)
{
if(t!=NULL)
{
postorder(t->left);
postorder(t->right);
printf(" %d",t->data);
}
}
int main()
{
node *root;
root=create();
printf("\nThe preorder traversal of tree is: ");
preorder(root);
printf("\nThe inorder traversal of tree is: ");
inorder(root);
printf("\nThe postorder traversal of tree is: ");
postorder(root);
printf("\nThe levelorder traversal of tree is: ");
levelorder(root);
return 0;
}
```
結果
:::success
Enter data(-1 for no node):1
Enter left child of 1:
Enter data(-1 for no node):2
Enter left child of 2:
Enter data(-1 for no node):-1
Enter right child of 2:
Enter data(-1 for no node):-1
Enter right child of 1:
Enter data(-1 for no node):3
Enter left child of 3:
Enter data(-1 for no node):-1
Enter right child of 3:
Enter data(-1 for no node):-1
The preorder traversal of tree is: 1 2 3
The inorder traversal of tree is: 2 1 3
The postorder traversal of tree is: 2 3 1
The levelorder traversal of tree is: 1 2 3
:::