二叉排序树_二叉树的遍历算法_平衡二叉树(2)

关于二叉排序树的有关操作，个人认为，最有技术含量的是节点的删除。这个问题需要考虑的情况较多点。

删除一个节点需要考虑对应节点的状态，具体的说就是，节点是否为空，若不空，它的左右子树是否存在。我们可以按以下步骤来进行：

一、查找待删除节点，在查找的同时需要记录一下待删除节点的父亲，因为删除节点的同时需要善后（将其父节点的lchild或者rchild置空）。

二、根据待删除节点的左右子树状态做相应处理，这些状态包括：

1.如果待删除节点的左右节点都不存在，那么直接删除，将其父节点相应的指针置空（如果存在父节点）。二叉排序树

2.如果待删除节点左子树存在右子树不存在，或者左子树不存在右子树存在。直接将其子树中存在的一边候补上来即可。

3.如果待删除节点左右子树都在，这个情况稍微复杂点。需要按照二叉排序树的性质从其左子树或者有子树中选择节点补到待删除节点的位置。

一般是用树的中序遍历中跟待删除节点相邻的节点（左右节点都行，这里就选右节点）来替带待删除的节点。实际上执行删除操作时，并不

是真的把待删除节点删掉，而是用替代节点的键赋给待删节点键，然后delete掉替代节点。

（a） (b)

上面从图（a）到（b）是一个典型待删节点左右子树都存在的删除过程：要删除15节点，先把21节点改为20节点的左子树，再把18节点见复给待删除的15节点，最后删除原18节点。

template<typename T>
void BinaryTree<T>::Remove(const T &data, Node<T>* &a, Node<T>* &b)
{
	         Node<T>*temp1, *temp2;
		if (b == NULL) { cerr << "Invalid input"; return; }
		if (data < b->info) Remove(data, b, b->lchild);    //先找到节点位置，这里没有考虑找不到的情况
		else if (data >b->info) Remove(data, b, b->rchild);

               else if (b->lchild != NULL&&b->rchild != NULL)     //这个分支以及下面的分支表示已找到data所在节点
		{
			temp2 = b;
			temp1 = b->rchild;
			if (temp1->lchild != NULL)
			{
				while (temp1->lchild != NULL)
				{
					temp2 = temp1;
					temp1 = temp1->lchild;
				}
				temp2->lchild = temp1->rchild;
			}
			else temp2->rchild = temp1->rchild;
			b->info = temp1->info;
			delete temp1;
		}
	        else                                                //左右子树中至少有一个不存在的情况
		{
			temp1 = b;
			if (b->rchild != NULL)
			{
				temp1 = b->rchild;
				b->info = temp1->info;
				b->rchild = temp1->rchild;
				b->lchild = temp1->lchild;
			}
			else if (b->lchild != NULL)
			{
				temp1 = b->lchild;
				b->info = temp1->info;
				b->rchild = temp1->rchild;
				b->lchild = temp1->lchild;
			}
			else if (b == root) root = NULL;
			else if (a->rchild == temp1) a->rchild = NULL;
			else a->lchild = NULL;
			delete temp1;
		}
	
}

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