參考文獻： 《資料結構（C語言版）》 嚴蔚敏 吳偉民 編著
開發平台：Ubuntu11.04
編譯器：gcc version4.5.2 (Ubuntu/Linaro 4.5.2-8ubuntu4)
樹（Tree）是n（n≥0）個結點的有限集。在任意一棵非空樹中：（1）有且僅有一個特定的被稱為根（Root）的結點；（2）當n>1時，其餘結點可分為m（m>0）個互不相交的有限集T1，T2，…，Tm，其中每一個集合本身又是一棵樹，并且稱為根的子樹（SubTree）。
結點擁有的子樹數稱為結點的度（Degree）。度為0的結點稱為葉子（Leaf）或終端結點。度不為0的結點稱為非終端結點或分支結點。
樹的度是樹内各結點的度的最大值。
結點的子樹的根稱為該結點的孩子（Child），相應地，該結點稱為孩子的雙親（Parent）。
結點的層次（Level）是從根結點開始計算起，根為第一層，根的孩子為第二層，依次類推。樹中結點的最大層次稱為樹的深度（Depth）或高度。
如果将樹中結點的各子樹看成從左至右是有次序的（即不能互換），則稱該樹為有序樹，否則稱為無序樹。
1、二叉樹
二叉樹（Binary Tree）的特點是每個結點至多具有兩棵子樹（即在二叉樹中不存在度大于2的結點），并且子樹之間有左右之分。
二叉樹的性質：
（1）、在二叉樹的第i層上至多有2i-1個結點（i≥1）。
（2）、深度為k的二叉樹至多有2k-1個結點（k≥1）。
（3）、對任何一棵二叉樹，如果其終端結點數為n0，度為2的結點數為n2，則n0=n2+1。
一棵深度為k且有2k-1個結點的二叉樹稱為滿二叉樹。
可以對滿二叉樹的結點進行連續編号，約定編号從根結點起，自上而下，自左至右，則由此可引出完全二叉樹的定義。深度為k且有n個結點的二叉樹，當且僅當其每一個結點都與深度為k的滿二叉樹中編号從1到n的結點一一對應時，稱之為完全二叉樹。
（4）、具有n個結點的完全二叉樹的深度為不大于log2n的最大整數加1。
（5）、如果對一棵有n個結點的完全二叉樹的結點按層序編号（從第1層到最後一層，每層從左到右），則對任一結點i（1≤i≤n）,有
a、如果i=1,則結點i是二叉樹的根，無雙親；如果i>1，則其雙親是結點x（其中x是不大于i/2的最大整數）。
b、如果2i>n，則結點i無左孩子（結點i為葉子結點）；否則其左孩子是結點2i。
c、如果2i+1>n，則結點i無右孩子；否則其右孩子是結點2i+1。
二叉樹的鍊式存儲：
鍊式二叉樹中的每個結點至少需要包含三個域，資料域和左、右指針域。
二叉樹的周遊：
假如以L、D、R分别表示周遊左子樹、通路根結點和周遊右子樹，則可有DLR、DRL、LRD、LDR、RLD、RDL這六種周遊二叉樹的方案。若限定先左後右，則隻有三種方案，分别稱之為先（根）序周遊、中（根）序周遊和後（根）序周遊，它們以通路根結點的次序來區分。
2、二叉查找樹
二叉查找樹（BinarySearch Tree，也叫二叉搜尋樹，或稱二叉排序樹Binary Sort Tree）或者是一棵空樹，或者是具有下列性質的二叉樹：
（1）、若它的左子樹不為空，則左子樹上所有結點的值均小于它的根結點的值；
（2）、若它的右子樹不為空，則右子樹上所有結點的值均大于它的根結點的值；
（3）、它的左、右子樹也分别為二叉查找樹。
3、二叉查找樹的基本運算
/* bst - binary search/sort tree
* by Richard Tang <[email protected]>
*/
#include <stdio.h>
#include <stdlib.h>
typedef int data_type;
typedef struct bst_node {
data_type data;
struct bst_node *lchild, *rchild;
}bst_t, *bst_p;
（1）、插入
在二叉查找樹中插入新結點，要保證插入新結點後仍能滿足二叉查找樹的性質。例子中的插入過程如下：
a、若二叉查找樹root為空，則使新結點為根；
b、若二叉查找樹root不為空，則通過search_bst_for_insert函數尋找插入點并傳回它的位址（若新結點中的關鍵字已經存在，則傳回空指針）；
c、若新結點的關鍵字小于插入點的關鍵字，則将新結點插入到插入點的左子樹中，大于則插入到插入點的右子樹中。
static bst_p search_bst_for_insert(bst_p *root, data_type key)
{
bst_p s, p = *root;
while (p) {
s = p;
if (p->data == key)
return NULL;
p = (key < p->data) ? p->lchild : p->rchild;
}
return s;
}
void insert_bst_node(bst_p *root, data_type data)
{
bst_p s, p;
s = malloc(sizeof(struct bst_node));
if (!s)
perror("Allocate dynamic memory");
s -> data = data;
s -> lchild = s -> rchild = NULL;
if (*root == NULL)
*root = s;
else {
p = search_bst_for_insert(root, data);
if (p == NULL) {
fprintf(stderr, "The %d already exists.\n", data);
free(s);
return;
}
if (data < p->data)
p->lchild = s;
else
p->rchild = s;
}
}
（2）、周遊
static int print(data_type data)
{
printf("%d ", data);
return 1;
}
int pre_order_traverse(bst_p root, int (*visit)(data_type data))
{
if (root) {
if (visit(root->data))
if (pre_order_traverse(root->lchild, visit))
if (pre_order_traverse(root->rchild, visit))
return 1;
return 0;
}
else
return 1;
}
int post_order_traverse(bst_p root, int (*visit)(data_type data))
{
if (root) {
if (post_order_traverse(root->lchild, visit))
if (visit(root->data))
if (post_order_traverse(root->rchild, visit))
return 1;
return 0;
}
else
return 1;
}
中序周遊二叉查找樹可得到一個關鍵字的有序序列。
（3）、删除
删除某個結點後依然要保持二叉查找樹的特性。例子中的删除過程如下：
a、若删除點是葉子結點，則設定其雙親結點的指針為空。
b、若删除點隻有左子樹，或隻有右子樹，則設定其雙親結點的指針指向左子樹或右子樹。
c、若删除點的左右子樹均不為空，則：
1）、查詢删除點的右子樹的左子樹是否為空，若為空，則把删除點的左子樹設為删除點的右子樹的左子樹。
2）、若不為空，則繼續查詢左子樹，直到找到最底層的左子樹為止。
void delete_bst_node(bst_p *root, data_type data)
{
bst_p p = *root, parent, s;
if (!p) {
fprintf(stderr, "Not found %d.\n", data);
return;
}
if (p->data == data) {
/* It's a leaf node */
if (!p->rchild && !p->lchild) {
*root = NULL;
free(p);
}
/* the right child is NULL */
else if (!p->rchild) {
*root = p->lchild;
free(p);
}
/* the left child is NULL */
else if (!p->lchild) {
*root = p->rchild;
free(p);
}
/* the node has both children */
else {
s = p->rchild;
/* the s without left child */
if (!s->lchild)
s->lchild = p->lchild;
/* the s have left child */
else {
/* find the smallest node in the left subtree of s */
while (s->lchild) {
/* record the parent node of s */
parent = s;
s = s->lchild;
}
parent->lchild = s->rchild;
s->lchild = p->lchild;
s->rchild = p->rchild;
}
*root = s;
free(p);
}
}
else if (data > p->data) {
delete_bst_node(&(p->rchild), data);
}
else if (data < p->data) {
delete_bst_node(&(p->lchild), data);
}
}
4、二叉查找樹的查找分析
同樣的關鍵字，以不同的插入順序，會産生不同形态的二叉查找樹。
int main(int argc, char *argv[])
{
int i, num;
bst_p root = NULL;
if (argc < 2) {
fprintf(stderr, "Usage: %s num\n", argv[0]);
exit(-1);
}
num = atoi(argv[1]);
data_type arr[num];
printf("Please enter %d integers:\n", num);
for (i = 0; i < num; i++) {
scanf("%d", &arr[i]);
insert_bst_node(&root, arr[i]);
}
printf("\npre order traverse: ");
pre_order_traverse(root, print);
printf("\npost order traverse: ");
post_order_traverse(root, print);
printf("\n");
delete_bst_node(&root, 45);
printf("\npre order traverse: ");
pre_order_traverse(root, print);
printf("\npost order traverse: ");
post_order_traverse(root, print);
printf("\n");
return 0;
}
運作兩次，以不同的順序輸入相同的六個關鍵字：
根據前序周遊的結果可得到兩次運作所産生的二叉查找樹的形态并不相同，如下圖：