主题：求教关于二叉排序树的建立、插入、删除操作
alren
[专家分：0] 发布于 2006-06-20 15:45:00
请教各位高手：如何用C语言实现二叉排序树的建立、插入、删除操作呢？
回复列表 （共5个回复）
沙发
英语乞丐5555 [专家分：0] 发布于 2006-06-21 13:32:00
同求,知道的恩人,麻烦告之邮箱yeshebaihe@sina.com
板凳
haozhimin [专家分：0] 发布于 2007-01-14 20:11:00
#include <datastru.h>
#include <string.h>
#include <alloc.h>
#include <stdio.h>
#define KEYTYPE int
typedef struct node
{
KEYTYPE key;
struct * lchild, * rchild;
}BSTNODE;
BSTNODE * searchnode(int w, BSTNODE * r)
//按给定值在二叉排序树中查询
{
BSTNODE * p;
if (r == NULL)
p = NULL;
else
{
if (w == r->key)
p = r;
else if (w> r->key)
p = searchnode(w, r->rchild);
else
p = searchnode(w, r->lchild);
return p;
}
3 楼
haozhimin [专家分：0] 发布于 2007-01-14 20:13:00
BSTNODE* insert_bst(int w, BSTNODE * p)
//将一个元素插入二叉排序树中
{
if (p == NULL)
{
p = malloc(sizeof(BSTNODE));
p->lchild = NULL;
p->rchild = NULL;
p->key = w;
}
else if (w> p->key)
p->rchild = insert_bst(w, p->rchild);
else
p->lchild = insert_bst(w, p->lchild);
return p;
}
BSTNODE * getfather(BSTNODE * p, BSTNODE * r)
{
BSTNODE * pf;
if (r == NULL || p == r)
pf = NULL;
else
{
if (p == r->lchild || p == r->rchild)
pf = r;
else if (p->key > r->key)
pf = getfather(p, r->rchild);
else
pf = getfather(p, r->lchild);
}
return pf;
}
BSTNODE * dele_bst(BSTNODE * p, BSTNODE * r)
{
BSTNODE * temp, * tfather, * pf;
pf = getfather(p, r);
if (p->lchild == NULL && p->rchild == NULL && pf != NULL)
//被删除结点是叶子结点, 不是根结点
if (pf->lchild == p)
pf->lchild = NULL;
else
pf->rchild = NULL;
if (p->lchild == NULL && p->rchild == NULL && pf != NULL)
//被删除结点是叶子结点,又是根结点
r = NULL;
if (p->lchild == NULL && p->rchild != NULL && pf != NULL)
if (pf->lchild == p)
pf->lchild = p->rchild;
else
pf->rchild = p->lchild;
if (p->lchild == NULL && p->rchild != NULL && pf == NULL)
//被删除结点有右孩子,无左孩子.被删结点是根结点
r = p->rchild;
if (p->lchild != NULL && p->rchild == NULL && pf != NULL)
//被删结点有左孩子,无右孩子.被删结点不是根结点
if (pf->lchild == p)
pf->lchild = p->lchild;
else
pf->rchild = p->lchild;
if (p->lchild != NULL && p->rchild == NULL && pf == NULL)
//被删结点有左孩子,无右孩子.被删结点是根结点
r = p->lchild;
if (p->lchild != NULL && p->rchild != NULL)
//被删结点有左孩子,又有右孩子
4 楼
haozhimin [专家分：0] 发布于 2007-01-14 20:15:00
{
temp = p->lchild;
tfather = p;
while (temp->rchild != NULL)
{
tfather = temp;
temp = temp->rchild;
}
p->key = temp->key;
if (tfather != p)
tfather->rchild = temp->lchild;
else
tfather->lchild = temp->lchild;
}
printf("\n");
if (r != NULL)
printf("二叉排序树的根是:%d\n", r->key);
else
printf("二叉排序树空!");
return r;
}
int at(char *str, char ch)
{
int r;
while (*str != '\0' && *str != ch)
str++;
r = (*str == ch)
return r;
}
void print_bst(BSTNODE * p)
{
//中序遍历二叉排序树, 并显示遍历结果
if (p != NULL)
{
print_bst(p->lchild);
printf("%d", p->key);
if (p->lchild != NULL)
printf("<< %d 的左结点:%d >>", p->key, p->lchild->key);
else
printf("<< %d的左结点=NULL", p->key);
if (p->rchild != NULL)
printf("<< %d的右结点:%d >>", p->key, p->rchild->key);
else
printf("<< %d的右结点=NULL", p->key);
printf("\n");
print_bst(p->rchild);
}
}
BSTNODE * creat_bst()
//建立二叉排序树模块
{
BSTNODE * root, * p;
int loop = false;
int s;
root = NULL;
printf("如果要退出,请按< 0 >\n");
do
{
printf("\n");
printf("请输入一个整数:");
scanf("%d", &s);
if (s == 0)
loop = true;
else
{
p = searchnode(s, root);
if (p == NULL)
{
root = insert_bst(s, root);//将元素S插入二叉排序树
print_bst(root);
}
if (root != NULL)
printf("二叉排序树的根为:%d\n", root->key);
}while (!roop);
return root;
}
BSTNODE * insert(BSTNODE * root)
{
//结点插入二叉排序树模块
BSTNODE * p;
int s;
printf("\n");
printf("请输入一个整数:");
scanf("%d", &s);
if (s != 0)
{
p = searchnode(s, root);
if (p == NULL)
{
root = insert_bst(s, root);
print_bst(root);
if (root != NULL) printf("二叉排序树的根为:%d\n", root->key);
}
else printf("该结点值存在, 不插入!\n");
}
return root;
}
5 楼
haozhimin [专家分：0] 发布于 2007-01-14 20:17:00
search_bst(BSTNODE * root)
//查询模块
{
int s;
BSTNODE * p;
char ch[5];
printf("\n");
printf("请输入要查询的结点值:");
scanf("%d",&s);
if ( s!= 0)
{
p = searchnode(s, root);
if (p == NULL)
printf("该结点值不存在!\n");
else
printf("该结点值存在!\n");
}
}
BSTNODE * delete(BSTNODE * root)
//删除模块
{
int s;
BSTNODE * p;
char ch[5];
printf("\n");
printf("请输入要删除的结点值:");
scanf("%d", &s);
if (s != 0)
{
p = searchnode(s, root);
if (p == NULL)
printf("该结点值不存在!\n");
else
{
printf("该结点值存在,要删除吗?(Y/N)\n");
getchar();
gets(ch);
if (at(ch, 'y')||at(ch, 'Y'))
root = dele_bst (p, root);
}
print_bst(root);
return(root);
}
main()
{
BSTNODE * root;
int loop, i;
loop = true;
while (loop)
{
printf("\n\n\n");
printf(" 1.二叉排序树------建立\n");
printf(" 2.二叉排序树------插入\n");
printf(" 3.二叉排序树------查询\n");
printf(" 4.二叉排序树------删除\n");
printf(" 5.二叉排序树------显示\n");
printf(" 0.exit main\n");
scanf("%d", &i);
switch(i)
{
case 0: loop = false;break;
case 1: root = creat_bst();break;
case 2: root = insert(root);break;
case 3: search_bst(root);break;
case 4: root = delete(root);break;
case 5: printf("\n");
if (root != NULL)
printf("二叉排序树的根为:%d\n",root->key);
print_bst(root);break;
}
}
}
我来回复
您所在位置：