1、二叉查找樹的實現：
[cpp] include<stdio.h>
#include<stdlib.h>
typedef struct Node{ //定義二叉樹類型
int data;
struct Node *parent;
struct Node *lchild;
struct Node *rchild;
}BiTreeNode,*BiTree;
//二叉樹的查找，如果找到關鍵字為x，則返回指向節點的指針，否則返回null
BiTree BSTSearch(BiTree T,int x){
BiTreeNode *p;
if(T != NULL){
p=T;
while(p != NULL){
if(x == p->data)
return p;
else if(x < p->data)
p = p->lchild;
else
p = p->rchild;
}
}
return NULL;
}
//使用遞歸來實現查找算法
BiTree BSTSearch2(BiTree T,int x){
if(T == NULL)
return NULL;
if(x<T->data)
return BSTSearch2(T->lchild,x);
else if(x>T->data)
return BSTSearch2(T->rchild,x);
else
return T;
}
//二叉查找樹的插入操作
int BSTInsert(BiTree *T,int x){
BiTreeNode *p,*cur,*parent=NULL;
cur = *T;
while(cur != NULL){
if(cur->data == x)
return 0; //已存在關鍵字為x的節點，插入失敗
parent = cur;
if(x<cur->data)
cur = cur->lchild;
else
cur = cur->rchild;
}
p=(BiTreeNode *)malloc(sizeof(BiTreeNode));
if(!p)
return -1;
p->data = x;
p->parent=parent;
p->lchild=NULL;
p->rchild=NULL;
if(!parent)
*T = p;
else if(x < parent->data)
parent->lchild = p;
else
parent->rchild = p;
return 1;
}
//從二叉查找樹中刪除節點s，並使該二叉查找樹性質不變
void DeleteNode(BiTree *s){
BiTree q,x,y;
if(!(*s)->rchild){//如果s的右子樹為空，則s的左子樹成為被刪節點雙親節點的左子樹
q=*s;
*s= (*s)->lchild;
free(q);
}
else if(!(*s)->lchild){//如果s的左子樹為空，則s的右子樹成為被刪節點雙親節點的右子樹
q=*s;
*s= (*s)->rchild;
free(q);
}
else{//如果s的左右子樹都存在，則使s的直接前驅節點代替s，並使其直接前驅節點的左子樹成為其雙親節點的右子樹節點
x=*s;
y=(*s)->lchild;
while(y->rchild){//查找s的直接前驅節點，y為s的直接前驅節點，x為y的雙親節點
x=y;
y=y->rchild;
}
(*s)->data=y->data;//節點s被y取代
if(x!=*s)//如果節點s的左孩子節點不存在右子樹
x->rchild=y->lchild;//使y的左子樹成為x的右子樹
else
x->lchild=y->lchild;
free(y);
}
}
//在二叉查找樹T中找到關鍵字為x的結點，並刪除，刪除成功返回1，否則返回0
int BSTDelete(BiTree *T,int x){
if(!*T)
return 0;
else{
if(x == (*T)->data)
DeleteNode(T);
else if(x<(*T)->data)
return BSTDelete(&(*T)->lchild,x);
else
return BSTDelete(&(*T)->rchild,x);
return 1;
}
}
void InOrderTraverse(BiTree T){
if(T){
InOrderTraverse(T->lchild);
printf("%d \n",T->data);
InOrderTraverse(T->rchild);
}
}
BiTree BSTMinNode(BiTree T){
BiTree p = T;
while(p->lchild)
p = p->lchild;
return p;
}
BiTree BSTMaxNode(BiTree T){
BiTree p = T;
while(p->rchild)
p = p->rchild;
return p;
}
BiTree BSTSearchSuccessor(BiTree T){
if(T->rchild)
return BSTMinNode(T->rchild);
BiTree p = T->parent;
while(p!=NULL && T == p->rchild){
T = p;
p = p->parent;
}
return p;
}
BiTree BSTSearchPredecessor(BiTree T){
if(T->lchild)
return BSTMaxNode(T->lchild);
BiTree p = T->parent;
while(p!=NULL && T == p->lchild){
T = p;
p = p->parent;
}
return p;
}
#define LEN 10
int generate_array(int *array){
int i=0;
srand((unsigned)time(NULL));
for(i=0;i<LEN;i++){
array[i]=rand()%100;
printf("%d ",array[i]);
}
printf("\n");
return 0;
}
int main(void){
int num[LEN];
generate_array(num);
BiTree T = NULL;
int i;
for(i=0;i<LEN;i++){
BSTInsert(&T,num[i]);
}
printf("中序遍歷二叉查找樹：\n");
InOrderTraverse(T);
printf("查找：\n");
for(i=0;i<100;i++){
if(BSTSearch2(T,i))
printf("樹中存在：%d\n",i);
}
printf("最大的結點值為：%d\n",BSTMaxNode(T)->data);
printf("最小的結點值為：%d\n",BSTMinNode(T)->data);
printf("%d",num[4]);
BiTree p;
if(p=BSTSearchPredecessor(BSTSearch2(T,num[4]))){
printf("的前驅結點為：%d \n",p->data);
}
else
printf("沒有前驅結點\n");
if(p=BSTSearchSuccessor(BSTSearch2(T,num[4]))){
printf("後繼結點為：%d \n",p->data);
}
else
printf("沒有後繼結點\n");
printf("刪除小於50的結點：\n");
for(i=0;i<50;i++){
if(BSTDelete(&T,i))
printf("刪除結點：%d\n",i);
}
printf("刪除後中序遍歷：\n");
InOrderTraverse(T);
}
