构造二叉排序树_序列构造二叉排序树_构造二叉排序树代码(4)

{

BSTreeq,s;

if(!p->lchild)

{//如果左子树为空，则只需重接其右子树

//这里包含了左右子树均为空的情况

q=p;

p=p->rchild;

free(q);

}

elseif(!p->rchild)

{//如果右子树为空，则只需重接其左子树

q=p;

p=p->lchild;

free(q);

}

else

{//如果左右子树都不为空，我们采取第一种方法来重接左右子树，

//我们这里采取修改左子树的方法，也可以修改右子树，方法类似

s=p->lchild;//取待删节点的左节点

//一直向右，最终s为待删节点的前驱节点

//如果将各节点元素按从小到大顺序排列成一个序列，

//则某节点的前驱节点即为序列中该节点的前面一个节点

while(s->rchild)

s=s->rchild;

s->rchild=p->rchild;//将p的右子树接为s的右子树

q=p;

p=p->lchild;//将p的左子树直接接到其父节点的左子树上

free(q);

}

}

/*

采用第二种算法从二叉排序树中删除指针p所指向的节点,

并在保持二叉排序树有序的情况下，将其左右子树重接到该二叉排序树中.

该函数主要用来被后面的删除函数调用

*/

voiddelete_Node2(BSTree&p)

{

BSTreeq,s;

if(!p->lchild)

{//如果左子树为空，则只需重接其右子树

//这里包含了左右子树均为空的情况

q=p;

p=p->rchild;

free(q);

}

elseif(!p->rchild)

{//如果右子树为空，则只需重接其左子树

q=p;

p=p->lchild;

free(q);

}

else

{//如果左右子树都不为空，我们采取第二种方法来重接左右子树，

//我们这里采取修改左子树的方法，也可以修改右子树，方法类似

q=p;

s=p->lchild;//取待删节点的左节点

while(s->rchild)

{//一直向右，最终s为待删节点的前驱节点。

//如果将各节点元素按从小到大顺序排列成一个序列，

//则某节点的前驱节点即为序列中该节点的前面一个节点

q=s;

s=s->rchild;

}

//用s来替换待删节点p

p->data=s->data;

//根据情况，将s的左子树重接到q上

if(p!=q)

q->rchild=s->lchild;

else

q->lchild=s->lchild;

free(s);

}

}

/*

若pTree所指向的二叉排序树中查找到关键字为key的数据元素，

则删除该元素对应的节点，并返回true，否则返回false

如果要删除的恰好是根节点，则会改变根节点的值，因此要传入引用

*/

booldelete_BSTree(BSTree&pTree,intkey)

{

//不存在关键字为key的节点

if(!pTree)

returnfalse;

else

{

if(key==pTree->data)//查找到关键字为key的节点

{

delete_Node1(pTree);

//delete_Node2(pTree);

returntrue;

}

elseif(key<pTree->data)//继续查找左子树

returndelete_BSTree(pTree->lchild,key);

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-24246-4.html