博客

算法导论—

二叉树

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

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

最小值

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