【例 5.16】从二叉排序树中删除一个结点。
分析:
(1) 被删除结点为叶结点,则只需修改其双亲结点对应指针为 NULL,并释放该结点。
(2) 被删结点只有左子树或右子树,此时只要将其左子树或右子树,直接成为其双亲
结点的左或右子树。
(3) 若被删结点 K 左右子树均不空,需循该结点的右子树根结点 M 的左子树,一直向
左子树找,直到某结点 x 的左子树为空,则把 x 的右子树改为其父结点的左子树,而用 x
结点取代 K 结点。递归的说法:用结点 x 取代 K,再从右子树中删去结点 x。实际就是用 K
结点的中序下一结点 x 取代 K 结点,也可以用 K 结 点中序前一结点 y 来取代 K 结点,
一句话用最接近被删结点值的结点来代替它。
程序如下:
#include<iostream.h>
#include<stdlib.h>
template<typename T>
class BinaryTree;
template<typename T>
class Node
{
Node<T> *lchild,*rchild;
T info;
public:
Node()
{lchild=NULL;rchild=NULL;}
Node(T data,Node<T> *left=NULL,Node<T> *right=NULL)
{
info=data;
lchild=left;
rchild=right;
}
friend class BinaryTree<T>;
};
template<typename T>
class BinaryTree
{
Node<T> *root; // 二叉树的根指针
void InOrder(Node<T> *Current); // 中序遍历
void Insert(const T &data,Node<T> * &b); //插入结点,第二参数为引用
void Remove(const T &data,Node<T> * &a,Node<T> * &b); // 删除结点
void Destory(Node<T> * Current); // 删除树
public: