# 樹與二叉樹
## 樹
樹是由n (n≥0）個節點（元素）組成的有限集合（記為T）。其中，如果n=0，它是一棵空樹，這是樹的特例；如果n>0，這n個節點中存在（有僅存在)一個節點作為樹的根，節點，簡稱為根節點，其余節點可分為m (m≥0)個互不相交的有限集T1, T2,..…,Tm，其中每一個子集本身又是一棵符合本定義的樹，稱為根節點的子樹。
### 樹的邏輯表示方法
樹形表示法、文氏圖表示法、凹入表示法和括號表示法
### 樹的基本術語
節點的度與樹的度：樹中某個節點的子樹的個數稱為該節點的度，樹中各節點的度的最大值稱為樹的度，通常將度為m的樹稱為m次樹
分支節點與葉子節點：度不為零的節點稱為非終端節點，又叫分支節點。度為零的節點稱為終端節點或葉子節點。在分支節點中，每個節點的分支數就是該節點的度。
路徑與路徑長度：對于任意兩個節點ki和kj，若樹中存在一個節點序列ki、ki1、ki2、 ..…、kin、 kj，使得序列中除ki外的任一節點都是其在序列中的前一個節點的后繼，則稱該節點序列為由ki到kj的一條路徑，用路徑所通過的節點序列( ki，ki1，ki2，..…，kj )表示這條路徑。路徑的長度等于路徑所通過的邊的數目。
節點的層次和樹的高度：樹中的每個節點都處在一定的層次上。節點的層次從樹根開始定義，根節點為第1層，它的孩子節點為第2層，依次類推，一個節點所在的層次為其雙親節，點所在的層次加1，樹中節點的最大層次稱為樹的高度。
有序樹和無序樹：若樹中各節點的子樹是按照一定的次序從左向右安排的，且相對次序是不能隨意變換的，則稱為有有序樹，否則稱為無序樹。通常意義上的樹都指的是無序樹。
森林：n（n≥0）個互不相交的樹的集合稱為森林。森林的概念與樹的概念十分相近，因為只要把樹的根節點刪去就成了森林。反之，只要給n棵獨立的樹加上一個節點，并把這n棵樹作為該節點的子樹，則森林就變成了樹。
滿m次樹：如果除根節點和葉子節點外，其他節點的度均為m，且所有葉子節點均在同一層，這樣的樹稱為滿m次樹。滿m次樹可以按層從上到下、同層從左到右遍歷，并對層次遍歷的次序編號，根節點編號為1，然后依次遞增，這稱為滿m次樹的層序編號。對于高度為h的滿m次樹，節點編號范圍為1~$\frac {m^h-1}{m-1}$
完全m次樹：對于高度為h的滿m次樹，按滿m次樹的層序編號后，最高層連續缺少編號最大的若干個節點，但最高層中至少有一個節點，這樣的樹稱為高度為h 的完全m次樹。
### 樹的性質
性質1：樹中的節點數等于所有節點的度數加1。
性質2：度為m的樹中第i層上至多有 $m^{i-1}$個節點 (i≥1)。
性質3：高度為h的m次樹至多有 $\frac {m^h-1}{m-1}$ 個節點。s
性質4：具有n個節點的m次樹的最小高度為$\lceil log_m(n(m-1)+1)\rceil$ 。
## 二叉樹
一棵二叉樹中含有n (n≥0)個節點，當n=0時，它是一棵空二叉樹：當n>0時，它由一個根節點和兩棵互不相交的稱為左子樹和右子樹的二叉樹組成。
### 二叉樹性質
性質1：非空二叉樹上葉子節點數等于雙分支節點數加1。
性質2：在完全二叉樹中，對于編號為i的節點（1≤i≤n，n≥1，其中n為節點數）：
- 若2i≤n，則編號為i的節點為分支節點，否則為葉子節點。
- 若編號為i的節點有左孩子節點，則左孩子節點的編號為2i;若編號為i的節點有右孩子節點，則右孩子節點的編號為(2i+1)。
性質3：具有n個( n>0)節點的完全二叉樹的高度為 $\lceil log_2(n+1)\rceil$ 或 $\lfloor log_2n\rfloor +1$
### 二叉樹與樹、森林之間的轉換
森林、樹轉換為二叉樹：
- 在所有相鄰兄弟節點（森林中每棵樹的根節點可看成是兄弟節點）之間加一水平連線。
- 對每個非葉子節點k，除了其最左邊的孩子節點外，刪去k與其他孩子節點的連線。
- 將圖形規整化，所有水平線段以左邊節點為軸心順時針旋轉45。
### 存儲結構
二叉樹的順序存儲結構
```C
typedef ElemType SBTree[MaxSize]; //節點值從數組1開始存放
```
二叉樹的鏈式存儲結構
```C
typedef struct node {
ElemType data;
struct node *lchild;
struct node *rchild;
}BTNode;
```
## 二叉樹的基本運算算法
創建二叉樹
```C
// 括號表示法創建二叉樹
void CreateBTNode(BTNode *&b, char *str)
{
BTNode *St[MaxSize], *p=NULL;
int top=-1, k, j=0;//k 標志左右子樹
char ch;
b=NULL;
ch=str[j];
while(ch!='\0'){
switch(ch){
case '(':top++;St[top]=p;k=1;break;
case ')':top--;break;
case ',':k=2;break;
default:p=(BTNode *)malloc(sizeof(BTNode));
p->data=ch;p->lchild=p->rchild=NULL;
if(b==NULL)
b=p;
else{
switch(k){
case 1:St[top]->lchild=p;break;
case 2:St[top]->rchild=p;break;
}
}
}
ch=str[++j];
}
}
```
求二叉樹高度
```C
int BTNodeDepth(BTNode *b)
{
int lchilddep, rchilddep;
if(b==NULL)
return 0;
else{
lchilddep=BTNodeDepth(b->lchild);
rchilddep=BTNodeDepth(b->rchild);
return lchilddep>rchilddep?(lchilddep+1):(rchilddep+1);
}
}
```
#### 二叉樹的遞歸算法設計
一般遞歸模型
```
f(b)=c 當 b=NULL;
f(b)=g(fun(b->lchild),fun(b->rchild),c1) 其他情況；
```
```C
DataType fun(BTNode *b)
{
if(b==NULL)
return(c);
else
return g(fun(b->lchild),fun(b->rchild),c1);
}
```
##
