一、定義與性質
定義
二叉排序樹(Binary Sort Tree)又稱二叉查找(搜索)樹(Binary Search Tree)。其定義為：二叉排序樹或者是空樹，或者是滿足如下性質的二叉樹：
①若它的左子樹非空，則左子樹上所有結點的值均小于根結點的值；
②若它的右子樹非空，則右子樹上所有結點的值均大于根結點的值；
③左、右子樹本身又各是一棵二叉排序樹。
上述性質簡稱二叉排序樹性質(BST性質)，故二叉排序樹實際上是滿足BST性質的二叉樹。

性質
（1） 二叉排序樹中任一結點x，其左(右)子樹中任一結點y(若存在)的關鍵字必小(大)于x的關鍵字。
（2） 二叉排序樹中，各結點關鍵字是惟一的。
注意：
實際應用中，不能保證被查找的數據集中各元素的關鍵字互不相同，所以可將二叉排序樹定義中BST性質(1)里的"小于"改為"大于等于"，或將BST性質(2)里的"大于"改為"小于等于"，甚至可同時修改這兩個性質。
（3） 按中序遍歷該樹所得到的中序序列是一個遞增有序序列。
二、插入與刪除
插入與刪除操作是二叉排序樹中最常用也是最重要的兩個操作。
插入過程是：
(a)若二叉排序樹T為空，則為待插入的關鍵字key申請一個新結點，并令其為根；
(b)若二叉排序樹T不為空，則將key和根的關鍵字比較：
(i)若二者相等，則說明樹中已有此關鍵字key，無須插入。
(ii)若key<T→key，則將key插入根的左子樹中。
(iii)若key>T→key，則將它插入根的右子樹中。
子樹中的插入過程與上述的樹中插入過程相同。如此進行下去，直到將key作為一個新的葉結點的關鍵字插入到二叉排序樹中，或者直到發現樹中已有此關鍵字為止。
刪除過程：

(1) 進行查找
查找時，令p指向當前訪問到的結點，parent指向其雙親(其初值為NULL)。若樹中找不到被刪結點則返回，否則被刪結點是p。
(2) 刪去p。
刪p時，應將p的子樹(若有)仍連接在樹上且保持BST性質不變。按p的孩子數目分三種情況進行處理。
刪除p結點的三種情況
a.p是葉子(即它的孩子數為0)
無須連接p的子樹，只需將p的雙親parent中指向p的指針域置空即可。

b.p只有一個孩子child
只需將child和p的雙親直接連接后，即可刪去p。
注意：p既可能是parent的左孩子也可能是其右孩子，而child可能是p的左孩子或右孩子，故共有4種狀態。
c.p有兩個孩子
先令q=p，將被刪結點的地址保存在q中；然后找q的中序后繼p，并在查找過程中仍用parent記住p的雙親位置。q的中序后繼p一定 是q的右子樹中最左下的結點，它無左子樹。因此，可以將刪去q的操作轉換為刪去的p的操作，即在釋放結點p之前將其數據復制到q中，就相當于刪 去了q。

#include<stdio.h>

