目錄
樹的基礎知識
二叉樹特點：
二叉樹具有五種基本形态：
斜樹
滿二叉樹
特點：
完全二叉樹
特點：
二叉樹性質
二叉樹周遊方法
推導周遊結果
樹的基礎知識
- 結點擁有的子樹數稱為結點的度（Degree）。有幾個分支度就是多少。
- 度為0的結點稱為葉結點（Leaf）或終端結點。度不為0的結點稱為非終端結點或分支結點。
- 分支結點也稱為内部節點。（除根結點之外）。
- 樹的度為樹内各結點的度的最大值。
- 樹中結點的最大層次稱為樹的深度（Depth）或高度。
- 如果将樹中結點的各子樹看成從左至右是有次序的，稱為該樹為有序樹，否則稱為無序樹。
二叉樹特點：
- 每個結點最多有兩棵子樹，是以二叉樹中不存在度大于2的結點。沒有子樹或者有一科子樹都是可以的。
- 左子樹和右子樹是有順序的。
- 即使樹中某結點隻有一顆子樹，也要區分它是左子樹還是右子樹。
二叉樹具有五種基本形态：
- 空二叉樹。
- 隻有一個根結點。
- 根結點隻有左子樹
- 根結點隻有右子樹
- 根結點既有左子樹又有右子樹
斜樹
所有的結點都隻有左子樹的二叉樹叫左斜樹。（右斜樹）
滿二叉樹
分支結點都存在左子樹和右子樹，并且所有葉子都在同一層上。
特點：
- 葉子結點隻能出現在最下一層。
- 飛葉子結點的度一定是2。
- 在同樣深度的二叉樹中，滿二叉樹的結點個數最多，葉子結點最多。
完全二叉樹
對一棵具有n個結點的二叉樹按層序編号，如果編号的結點與同樣深度的滿二叉樹中的編号為i的結點在二叉樹中位置完全相同，則這棵二叉樹稱為完全二叉樹。
特點：
- 葉子結點隻能出現在最下兩層。
- 最下層的葉子一定集中在左部連續位置。
- 倒數二層，若有葉子結點，一定都在右部連續位置。
- 如果結點度為1，則該結點隻有做孩子，即不存在隻有右子樹的情況。
- 同樣節點數的二叉樹，完全二叉樹的深度最小。
二叉樹性質
性質1：在二叉樹的第i層上至多有
個結點（i>=1）。
性質2：深度為k的二叉樹至多有
個結點（k>=1）。
性質3：對任何一棵二叉樹T，如果其終端結點數為
，度為2的結點數為
，則
=
+1。
性質4：具有n個結點的完全二叉樹的深度為（
）+1 （x）定義為不大于x的最大整數。
性質5：如果對一棵有n個結點的完全二叉樹（其深度為（
）+1 ）的結點按層序編号（從第1層到第（
）+1 層，每層從左到右），對任一結點i（i<=n && i>=1）有：
- 如果i=1，則結點i是二叉樹的根，無雙親；如果i>1，則其雙親是結點不大于i/2的最大整數。
- 如果2i>n，則結點i無左孩子（結點i為葉子結點）；否則其左孩子是結點2i。
- 如果2i+1>n，則結點i無右孩子；否則其右孩子是結點2i+1。
二叉樹周遊方法
- 前序周遊
規則：若二叉樹為空，則空操作傳回，否則先通路根結點，然後前序周遊左子樹，再前序周遊右子樹。
typedef struct BiTNode
{
int data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
/*二叉樹的前序周遊算法*/
void preOrderTraverse(BiTree T)
{
if(T == NULL)
return;
printf("%d",T->data);
preOrderTraverse(T->lchild);
preOrderTraverse(T->rchild);
}
- 中序周遊
規則：若樹為空，則空操作傳回，否則從根結點開始（注意并不是先通路根結點），中序周遊根結點的左子樹，然後是通路根結點，最後中序周遊右子樹。
/*二叉樹的中序周遊算法*/
void midOrderTraverse(BiTree T)
{
if(T == NULL)
return;
midOrderTraverse(T->lchild);
printf("%d",T->data);
midOrderTraverse(T->rchild);
}
- 後序周遊
規則：若樹為空，則空操作傳回，否則從左到右先葉子後結點的方式周遊通路左右子樹，最後是通路根結點。
/*二叉樹的後序周遊算法*/
void postOrderTraverse(BiTree T)
{
if(T == NULL)
return;
postOrderTraverse(T->lchild);
postOrderTraverse(T->rchild);
printf("%d",T->data);
}
- 層序周遊
規則：若樹為空，則操作傳回，否則從樹的第一層，也就是根結點開始通路，從上而下逐層周遊，在同一層中，按從左到右的順序對結點逐個通路。
推導周遊結果
思路：就是由兩種周遊結果推到樹的結構，然後根據樹寫出另一周遊的順序。
已知前序和中序推導後續周遊順序
已知中序和後序推導前序周遊順序
方法：根據前序和後序判斷根結點，再由中序周遊确定哪些是左子樹，哪些是右子樹。
注：已知前序周遊和中序周遊可以确定唯一一棵二叉樹。
已知中序周遊和後序周遊可以确定唯一一棵二叉樹。
但是已知前序和後序周遊不能确定唯一的二叉樹。