樹與二叉樹的基本知識

樹的術語

1. 結點： 樹中的每個元素都稱為結點， 例如上圖中的 A,B,C…
2. 根結點： 位于樹頂部的結點， 它沒有父結點,比如 A 結點。
3. 父結點： 若一個結點有子結點， 那么這個結點就稱為其子結點的父結點。
   例如 A 是 B,C,D 的父節點。
4. 子結點： 一個結點含有的子樹的根結點稱為該結點的子結點。
   例如 B,C,D 是 A 的子節點。
5. 兄弟結點： 具有相同父結點的結點互稱為兄弟結點。
   例如 B,C,D 結點互為兄弟結點。
6. 葉子結點： 沒有子節點的節點， 例如 B,D,F,G,H 結點。
7. 結點的層次： 從根開始定義起， 根為第 1 層， 根的子結點為第 2 層， 以此類推。
8. 樹的深度（高度） ： 樹中結點的最大層次， 右圖中的樹的深度為 4。
9. 結點的度： 一個結點含有的子樹的個數稱為該結點的度。
10. 樹的度： 一棵樹中， 最大的結點的度稱為樹的度,右圖中的樹的度為 3。
11. 子孫： 以某結點為根的子樹中任一結點都稱為該結點的子孫。
12. 森林： 由 n(n>=0)棵互不相交的樹的集合稱為森林。

高度為h的m叉樹和高度為h,度為m的樹有什么區別?

1. 度為m的樹中，必須至少有一個結點有m個孩子結點
2. m叉樹中可以沒有一個結點的孩子數等于m，甚至可以是一棵空樹。

樹的性質：

1. 樹中的結點數等于所有結點的度數加1.
2. 度為m的樹中第i層上至多有m^{i-1}個結點.
3. 高度為h的m叉樹至多有(m^{h} - 1) / (m - 1)個結點
4. 具有n個結點的m叉樹的最小高度為ceil(log_{m}(n(m-1)+1))

二叉樹的基本概念

二叉樹中每個節點的度數均不超過 2。

二叉樹和度為2的有序樹有什么區別?

1. 度為2的樹至少有3個結點，二叉樹可以為空。
2. 度為2的有序樹的孩子結點的左右次序是相對而言的，
   若某個結點只有一個孩子，則這個孩子就不存在左右這個概念。
   二叉樹無論有沒有2個孩子，均需要區分左右孩子結點。

滿二叉樹

性質：

1. 高為 h 的滿二叉樹上一共有 2^h -1 個結點。
2. 高為 h 的滿二叉樹上, 每層都有 2^{h-1}個結點。
3. 高為 h 的滿二叉樹上, 所有的葉子結點都在最后一層。
4. 高為 h 的滿二叉樹上, 除葉子結點外， 每個結點的度都為 2.
5. 高為 h 的滿二叉樹上, 對每個結點從上到下， 從左到右進行編號(從 1 開始), 對于任意編號 i, 若有雙親， 則其雙親結點的編號一定是 floor(i/2), 若有孩子結點, 則左孩子編號為 2i, 右孩子編號為 2i+1.

完全二叉樹

性質：

1. 高為 h, 有 n 個結點的完全二叉樹上, 編號與滿二叉樹的一一對應。
2. 高為 h, 有 n 個結點的完全二叉樹上, 若結點編號 i>floor(n/2), 則該結點一定是葉子結點, 否則是非葉子結點。
3. 高為 h, 有 n 個結點的完全二叉樹上, 葉子結點只會處于最后一層和倒數第二層。
4. 高為 h, 有 n 個結點的完全二叉樹上, 只可能存在一個結點度為 1 并且它肯定只有左孩子沒有右孩子。
5. 高為 h, 有 n 個結點的完全二叉樹上, 若 n 為奇數則所有結點度都為 2， 若為偶數，則有一個結點度為 1。
6. 具有 n 個(n>0)結點的完全二叉樹的高度為 ceil(log_{2} (n+1))或 floor(log_{2} n)+1

6.證明：設完全二叉樹的高度為h，則有
2^{h-1}-1 (高度為h-1的滿二叉樹)<n≤2^{h} -1(高度為h的滿二叉樹)
或 2^{h-1}≤n < 2^h 得 2^{h-1}<n+1 ≤ 2^h ，
即 h-1<log_{2}(n+1)≤h,
故 h= ceil(log_{2} (n+1))
或得 h-1 ≤log_{2}(n)<h,
故 h=floor(log_{2} n)+1

二叉樹的性質

1. 樹中的結點數等于所有結點的度數加1
2. 二叉樹第 k 層上的結點數目最多為 2k-1。 (k≥1)
3. 深度為 k 的二叉樹至多有 2k -1 個結點。 (k≥1)
4. 包含 n 個結點的二叉樹的高度至少為 log2(n+1)。
5. 在任意一棵二叉樹中， 若葉子結點的個數為 n0， 度為 2 的結點數為 n2， 則 n0=n2+1 。
   證明： 結點總數為 n0+n1+n2,有 n0+n1+n2 = n1+2n2+1 化簡得 n0=n2+1

二叉樹的存儲結構

順序存儲結構

