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

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);

}

}

2）将节点s的右子树重接到其父节点上，作为其父节点的右子树，而后用s替换掉带删节点p。采取这种方法删除节点p后，得到的二叉排序树的形状如上图中的图d所示。采用该方法删除节点的实现代码如下：

/*

采用第二种算法从二叉排序树中删除指针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);

}

}

完整源码

上面重点分析了删除节点的思路和过程，下面给出二叉排序树各种操作实现的完整C代码（含测试代码并加有详细注释）：

[cpp]view plaincopy

/*********************************

二叉排序树的相关操作实现

Author:兰亭风雨Date：2014-02-23

Email:zyb_maodun@163.com

**********************************/

#include<stdio.h>

#include<stdlib.h>

typedefstructNode

{

intdata;

structNode*lchild;

structNode*rchild;

}NODE,*BSTree;

/*

在指针pTree所指的二叉排序树中递归查找关键字为key的元素，

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