一个二叉查找树,插入建树有错误,大家帮忙看下,急!
[code=C/C++][/code]#include <stdio.h>
#include <conio.h>
#include <malloc.h>
#include <stdlib.h>
typedef struct Tree
{
int data;
struct Tree *lchild;
struct Tree *rchild;
struct Tree *parent;
}Bit_Search_Tree,*BST;
//**************************************************
BST Tree_Search(BST root,int e) //二叉树递归查找
{
BST p;
p=root;
if(p==NULL||p->data==e)
return p;
if(e<p->data)
return Tree_Search(p->lchild,e);
else
return Tree_Search(p->rchild,e);
}
//**************************************************
BST Tree_Search2(BST root,int e) //二叉树非递归查找
{
BST p;
p=root;
while(p&&p->data!=e)
{
if(e<p->data)
p=p->lchild;
else
p=p->rchild;
}
return p;
}
//***************************************************
BST Tree_MINIMUM(BST root) //求子树最小值
{
BST p;
p=root;
while(p->lchild)
p=p->lchild;
return p;
}
//***************************************************
BST Tree_MAXIMUM(BST root) //求子树最大值
{
BST p;
p=root;
while(p->rchild)
p=p->rchild;
return p;
}
//************************************************
void Tree_INSERT(BST *root,int e) //在子树中插入元素
{
BST x,y,z;
x=*root;
while(x)
{
y=x; //y是指示x的路线
if(e<x->data) //寻找插入位置
x=x->lchild;
else
x=x->rchild;
}
z=(BST)malloc(sizeof(Bit_Search_Tree)); //生成节点
z->data=e; //将值赋给节点
z->parent=y;
z->lchild=z->rchild=NULL;
if(y==NULL) //如果y为空，即这是棵子树
(*root)=z;
else //判断插入位置
{
if(z->data<y->data)
y->lchild=z;
else
y->rchild=z;
}
}
//****************************************************
BST Tree_SUCCESSOR(BST root,BST x) //求x的后继
{
BST y;
if(x->rchild)
return Tree_MINIMUM(x->rchild);
else
{
y=x->parent;
while(y&&x==y->rchild)
{
x=y;
y=y->rchild;
}
return y;
}
}
//****************************************************
void Tree_DELETE(BST *root,BST z) //删除节点
{
if(!z->lchild&&!z->rchild) //如节点没有子女
{
free(z);
}
else if(!z->lchild) //如果节点没有左节点
{
BST t;
t=z;
z=z->rchild;
free(t);
}
else if(!z->rchild) //如果节点没有右节点
{
BST t;
t=z;
z=z->lchild;
free(t);
}
else //如果节点有左右子节点
{
BST q,s;
q=z; //寻找z的后继
s=z->rchild;
while(s->lchild)
{
q=s;
s=s->lchild;
}
z->data=q->data; //将后继替换给待删除节点
if(q!=z)
q->lchild=s->rchild;
else
q->rchild=s->rchild;
free(s);
}
}
void DisplayBST(BST root) //输出二叉查找树
{
if(root->lchild)
DisplayBST(root->lchild);
printf("%4d",root->data);
if(root->rchild)
DisplayBST(root->rchild);
}
//****************************************************
int main()
{
BST tree,p;
int data;
printf("crate a bit-search-tree:\n");
for(int i=0;i<10;i++) //输入十个数插入建立一棵二叉查找树
{
printf("input the data of elem:\n");
scanf("%d",&data);
Tree_INSERT(&tree,data);
}
printf("BST:\n");
DisplayBST(tree);
printf("input the data you want search:\n");
scanf("%d",&data);
p=Tree_Search(tree,data); //搜索值为data的节点
printf("delete it\n");
Tree_DELETE(&tree,p); //删除p
printf("BST\n");
DisplayBST(tree);
getch();
return 0;
}
[解决办法]
这里有两个问题：
1）在main()中，只定义了BST tree；并没有对它赋初值NULL，然后就在Tree_INSERT()中使用了。
所以，在定义tree之后，应该初始化为NULL。
2）在Tree_INSERT()中，在while(x)之前应该先对y初始化一次，如果是空树时，在你的函数中，y是未初始化的，，所以在while(x)之前在加一句：y=x;
