数据结构 二叉搜索树的删除

时间:2024-04-02 22:30:28

概述

这是一篇短文,专门考究一下二叉搜索树的删除。

二叉搜索树的建立非常简单,如果不熟悉的见此文 树与二叉树

而删除则有数种情况:

  1. 待删除的结点没有子树。
  2. 待删除的结点仅有一颗子树。
  3. 待删除的结点有两颗子树。

下面逐一分析。

待删除的结点没有子树

如需删除下图中结点9:

数据结构 二叉搜索树的删除

这是最简单的一种情况,它没有子树,意味着没有太多需要特殊处理的地方,只需要简单的将其从其父亲处删除即可。即移除结点8的右子树,移除后如下图:

数据结构 二叉搜索树的删除

待删除的结点仅有一颗子树

如需删除下图中结点8:

数据结构 二叉搜索树的删除

仅有一颗子树的情况其实也非常简单,只需要将其唯一的子树接到其原父亲结点处,即原本指向被删除结点的指针改为指向被删除结点的子树。移除后如下图:

数据结构 二叉搜索树的删除

待删除的结点有两颗子树

如需删除下图中结点3:

数据结构 二叉搜索树的删除

这种情况就有些特殊了,如果要保证删除后二叉搜索树的相对位置不变(即中序遍历顺序不变),那有两种方法:

  1. 使待删除结点的左子树代替被删除的结点,将被删除结点的右子树放置于被删除结点的左子树的最右边。
  2. 用待删除结点的直接前驱或直接后继(指的是遍历顺序的)代替被删除的结点,然后再删除用以替代的原节点。

下面主要说明第一种方法,删除后即如下:

数据结构 二叉搜索树的删除

可以看到,删除前中序遍历结果为:1345689,而删除后中序遍历结果为:145689,即元素间的顺序没有被改变。

如果删除的是根结点,情况也是一样的:

数据结构 二叉搜索树的删除

数据结构 二叉搜索树的删除

它的中序遍历1345689->134689也没有发生变化。

C代码实现

int BT_delete(BTree * t, int dat)
{
	if (t == NULL || t->cnt == 0)
		return 0;
	BTreeNode **pointToCur = &t->root; //因为结点删除实际上是让原本指向该结点的指针指向别的结点,为了方便修改使用一个指向树结点指针的指针。
	BTreeNode *pcur = t->root;
	BTreeNode *pdelete;

	while (pcur != NULL && pcur->data != dat) //查找树是否存在待删除元素
	{
		if (dat <= pcur->data)
		{
			pointToCur = &pcur->left;
			pcur = pcur->left;
		}
		else
		{
			pointToCur = &pcur->right;
			pcur = pcur->right;
		}
	}
	if (pcur == NULL) //未找到元素
		return 0;

	pdelete = pcur;
	if (pcur->left == NULL && pcur->right == NULL)
		*pointToCur = NULL;
	else if (pcur->left == NULL)
		*pointToCur = pcur->right;
	else if (pcur->right == NULL)
		*pointToCur = pcur->left;
	else
	{
		*pointToCur = pcur->left; //用被删除结点的左子树替换被删除的结点

		pcur = pdelete->left; //转至被删除结点左子树
		while (pcur->right != NULL) pcur = pcur->right; //递进至最右

		pcur->right = pdelete->right; //将被删除结点的右子树结于被删除结点的左子树最右边。
	}
	free(pdelete);
	t->cnt--;
	return 1;
}