- 若它的左子树不空,则左子树上所有结点的值均小于它的根结构的值
- 若它的右子树不空,则右子树上所有结点的值均大于它的根节点的值
- 它的左右子树也分别是二叉排序树
节点结构
typedef struct BiTNode {
//结点数据
int data;
//左右孩子指针
struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
查找
/*
递归查找二叉排序树T中,是否存在key;
指针f指向T的双亲,器初始值为NULL;
若查找成功,则指针p指向该数据元素的结点,并且返回TRUE;
若指针p指向查找路径上访问的最后一个结点则返回FALSE;
*/
Status SearchBST(BiTree T,int key,BiTree f, BiTree *p){
if (!T) /* 查找不成功 */
{
*p = f;
return FALSE;
}
else if (key==T->data) /* 查找成功 */
{
*p = T;
return TRUE;
}
else if (key<T->data)
return SearchBST(T->lchild, key, T, p); /* 在左子树中继续查找 */
else
return SearchBST(T->rchild, key, T, p); /* 在右子树中继续查找 */
}
数据插入
/* 当二叉排序树T中不存在关键字等于key的数据元素时， */
/* 插入key并返回TRUE，否则返回FALSE */
Status InsertBST(BiTree *T, int key) {
BiTree p,s;
//1.查找插入的值是否存在二叉树中;查找失败则->
if (!SearchBST(*T, key, NULL, &p)) {
//2.初始化结点s,并将key赋值给s,将s的左右孩子结点暂时设置为NULL
s = (BiTree)malloc(sizeof(BiTNode));
s->data = key;
s->lchild = s->rchild = NULL;
//3.
if (!p) {
//如果p为空,则将s作为二叉树新的根结点;
*T = s;
}else if(key < p->data){
//如果key<p->data,则将s插入为左孩子;
p->lchild = s;
}else
//如果key>p->data,则将s插入为右孩子;
p->rchild = s;
return TRUE;
}
return FALSE;
}
节点的删除
//从二叉排序树中删除结点p,并重接它的左或者右子树;
Status Delete(BiTree *p) {
BiTree temp,s;
if((*p)->rchild == NULL){
//情况1: 如果当前删除的结点,右子树为空.那么则只需要重新连接它的左子树;
//①将结点p临时存储到temp中;
temp = *p;
//②将p指向到p的左子树上;
*p = (*p)->lchild;
//③释放需要删除的temp结点;
free(temp);
}else if((*p)->lchild == NULL){
//情况2:如果当前删除的结点,左子树为空.那么则只需要重新连接它的右子树;
//①将结点p存储到temp中;
temp = *p;
//②将p指向到p的右子树上;
*p = (*p)->rchild;
//③释放需要删除的temp结点
free(temp);
}else{
//情况③:删除的当前结点的左右子树均不为空;
//①将结点p存储到临时变量temp, 并且让结点s指向p的左子树
temp = *p;
s = (*p)->lchild;
//②将s指针,向右到尽头(目的是找到待删结点的前驱)
//-在待删除的结点的左子树中,从右边找到直接前驱
//-使用`temp`保存好直接前驱的双亲结点
while (s->rchild) {
temp = s;
s = s->rchild;
}
//③将要删除的结点p数据赋值成s->data;
(*p)->data = s->data;
//④重连子树
//-如果temp 不等于p,则将S->lchild 赋值给temp->rchild
//-如果temp 等于p,则将S->lchild 赋值给temp->lchild
if(temp != *p)
temp->rchild = s->lchild;
else
temp->lchild = s->lchild;
//⑤删除s指向的结点; free(s)
free(s);
}
return TRUE;
}
从二叉排序树中删除结点p,并重接它的左或者右子树
Status Delete(BiTree *p) {
BiTree temp,s;
if((*p)->rchild == NULL){
//情况1: 如果当前删除的结点,右子树为空.那么则只需要重新连接它的左子树;
//①将结点p临时存储到temp中;
temp = *p;
//②将p指向到p的左子树上;
*p = (*p)->lchild;
//③释放需要删除的temp结点;
free(temp);
}else if((*p)->lchild == NULL){
//情况2:如果当前删除的结点,左子树为空.那么则只需要重新连接它的右子树;
//①将结点p存储到temp中;
temp = *p;
//②将p指向到p的右子树上;
*p = (*p)->rchild;
//③释放需要删除的temp结点
free(temp);
}else{
//情况③:删除的当前结点的左右子树均不为空;
//①将结点p存储到临时变量temp, 并且让结点s指向p的左子树
temp = *p;
s = (*p)->lchild;
//②将s指针,向右到尽头(目的是找到待删结点的前驱)
//-在待删除的结点的左子树中,从右边找到直接前驱
//-使用`temp`保存好直接前驱的双亲结点
while (s->rchild) {
temp = s;
s = s->rchild;
}
//③将要删除的结点p数据赋值成s->data;
(*p)->data = s->data;
//④重连子树
//-如果temp 不等于p,则将S->lchild 赋值给temp->rchild
//-如果temp 等于p,则将S->lchild 赋值给temp->lchild
if(temp != *p)
temp->rchild = s->lchild;
else
temp->lchild = s->lchild;
//⑤删除s指向的结点; free(s)
free(s);
}
return TRUE;
}
网友评论