事實一：所有完全二叉樹前k個結點的形狀結構完全相同

事實二：完全二叉樹中結點編號與其位置一對應

注: 數組編號應從 1 開始， 不然無法滿足前面所述的二叉樹節點編號之間的關系， 無法做到隨機訪問。 此方法也是后面堆排序的基礎。

鏈式存儲結構

數據結構定義

typedef struct BiTNode{Elemtypedata;struct BiTNode *Ichild, *rchild;
}BiTNode;typedef struct BiTreeBiTNode *root;
}BiTree;

注： 一棵含有 n 個結點的二叉樹采用鏈式存儲結構時， 有 n+1 個指針處于閑置狀態， 也就是沒有高效利用內存

二叉樹的遍歷

設解決某個遞歸問題的時間為T(N)其中處理一半問題的時間為T(N/2)
設其他處理的時間為O(N)
得 T(N) = 2*T(N/2) +c*N
則有T(N/2)= 2*T(N/4)+c*N/2
代入得T(N) = 2*(2*T(N/4)+c*N/2)+c*N
以此類推,
T(N) = 2^k* T(N/2^k)+ k*c*N
當N/2^k=1時，(N=2^k,k=log_{2}N 則有T(N)= 2^{k}*O(1)+k*c*N =N*O(1) + logN*c*N
O(nlogn)

以 A 為根節點的二叉樹可以在左子樹上遞歸劃分

先序遍歷

1. 訪問根節點
2. 先序遍歷左子樹
3. 先序遍歷右子樹

void PreOrder(BiTree T){//先序遞歸遍歷if(T != Null){ visit(T);PreOrder(T->lchild);PreOrder(T->rchild);}
}

中序遍歷

1. 中序遍歷左子樹
2. 訪問根節點
3. 中序遍歷右子樹

void InOrder(BiTreeT) //中序遞歸遍歷if(T != Null){InOrder(T->lchild); visit(T); InOrder(T->rchild);}
}

中序遞歸遍歷時，當訪問到某結點時，其他結點的狀態?
當訪問到任意結點時，都代表以該結點為根的左子樹已經遍歷完成并且都退出了棧；
若該結點是其雙親結點的左孩子，則它的雙親結點此時還沒有被訪問且在棧中;
若該結點是其雙親結點的右孩子，那么此時其雙親結點已經被訪問過并且出棧了。

注：對于系統棧來說，中序遍歷時，左右子樹都訪問完才會出棧雙親結點，而非遞歸遍歷時用戶自己申請的棧一般是雙親結點出棧后才訪問的右子樹(具體代碼可能有不同的實現)

后序遍歷

1. 后序訪問左子樹
2. 后序訪問右子樹
3. 訪問根節點

void PostOrder(BiTree T) //后序遞歸遍歷if(T != Null){PostOrder(T->lchild);PostOrder(T->rchild); visit(T);}
}

后序遞歸遍歷時，當訪問到某結點時，其他結點的狀態?
若該結點是其雙親結點的左孩子，此時其雙親結點都沒有被訪問到并且還在棧中。而且該結點的所有祖先結點也保存在棧中。
若該結點是其雙親結點的右孩子，此時其雙親結點都沒有被訪問到并且還在棧中。而且該結點的所有祖先結點也保存在棧中。
當訪問到任意結點時，都代表以該結點為根的子樹已經全部遍歷完成并且都退出了棧，不會再訪問到。
不管該結點是其雙親結點的左孩子還是右孩子，此時其雙親結點都沒有被訪問到并且還在棧中。而且該結點的所有祖先結點也保存在棧中。

層序遍歷

從上至上、 從左至右依次訪問樹中的每個節點

void LevelOrder(BiTree T) //層序遍歷InitQueue(Q);//聲明隊列BiTree p; //聲明工作結點EnQueue(Q, T);//根結點入隊while(!isEmpty(Q)){//遍歷整棵樹 DeQueue(Q,p);//出隊visit(p); //訪問當前結點if(p->lchild != Null{ //左孩子入隊EnQueue(Q, p->lchild);} if(p->rchild != Null{ //右孩子入隊 EnQueue(Q, p->rchild);}}
}

若想要從下到上， 從右到左(也就是層序遍歷逆序列)的遍歷一棵二叉樹， 只需要在層序遍歷的基礎上再借助一個棧即可實現。

例題

先序序列為 abcd 的不同二叉樹的個數為( )B
A.13 B.14
C.15 D.16

f(4) = 2f(3)+2(f(1)× f(2))

f(3) = 2f(2) + f(1)× f(1)

f(2) = f(1) + f(1) = 2
f(3) = 2f(2) + f(1)× f(1) = 5
f(4) = 2f(3)+2(f(1)× f(2)) = 10+4 = 14

思考： 先序序列為1,2,3,…,n的二叉樹一共有多少種不同的形狀？
f(4) = 2f(3)+2(f(1)× f(2))
= f(3)× f(0) + f(2)× f(1) + f(1)× f(2) + f(0)× f(3), (f(0)=1)

f(n) = f(n-1)× f(0) + f(n-2)× f(1)+… + f(1)× f(n-2) + f(0)× f(n-1), (f(0)=1)