算法导论-二叉树删除 前驱 后继

  • Post author:
  • Post category:其他


算法导论—

二叉树

在算法导论中的删除使用的是后继来查找要删除的节点。这是一种通过拷贝的方式,如前面文章所提到的能够在最小程度上较少对树结构带来的变化

下面给出的是计算某个节点下面最大以及最小的值,前驱,后继。以及基于此的删除算法:

最小值

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 版权协议,转载请附上原文出处链接和本声明。