什么是二叉搜索树，以及如何实现二叉搜索树的增删查代码

目录

1.什么是二叉搜索树

​编辑2.二叉搜索树的节点构成

3.二叉搜索树的 增加，查找，删除

1.查找

2.增加

3.删除

1.孩子数为0的情况

2.孩子数为1的情况

3.孩子数为2的情况

1.什么是二叉搜索树

2.二叉搜索树的节点构成

搜索二叉树是在二叉树的基础上构成的所以二叉树的节点是

class BSTNode
{
    private:
        int _data;
        BSTNode *left;
        BSTNode *right;
};

我们可以在此基础上进行优化。我们可以思考二叉树中的_data一定是为int类型的吗？不一定可能是char可能是其他，所以为了兼容性使得代码的更加全面。我们可以使用模版。

​temlate <typname T>
class BSTNode
{
    private:
        T _data;
        BSTNode<T> *left;
        BSTNode<T> *right;
};

​

为了方便维护我们借鉴list的思维，再创造一个类BSTree来存放BSTNode节点。将节点和树分开来。

template <typename T>
class BSTree
{
    private:
	    typedef BSTNode<T> Node;
	    typedef Node* PNode;
	    PNode _root;//非内置类型，要写构造函数
}；

3.二叉搜索树的 增加，查找，删除

1.查找

查找的目的是为了增加和删除。如果二叉搜索树中有这个要增加的值就不会再往树中增加了，同理如果二叉搜索树中没有这个要删除的树就不需要删除了。

查找的逻辑很简单，因为二叉搜索树的结构决定了它简单的逻辑。“左小右大”。所以我们只需要去拿要找的值key一个一个去比较，如果key比节点的值大就往右找，如果比节点的值小就往左找。

bool Find(const T& data)
{
	PNode cur = _root;
	while (cur)
	{
		if (data > cur->_data)
			cur = cur->right;
		else if (data < cur->_data)
			cur = cur->left;
		else
			return true;
	}
	return false;
}

2.增加

写了查找函数后方便缕清我们写增加函数的逻辑了。

我们如何增加一个数据到二叉树中呢？首先我们得知道这个数有没有存在于二叉搜索树中吧，如果树中没有这个数据那么我们进行插入操作，接着同样的还需要去遍历一遍树找到要插入的数据的位置，同与节点的值去比较的方式，如果大于节点的值就往右遍历，如果小于节点的值就往左遍历，直到没有值进行比较，此时就代表找到这个值插入的位置了。这里需要注意要插入节点，那就还需要找到插入位置的父节点，通过父节点的指向将新节点插入树中。大致思路是这样的，但还有一些小细节需要我们分类讨论。

1.树为空

2.树不为空，插入节点是父节点的左边还是右边。

代码如下

​
bool Insert(const T& a)
{	
	if (Find(a))  //如果树中已经有a值了就不需要插入，直接返回false代表插入失败。
		return false;

	if (_root == nullptr) //如果树为空，那么直接创个节点将节点地址赋给_root。
	{
		_root = new Node(a);
		return true;   //直接返回true代表插入成功。
	}

    
	PNode newnode = new Node(a);
	PNode cur = _root;
	while (cur)
	{
		if(a > cur->_data)
		{
			if (cur->right == nullptr)
				break;
			cur = cur->right;
		}
		else if(a < cur->_data)
		{
			if (cur->left == nullptr)
				break;
			cur = cur->left;
		}
	}
    //遍历结束找到插入位置。

    //判断插入的是父节点的左右
	if (a > cur->_data) //如果进入了这个if条件代表是父节点的右边。 
		cur->right = newnode;
	else                //同理这个就是父节点的左边。
		cur->left = newnode;
	return true;        //最后返回true代表插入成功了。
}
//函数中有两处return true的地方是因为这两种情况不会同时发生，是相互独立的情况，所以每一处都要写上return true。
​

3.删除

