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);
}
