数据结构 二叉排序树
【摘要】 二叉排序树(Binary Sort Tree),又称为二叉查找树。它或者是一棵空树，或者是具有下列性质的二叉树: 如果它的左子树不空，则左子树上所有结点的值均小于它的根结点的值 如果它的右子树不空，则右子树上所有结点的值均大于它的根结点的值。
#include <stdio.h>#include...
二叉排序树(Binary Sort Tree),又称为二叉查找树。它或者是一棵空树，或者是具有下列性质的二叉树:
如果它的左子树不空，则左子树上所有结点的值均小于它的根结点的值
如果它的右子树不空，则右子树上所有结点的值均大于它的根结点的值。
-
#include <stdio.h>
-
#include <stdlib.h>
-
-
#define TRUE 1
-
#define FALSE 0
-
#define OVERFLOW -2
-
-
typedef int TElemType;
-
-
typedef struct BiTNode
-
{
-
TElemType data;
-
struct BiTNode *lchild,*rchild;
-
}BiTNode,*BiTree;
-
-
/****************二叉排序树的查找*******************
-
参数说明：
-
T 二叉排序树
-
key 待查找的关键字
-
f 指向T的双亲
-
p 查找成功则指向该关键字的结点，返回TRUE，
-
失败则指向查找路径的最后一个结点，返回FALSE
-
****************************************************/
-
int SearchBST(BiTree T, TElemType 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)
-
{//关键字小于当前结点的值，则查找其左子树
-
SearchBST(T->lchild,key, T, p);
-
}
-
else
-
{//关键字大于当前结点的值，则查找其右子树
-
SearchBST(T->rchild,key, T, p);
-
}
-
}
-
-
/****************二叉排序树的插入*******************
-
二叉排序树的中序遍历是一个有序序列
-
参数说明：
-
T 二叉排序树
-
key 待插入的关键字
-
插入成功返回TRUE，失败返回FALSE
-
****************************************************/
-
-
int InsertBST(BiTree &T, TElemType key)
-
{
-
BiTree p,s;
-
if (!SearchBST(T,key,NULL,p))
-
{//如果该二叉排序树没有该关键字则插入
-
s = (BiTree)malloc(sizeof(BiTNode));
-
if (!s)
-
{
-
exit(OVERFLOW);
-
}
-
s->data = key;
-
s->lchild = NULL;
-
s->rchild = NULL; //插入新的结点
-
-
if (!p)
-
{//如果当前是一棵空树
-
T = s; //插入s为新的根结点
-
}
-
else if (key < p->data)
-
{//关键字小则为其左子树
-
p->lchild = s;
-
}
-
else
-
{//关键字大则为其右子树
-
p->rchild = s;
-
}
-
return TRUE;
-
}
-
else
-
{//插入失败，即二叉树包含有该关键字的结点
-
return FALSE;
-
}
-
}
-
-
/****************二叉排序树的删除*******************
-
函数int Delete(BiTree &p);p是待删除的结点，并整理其左右子树
-
函数int DeleteBST(BiTree &T, int key)删除值为key的结点
-
****************************************************/
-
-
/*
-
int Delete(BiTree &p)
-
{
-
BiTree q,s;
-
if (p->rchild == NULL)
-
{//如果右子树为空，则直接拼接左子树
-
q = p;
-
p = p->lchild;
-
free(q);
-
}
-
else if (p->lchild == NULL)
-
{//如果左子树为空，则直接拼接右子树
-
q = p;
-
p = p->rchild;
-
free(q);
-
}
-
else
-
{//左右子树均不为空的情况,找到其中序序列的直接前驱
-
q = p;
-
s = p->lchild;
-
while (s->rchild)
-
{//转左，然后向右到尽头(找待删结点的前驱)
-
q = s;
-
s = s->rchild;
-
}
-
p->data = s->data ; //s指向被删结点的直接前驱
-
if (q != p)
-
{//重接q的右子树
-
q->rchild = s->lchild ;
-
}
-
else
-
{//重接q的左子树
-
q->rchild = s->lchild ;
-
}
-
free(s);
-
}
-
-
return TRUE;
-
}
-
*/
-
-
-
int Delete(BiTree &p)
-
{
-
BiTree q,s;
-
if (p->rchild == NULL)
-
{//如果右子树为空，则直接拼接左子树
-
q = p;
-
p = p->lchild;
-
free(q);
-
}
-
else if (p->lchild == NULL)
-
{//如果左子树为空，则直接拼接右子树
-
q = p;
-
p = p->rchild;
-
free(q);
-
}
-
else
-
{//左右子树均不为空的情况,找到其中序序列的直接前驱
-
q = p;
-
s = p->rchild;
-
while (s->lchild)
-
{//转左，然后向右到尽头(找待删结点的前驱)
-
q = s;
-
s = s->lchild;
-
}
-
p->data = s->data ; //s指向被删结点的直接前驱
-
if (q != p)
-
{//重接q的左子树,不相等，则说明q->lchild = s;
-
q->lchild = s->rchild ;
-
}
-
else
-
{//重接q的右子树，相等，则说明s = q->rchild,即只有一个结点的时候;
-
q->rchild = s->rchild ;
-
}
-
free(s);
-
}
-
-
return TRUE;
-
}
-
-
int DeleteBST(BiTree &T, int key)
-
{
-
if (!T)
-
{
-
return FALSE;
-
}
-
else
-
{
-
if (key == T->data)
-
{
-
return Delete(T);
-
}
-
else if (key < T->data)
-
{
-
return DeleteBST(T->lchild, key);
-
}
-
else
-
{
-
return DeleteBST(T->rchild, key);
-
}
-
}
-
}
-
-
void InOrderTraverse(BiTree T)
-
{
-
if (T == NULL)
-
{
-
return;
-
}
-
InOrderTraverse(T->lchild);//访问左子树
-
printf("%d ",T->data);//访问根结点
-
InOrderTraverse(T->rchild);//访问右子树
-
}
-
-
-
int main()
-
{
-
int i,n;
-
int a[] = {62,88,58,47,35,73,51,99,37,93,29,37,36,49,56,48,50};
-
BiTree T = NULL,p;
-
for (i=0; i<sizeof(a) / sizeof(a[0]); i++)
-
{
-
InsertBST(T,a[i]);
-
}
-
printf("该二叉排序树的中序遍历:");
-
InOrderTraverse(T);
-
printf("\n");
-
printf("请输入您要查找的关键字:");
-
scanf("%d",&n);
-
if (SearchBST(T,n,NULL,p))
-
{
-
printf("查找成功!\n");
-
}
-
else
-
{
-
printf("查找失败，待查序列中不包含该关键字\n");
-
}
-
printf("请输入您要插入的关键字:");
-
scanf("%d",&n);
-
InsertBST(T,n);
-
printf("插入关键字 %d 后的二叉树的中序遍历:",n);
-
InOrderTraverse(T);
-
printf("\n");
-
printf("请输入您要删除的关键字:");
-
scanf("%d",&n);
-
if (DeleteBST(T,n))
-
{
-
printf("删除关键字 %d 后的二叉树的中序遍历:",n);
-
InOrderTraverse(T);
-
printf("\n");
-
}
-
else
-
{
-
printf("二叉树不包含关键字 %d\n!",n);
-
}
-
-
return 0;
-
}
文章来源: blog.csdn.net，作者：悦来客栈的老板，版权归原作者所有，如需转载，请联系作者。
原文链接：blog.csdn.net/qq523176585/article/details/17268233
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）