二叉树最麻烦的，最考验代码的逻辑能力的就是删除操作了。因为删除需要考虑多的情况。以下图为例。

看图我们可以发现三组，我们将要删除的节点分组分别是

孩子数为0的节点：0,3,6,11。

孩子数为1的节点：2,7,5。

孩子数为2的节点：1,4,10。

所以我们要分三种情况来讨论。

为了方便叙述我们将要删除节点称为cur,将cur的父节点称为pcur。

1.孩子数为0的情况

类比链表删除的思路，我们只需要找到pcur，将pcur的指向改为空就行。因此我们还需要找到pcur节点。找到pcur节点后我们就需要对其进行讨论pcur为不为空，如果为空意味着cur节点是_root节点，且我们将pcur指向改变时必定会访问pcur所指向的空间，那么此时就会出现空指针的访问问题。

2.孩子数为1的情况

 此情况和孩子数为0时的思路大差不差，唯一不同的就是在pcur不为空的情况下，要考虑如何将pcur指向cur的孩子，这是就要判断一：孩子是在cur的左边还是右边，且还要判断二：cur是在pcur的左边还是右边了。判断一和判断二是平行的关系所以谁前谁后并没有影响。

3.孩子数为2的情况

这种情况最麻烦，因为我们要考虑谁来替代cur节点。为了不破坏搜索二叉树的结果特性（左小右大），要来替代的值应该在排完序后cur的左边或者右边。这样才是最优的。我们选择升序的右边，也就是cur右子树的最左节点。我们将cur_right_left_min称为这个右子树的最左节点。

这时我们就要讨论cur_right_left_min存在的问题了。

如果存在和孩子数为1的情况一样在将cur的值替代成cur_right_left_min的值后我们需要将cur_right_left_min的右节点赋给cur_right_left_min的左边即可。

如果不存在也就是cur_right_left_min为空，此时cur的左边右边都可以来替代cur的值，为了代码更强的逻辑性，我们和之前一样选择cur的右子树。此时我们只需将右子树的值赋给cur然后将cur的右边指向空，最后将右子树delete就行了。

最后我们整理思路可以将孩子数为1和孩子数为0的情况放在一起。代码如下：

//用引用是因为，T可能是类，那么加上引用会减少拷贝构造函数的调用。
bool Erase(const T& key)
{
	Node* parent = nullptr;
	Node* cur = _root;
	while (cur)
	{
		if (cur->_data < key)
		{
			parent = cur;
			cur = cur->right;
		}
		else if (cur->_data > key)
		{
			parent = cur;
			cur = cur->left;
		}
		else
		{
			// 删除
			// 0-1个孩子的情况
			if (cur->left == nullptr)
			{
				//考虑parent节点为空节点
				if (parent == nullptr)
					_root = cur->right;
				else
				{
					if (parent->_data > key)//确定删除的是父节点的左边
						parent->left = cur->right;
					else
						parent->right = cur->right;
					
				}
				delete cur;
				cur = nullptr;
				return true;
			}
			else if (cur->right == nullptr)
			{
				if (parent == nullptr)
					_root = cur->left;
				else
				{
					if (parent->_data > key)//确定删除的是父节点的左边
						parent->left = cur->left;
					else
						parent->right = cur->left;
				}
				delete cur;
				cur = nullptr;
				return true;
			}
			else
			{
				// 2个孩子的情况
				// 右子树的最小节点作为替代节点
				PNode cur_left_min = cur->right;
				PNode pcur_left_min = cur;
				
				
					while (cur_left_min->left)
					{
						pcur_left_min = cur_left_min;
						cur_left_min = cur_left_min->left;
					}
					if (cur_left_min->left == nullptr)
						pcur_left_min->right = cur_left_min->right;
					else
					    pcur_left_min->left = cur_left_min->right;

					cur->_data = cur_left_min->_data;
					delete cur_left_min;
					cur_left_min = nullptr;
					return true;
			}
		}
	}
	return false;
}