本测试程序,尝试解决楼主的疑问,所以只是测试了第①种情况,测试用的二叉树只有三个节点:10,5,3
详细情况看函数Status Delete(BiTree &p)里的分析说明.
测试结果:
二叉树的原数据
先序遍历序列: 10 5 3
中序遍历序列: 3 5 10
后序遍历序列: 3 5 10
二叉树(原数据):
10
/
5
/
3
删除节点5之后
先序遍历序列: 10 3
中序遍历序列: 3 10
后序遍历序列: 3 10
二叉树(删除节点5之后):
10
/
3
#include
#include
typedef bool Status;
typedef int TElemType;
typedef int KeyType;
typedef struct BitNode
{
TElemType data;
struct BitNode *lchild,*rchild;
}BitNode, *BiTree;
Status SearchBST(BiTree T,KeyType 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);
}
}
Status InsertBST(BiTree &T, TElemType e)
{
BiTree p;
BiTree s;
if(!SearchBST(T, e, NULL, p))
{
s = (BiTree)malloc(sizeof(BitNode));
s->data = e;
s->lchild = NULL;
s->rchild = NULL;
if(!p)
T = s;
else if(p->data > e)
p->lchild = s;
else
p->rchild = s;
return true;
}
return false;
}
Status Delete(BiTree &p) //注意,输入参数&p使用了"引用"(&)
{
BiTree q;
BiTree s;
//首先,特别要注意函数Delete()里的输入参数是BiTree &p, 使用了"引用"(&),这是C++的关键字.
//而"没有引用"的BiTree p 与 "带有引用"的BiTree &p,是两个很不相同的概念.
//如果函数被修改为Status Delete(BiTree p),那么,这个删除函数不正确.
//父节点是10,其左孩子是节点5,而节点5没有右孩子,只有左孩子(节点3)
//假设父节点10的内存地址是0x6c2b70, 节点5的内存地址是0x6c2b98,
//节点3的内存地址是0x6c2bc0
//父节点10里的数据是: T->data=10, T->lchild=0x6c2b98, T->rchild=0x0
// 节点5里的数据是: p->data=5 , p->lchild=0x6c2bc0, p->rchild=0x0
// 节点3里的数据是: w->data=3 , w->lchild=0x0, w->rchild=0x0
//此时,p=0x6c2b98,指向节点5, p->lchild=0x6c2bc0(节点3), p->rchild=0x0
//执行语句 p=p->lchild 之后, p=0x6c2bc0(这是节点3)
//变量p的数值改变了,因为使用了"引用"&p,马上反馈到其上一层函数,
//也就是函数DeleteBST()里的语句 return DeleteBST(T->lchild,key);
//此时,变量T->lchild的数值也马上改变了,T是父节点10, T->lchild是其左孩子,
//父节点10里的数据变为: T->data=10, T->lchild=0x6c2bc0, T->rchild=0x0
//可以看到,父节点10的左孩子变为节点3(内存地址是0x6c2bc0)
//执行语句delete q删除了节点5, 而父节点10的左孩子也保证是节点3
//函数Status Delete(BiTree &p)的删除节点功能,运作正常.
if(!p->rchild)
{
q=p;
p=p->lchild;
delete q;
}
else if(!p->lchild)
{
q=p;
p=p->rchild;
delete q;
}
else
{
q=p;
s=p->lchild;
while(s->rchild)
{
q=s;
s=s->rchild;
}
p->data=s->data;
if(q!=p)
q->rchild=s->rchild;
else
q->lchild=s->lchild;
delete s;
}
return true;
}
Status DeleteBST(BiTree &T,KeyType 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);
}
return true;
}
//先序遍历
void PreOrder(BiTree T)
{
if(T != NULL)
{
printf("%d ",T->data);
PreOrder(T->lchild);
PreOrder(T->rchild);
}
}
//中序遍历
void InOrder(BiTree T)
{
if(T != NULL)
{
InOrder(T->lchild);
printf("%d ",T->data);
InOrder(T->rchild);
}
}
//后序遍历
void PostOrder(BiTree T)
{
if(T != NULL)
{
PostOrder(T->lchild);
PostOrder(T->rchild);
printf("%d ",T->data);
}
}
int main()
{
BiTree T=NULL;
TElemType data[]={10,5,3};
KeyType key;
int n;
int i;
n=sizeof(data)/sizeof(data[0]);
for(i=0;i {
InsertBST(T,data[i]);
}
printf("二叉树的原数据:");
printf("先序遍历序列: ");
PreOrder(T);
printf("\n");
printf("中序遍历序列: ");
InOrder(T);
printf("\n");
printf("后序遍历序列: ");
PostOrder(T);
printf("\n");
key=5;
printf("\n删除节点%d之后:",key);
DeleteBST(T,key);
printf("先序遍历序列: ");
PreOrder(T);
printf("\n");
printf("中序遍历序列: ");
InOrder(T);
printf("\n");
printf("后序遍历序列: ");
PostOrder(T);
printf("\n");
return 0 ;
}
