一、定義與性質
定義
二叉排序樹(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。
三、代碼清單
[cpp]
#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;
}
#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;
}
運行結果：
