完全理解搜索/排序/查找二叉树的插入、查找、删除

typedef int Treetype;
typedef struct binaryTree
{
	Treetype  val;
	struct binaryTree* left, * right;
}BinaryTree;
void Push_BST(BinaryTree* bt, Treetype n)//输入元素,建树
{
    if (bt->val == MAXNUM)//树中还没有元素
	{
		bt->val = n;
		return;
	}
	if (n <= bt->val)//元素比该树节点小
	{
		if (bt->left)//如果节点左边非空，继续递归比较
			Push_BST(bt->left, n);
		else//节点左边空的话就插入此位置
		{
			BinaryTree* tmp = (BinaryTree*)new BinaryTree;
			tmp->left = tmp->right = NULL;
			tmp->val = n;
			bt->left = tmp;
			return;
		}
	}
	else//元素比该树节点大
	{
		if (bt->right)
			Push_BST(bt->right, n);
		else
		{
			BinaryTree* tmp = (BinaryTree*)new BinaryTree;
			tmp->left = tmp->right = NULL;
			tmp->val = n;
			bt->right = tmp;
			return;
		}
	}
}

二.查找

（一）.实现原理

查找的原理与插入的类似。

我们将要查找的元素与经过的每个节点做比较，如果元素与该节点的值相等，那就返回该节点就可；如果比该节点小就往节点的左子树走，如果比该节点大就往节点的右子树走。

直到找到与该元素相同的节点或走到空白位置即该树中没有与该元素相同的节点。

（二）.代码实现

bool Search_BST(BinaryTree* bt, Treetype n)//查找
{
	if (bt == NULL) return false;
	else if (bt->val == n) return true;
	return n < bt->val ? Search_BST(bt->left, n) : Search_BST(bt->right, n);
}

三.删除

（一）.实现原理

删除的原理相对较难一些。

我们需要进行分类讨论。

第一种情况：删除的节点没有左右子树。

这是最简单的情况，我们直接删除这个节点即可。

第二种情况：删除的节点只有左子树或者只有右子树。

这里我们以只有左子树为例，我们只需要把该删除节点的左子树接上即可。

第三种情况：删除的节点既有左子树，又有右子树。（最重要）

大家跟着我一起来想：搜索二叉树的性质是比该节点小的都在左边，大的都在右边。

那么我们只需要在该节点的左边找到最大的或者在节点右边找到最小的即可，因为这两个都是最接近要删除的节点值的。把这两个最接近值中的其中一个与删除节点值交换，然后将交换后删除值所在的节点删除即可。

那么我们怎么找到这个最接近的值呢：

①节点左边最大的（直接前驱）：找到删除节点的左子树的最右边子树即可。因为，删除节点的左子树是比该节点小的，而该左子树的右子树是大于该左子树又小于删除节点的，然后一直往右走，直到找到最右边的子树，这颗树是大于删除节点所有左节点又小于删除节点的，即最接近删除节点的。

①节点右边最小的（直接后继）：找到删除节点的右子树的最左边子树即可。道理同直接前驱。

当然，我们还是用图来说明一下吧，这里用直接前驱来解释：

watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5bCx6KaBIOWuheWcqOWutg==,size_20,color_FFFFFF,t_70,g_se,x_16

注意：这里有一个陷阱！

如果删除节点的左子树没有右节点，那么就无法与要删除的节点交换，这里我们只需要在一开始确定删除节点左右子树非空的情况下，再判断左节点是否有有子树即可，没有右子树的话直接把左节点接到删除节点即可。

（二）.代码实现

void Pop_BST(BinaryTree* bt, Treetype n)//删除元素
{
	if (bt == NULL)//没找到
	{
		cout << "Pop false! No find it.\n";
		return;
	}
	else if (bt->val == n)
	{
		_pop(bt);
	}
	else
	n < bt->val ? Pop_BST(bt->left, n) : Pop_BST(bt->right, n);
}
void _pop(BinaryTree* bt)//删除的子函数
{
	if (bt->left == NULL)//左空、全空
	{
		BinaryTree* tmp = bt;
		bt = bt->right;
		free(tmp);
	}
	else if (bt->right == NULL)//右空
	{
		BinaryTree* tmp = bt;
		bt = bt->left;
		free(tmp);
	}
	else//左右子树都不是空
	{
		//采用找直接前驱的方法
		BinaryTree* prev = bt->left, *rtmp = bt->left->right, *tmp = bt;
		if (rtmp == NULL)//bt的左子树没有右子树
		{
			bt->val = bt->left->val;
			bt->left = bt->left->left;
			free(prev);
			return;
		}
		while (rtmp->right)//找左子树的最右节点
		{
			prev = rtmp;
			rtmp = rtmp->right;
		}
		bt->val = rtmp->val;
		prev->right = rtmp->left;
		free(rtmp);
	}
}

创作不易，点赞支持博主一下吧

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)