算法导论—
二叉树
在算法导论中的删除使用的是后继来查找要删除的节点。这是一种通过拷贝的方式,如前面文章所提到的能够在最小程度上较少对树结构带来的变化
下面给出的是计算某个节点下面最大以及最小的值,前驱,后继。以及基于此的删除算法:
最小值
template<class T>
BSTNode<T>* BST<T>::miniMum(BSTNode<T> *x)
{
while(x->left!=0)
{
x=x->left;//若是没有左子树,那么它本身就是最小值
}
return x;
}
/* 函数功能:找到指定节点x子树的最大值/* 函数功能:找到指定节点x子树的最大值/
template<class T>
BSTNode<T>* BST<T>::maximMum(BSTNode<T> *x)
{
while(x->right!=0)
{
x=x->right;//当然包括可能没有右子树的情况,那么这个时候它本身就是最大值
}
return x;
}
/* 找到某个节点的后继节点,返回为后继或者null
存在两种情况:1)若节点x的右子树非空,则x的后继即右子树中最左的节点为其后继
2)若x的右子树为空,且x有一个后继y,则y是x的最低祖先节点,且y的左儿子也是x的祖先
针对的是中序遍历下的后继*/
template<class T>
BSTNode<T>* BST<T>::successor(BSTNode<T> *x)
{
if (x->right!=0)//具体的分两种情况:若右子树不为空,找到右子树的最小节点,为其后继
{
return miniMum(x->right);
}
BSTNode<T> *y=x->parent;//将指针指向父节点,若该节点为某棵子树的最左边的孩子,那么后继为父节点
while(y!=0&& x==y->right)//若该节点为右子树上的一个,那么就要回溯,找到它的祖先
{
x=y;
y=y->parent;
}
return y;
}
/* 找到某个节点的前驱
*/
template<class T>
BSTNode<T>* BST<T>::predecessor(BSTNode<T> *x)
{
if (x->left!=0)//当左子树不为空时,其前驱为左子树中最大的元素
{
return maximMum(x->left);
}
BSTNode<T> *y=x->parent;//当某个节点为某个子树的右边节点,其父节点为其前驱
while(y!=0&& x==y->left)//进行回溯
{
x=y;
y=y->parent;
}
return y;
}
/* 基于后继,进行删除节点
主要分两种情况:1)若没有子女,则直接删除,
2)若只有一个子女,则删除本身
3)若有两个子女,则删除其后继y,y最多只有一个子女,最后,用Y中的关键字和其它数据替换掉z中关键字和其它数据
*/
template<class T>
bool BST<T>::Delete(BSTNode<T> *&z)
{
BSTNode<T>*y,*x;
//T key;
if (z.left==0||z.right==0){
y=z;
}//当左子树或者右子树为空,或者两者都为空,那么删除的节点为该节点,直接将其孩子的指针的parent指向该节点的父节点ok。
else {
y=successor(z);
} //找到后继节点,这个节点是仅次于这个节点的最小节点,它将作为被删除的节点。利用的是拷贝删除方法
if(y->left!=0) {//找到待删除节点的子树,此时待删除节点只哟一个子树或者为空
x=y->left;//若为左子树
}
else {
x=y->right;//若为右子树
}
if (x!=0){//若不为空
x->parent=y->parent;//直接的将父节点的指针指向子节点
}
if (y->parent==0){//当为根时
root=x;
}
else {
if (y->parent->left==y){//确定待删节点的左子树应该位于父节点的左右子树中的某一棵
y->parent->left=x;
}
else
y->parent->right=x;
}
if (y!=z)
{
z.key=y->key;//交换节点中的值
}
return true;
}
版权声明:本文为tang_jin2015原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。