include<stdlib.h>
define maxSize 20
define maxWidth 20
typedef int KeyType; //假定關鍵字類型為整數
typedef struct node { //結點類型
    KeyType key; //關鍵字項
    struct node lchild,rchild;//左右孩子指針
} BSTNode,BSTree;
//typedef BSTNode BSTree; //BSTree是二叉排序樹的類型
//先序遍歷 
void preOrder(BSTree BT) 
{ 
    if(BT!= NULL) 
    { 
        printf("%d",BT->key); 
        preOrder(BT->lchild); 
        preOrder(BT->rchild);

} 

} 
//中序遍歷 
void inOrder(BSTree BT) 
{ 
    if(BT!= NULL) 
    { 
        inOrder(BT->lchild); 
        printf("%d",BT->key); 
        inOrder(BT->rchild); 
    } 
} 
//后序遍歷 
void postOrder(BSTree BT) 
{ 
    if(BT!= NULL) 
    { 
        postOrder(BT->lchild); 
        postOrder(BT->rchild); 
        printf("%d",BT->key); 
    } 
}
//層次法打印樹 
void dispTree(BSTree BT) 
{ 
    BSTree stack[maxSize],*p; 
    int level[maxSize][2],top,n,i,width=4; 
    if(BT!=NULL) 
    { 
        printf("Display a tree by hollow means.\n"); 
        top=1; 
        stack[top]=BT;//push root point to stack. 
        level[top][0]=width; 
        while(top>0) 
        { 
            p=stack[top]; 
            n=level[top][0]; 
            for(i=1;i<=n;i++) 
                printf(" "); 
            printf("%d",p->key); 
            for(i=n+1;i<maxWidth;i+=2) 
                printf("--"); 
            printf("\n"); 
            top--; 
            if(p->rchild!=NULL) 
            { 
                top++; 
                stack[top]=p->rchild; 
                level[top][0]=n+width; 
                level[top][1]=2; 
            } 
            if(p->lchild!=NULL) 
            { 
                top++; 
                stack[top]=p->lchild; 
                level[top][0]=n+width; 
                level[top][1]=1; 
            } 
        } 
    } 
}
/ 向二叉排序樹中加入一個結點
要改變指針,需要傳遞指針的指針/
int InsertNode(BSTree *tree, KeyType key)
{
    BSTNode p= NULL, parent = NULL;
    BSTNode pNewNode = (BSTNode )malloc(sizeof(BSTNode));
    if (pNewNode==NULL)
    {
        return -1;
    }
    / 新建結點賦值,特別是左右子結點指針要賦值為NULL /
    pNewNode->key = key;
    pNewNode->lchild = NULL;
    pNewNode->rchild = NULL;
    / 二叉排序樹是空樹 /
    if (tree==NULL)
    {
        *tree = pNewNode;
        return 0;

}
else
{

    p = *tree;
    /* 尋找插入位置 */
    while (NULL != p)
    {
        /* key值已在二叉排序樹中 */
        if (p->key == key)
        {
            return 0;
        }
        else
        {
            parent = p;
            p = (p->key < key) ? p->rchild : p->lchild;
        }
    }
    if (parent->key < key)
    {
        parent->rchild = pNewNode;
    }
    else
    {
        parent->lchild = pNewNode;
    }
    return 0;
}

}
//刪除節點
 / 通過值查找并刪除一個結點 /
 int delNode(BSTree *tree, KeyType key)
 {
     BSTNode p = NULL, q = NULL, parent = NULL, child = NULL;
     p = tree;
     / parent為NULL表示根結點的父親為NULL /
     while (NULL != p)
     {
         if (p->key == key)
         {
             break;
         }
         else
         { parent = p;
         p = (p->key < key) ? p->rchild : p->lchild;
         }
     }
     / p為NULL時， 表示沒有找到結點值為key的結點 /
     if (NULL == p)
     {
         return 0;
     }
     / p, q現在都是保存了待刪結點指針 /
     q = p;

 /* 待刪結點有兩個兒子結點，進行一下轉化 */
 if (NULL != p->lchild && NULL != p->rchild)
 {
//找中序后繼，先右拐，然后左走到底
     parent = p;
     p = p->rchild;
     while (NULL != p->lchild)
     {
         parent = p;
         p = p->lchild;
     }
     /* p中保存了待刪結點右子樹中最左下的結點指針， parent中就保存了該結點父親指針 */
     child = p->rchild;
 }

 /* parent保存待刪結點的父親結點指針， child保存了待刪結點的兒子結點


//實際刪除的是待刪節點的直接后繼，下面是刪除直接后繼的過程，（待刪結點至多只有一個兒子， 有兩個會轉化為0個或1個右結點）

  待刪結點是根結點 */
 if (NULL == parent)
 {
     *tree = child;
 }
 else
 {
     /*待刪結點是父親結點的左兒子*/
     if (parent->lchild == p)
     {
         parent->lchild = child;
     }
     else
     {
         parent->rchild = child;
     }
//將實際刪除的節點的key值賦給原先要刪除的節點
     if (p != q)
     {
         q->key = p->key;
     }
 }
 free(p);
 return 0;

}
//二叉排序樹查找
BSTNode SearchBST(BSTree T,KeyType key)
{ //在二叉排序樹T上查找關鍵字為key的結點,成功時返回該結點位置,否則返回NUll
    if(T==NULL) //遞歸的終結條件
        return NULL; //T為空,查找失敗;
    if(key==T->key)
        //成功,返回找到的結點位置
    {
        printf("Got it!");
        return T;
    }

if(key<T->key)
    return SearchBST(T->lchild,key);
else
    return SearchBST(T->rchild,key);//繼續在右子樹中查找

} //SearchBST
int main()
{
    int n; 
    BSTree *B=NULL;
    printf("Input number to initialize a BSTree:");
    while(1)
    {
        scanf("%d",&n);
        if(n==0) break;
        InsertNode(&B, n);
    }

    dispTree(B);
    printf("PreOrder：");
    preOrder(B);
    printf("\n");
    printf("Search a node:");
    scanf("%d",&n);
    SearchBST(B,n);
    printf("\n");
    printf("Delete a node:");
    scanf("%d",&n);
    delNode(&B,n);
    dispTree(B);
    printf("PreOrder：");
    preOrder(B);
    printf("\n");
    return 1;
}</pre>