二叉查找树的实现 - c++编程基础

1、二叉查找树的实现：

[cpp] include
#include

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(xdata)
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(xdata)
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);

二叉查找树的实现 (一)