【C++】二叉搜索树的模拟实现

🌇个人主页：平凡的小苏
📚学习格言：命运给你一个低的起点，是想看你精彩的翻盘，而不是让你自甘堕落，脚下的路虽然难走，但我还能走，比起向阳而生，我更想尝试逆风翻盘。
🛸C++专栏：C++内功修炼基地
> 家人们更新不易，你们的👍点赞👍和⭐关注⭐真的对我真重要，各位路 过的友友麻烦多多点赞关注。 欢迎你们的私信提问，感谢你们的转发！ 关注我，关注我，关注我，你们将会看到更多的优质内容！！

一、二叉搜索树的概念

二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:

1.若他的左子树不为空，则左子树上所有节点的值小于根节点的值

2.若他的右子树不为空，则右子树上所有节点的值大于根节点的值

3.它的左右子树也分别为二叉搜索树

二叉搜索树的结构如下

template <class K,class V>
struct BSTreeNode//生成二叉搜索树的节点
{
	BSTreeNode<K,V>* _left;
	BSTreeNode<K,V>* _right;
	K _key;
	V _value;
	BSTreeNode(const K& key, const V& value)
		:_left(nullptr)
		,_right(nullptr)
		,_key(key)
		,_value(value)
	{}
};

template<class K,class V>
class BSTree//表示整颗二叉搜索树
{
	typedef BSTreeNode<K,V> Node;
public:
	BSTree()
		:_root(nullptr)
	{}
private:
	Node* _root;
};

二、二叉搜索树的查找

a、从根开始比较，查找，比根大则往右边走查找，比根小则往左边走查找。

b、最多查找高度次，走到到空，还没找到，这个值不存在。

• 插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能.

• 对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二

  叉搜索树的深度的函数，即结点越深，则比较次数越多。

  但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树：如下图所示
  

  最优情况下，二叉搜索树为完全二叉树(或者接近完全二叉树)，其平均比较次数为：logN

  最差情况下，二叉搜索树退化为单支树(或者类似单支)，其平均比较次数为：O(N)

1、递归版本的二叉搜索树的查找

Node* _FindR(Node* root, const K& key)
{
    if (root == nullptr)
    {
        return nullptr;
    }

    if (root->_key < key)
    {
        return _FindR(root->_right, key);
    }
    else if (root->_key > key)
    {
        return _FindR(root->_left, key);
    }
    else
    {
        return root;
    }
}

2、非递归版本的二叉搜索树的查找

Node* Find(const K& key)
{
    Node* cur = _root;
    while (cur)
    {
        if (cur->_key > key)
        {
            cur = cur->_left;
        }
        else if (cur->_key < key)
        {
            cur = cur->_right;
        }
        else
        {
            return cur;
        }
    }
    return nullptr;
}

三、二叉搜索树的插入

二叉搜索树的插入需要考虑插入后，需要维持二叉搜索树的形态。

1、二叉搜索树的非递归写法

bool Insert(const K& key, const V& value)
{
    if (_root == nullptr)
    {
        _root = new Node(key,value);
        return true;
    }

    Node* parent = nullptr;
    Node* cur = _root;
    while (cur)
    {
        if (cur->_key < key)
        {
            parent = cur;
            cur = cur->_right;
        }
        else if (cur->_key > key)
        {
            parent = cur;
            cur = cur->_left;
        }
        else
        {
            return false;
        }
    }
    cur = new Node(key,value);
    if (parent->_key > key)
    {
        parent->_left = cur;
    }
    else
    {
        parent->_right = cur;
    }
    return true;
}

注意：这里要记录一个父亲节点，来确保是插入在左侧还是插入在右侧

2、二叉搜索树的递归写法

bool _InsertR(Node*& root, const K& key,const V& value)
{
    if (root == nullptr)
    {
        root = new Node(key,value);
        return true;
    }

    if (root->_key < key)
    {
        return _InsertR(root->_right, key,value);
    }
    else if (root->_key > key)
    {
        return _InsertR(root->_left, key,value);
    }
    else
    {
        return false;
    }
}

递归写法巧就巧在形参是指针的引用，例如我现在要插入9，下层的root是上一层root->_left的别名， 下层root = new Node(key);即为上一层root->_left=new Node(key);这样插入节点就自动和父节点连接上了。

四、二叉搜索树的删除

二叉搜索树的节点进行删除后，同样需要维持二叉搜索树的形态。

二叉搜索树的删除无非是三种情况：

1、二叉搜索树非递归版本的删除

bool Erase(const K& key)
{
    Node* cur = _root;
    Node* parent = nullptr;
    while (cur)
    {
        if (cur->_key > key)
        {
            parent = cur;
            cur = cur->_left;
        }
        else if (cur->_key < key)
        {
            parent = cur;
            cur = cur->_right;
        }
        else
        {
            if (cur->_left == nullptr)
            {
                if (cur == _root)
                {
                    _root = cur->_right;
                }
                else
                {
                    if (parent->_right == cur)
                    {
                        parent->_right = cur->_right;
                    }
                    else
                    {
                        parent->_left = cur->_right;
                    }
                }
            }

            else if (cur->_right == nullptr)
            {
                if (cur == _root)
                {
                    _root = cur->_left;
                }
                else
                {
                    if (parent->_left == cur)
                    {
                        parent->_left = cur->_left;
                    }
                    else
                    {
                        parent->_right = cur->_left;
                    }
                }
            }

            else
            {
                Node* parent = cur;
                Node* leftMax = cur->_left;
                while (leftMax->_right)//找到左树的最大节点，即在左树的最右边
                {
                    parent = leftMax;
                    leftMax = leftMax->_right;
                }
                swap(cur->_key, leftMax->_key);//交换数据
				//如上图，如果删除的是3，那么就会和1交换，即是如下这种情况，需要将3的左连接到1的左
                if (parent->_left == leftMax)
                {
                    parent->_left = leftMax->_left;
                }
                //如上图如果删除的是8，则会和6交换，则是如下这种情况，需要将10的有连接到6的左
                else
                {
                    parent->_right = leftMax->_left;
                }
                cur = leftMax;
            }
            delete cur;
            return true;
        }
    }
    return false;
}

1、先通过二叉搜索树的性质找到要删除的节点；

2、找到需要删除的节点后，分三种情况进行讨论：

​ 一、被删除节点的左孩子为空，除了cur等于根节点情况下，其他情况下，父节点的孩子指针由指向被删除节点转为指向被删除节点的右孩子。（如图删除14）

二、被删除节点的左孩子存在但右孩子为空，除了cur等于根节点情况下，其他情况下，父节点的孩子指针由指向被删除节点转为指向被删除节点的左孩子。（如图删除9）

三、被删除的节点均不为空，可以选用左树最大节点或者右树最小节点对被删除节点进行值替换，问题转化为第一种或第二种情况。（详见代码注释）

2、二叉搜索树递归版本的删除

bool _EraseR(Node*& root, const K& key)
{
    if (root == nullptr)
    {
        return false;
    }

    if (root->_key < key)
    {
        return _EraseR(root->_right, key);
    }
    else if (root->_key > key)
    {
        return _EraseR(root->_left, key);
    }
    else
    {
        Node* del = root;
        if (root->_left == nullptr)
        {
            root = root->_right;//因为是引用直接修改它的指向就可以
        }
        else if (root->_right == nullptr)
        {
            root = root->_left;
        }
        else
        {
            Node* leftmax = root->_left;
            while (leftmax->_right)//找到左树的最大节点
            {
                leftmax = leftmax->_right;
            }

            swap(root->_key, leftmax->_key);//交换
            swap(root->_value, leftmax->_value);


            return _EraseR(root->_left, key);//再次进行递归删除，这样就转换成了情况1或者情况2 的删除
        }
        delete del;
        return true;
    }

    return false;
}

注意：由于引用的语法，循环版本不能使用引用，因为递归使其每个栈帧不一样了，所以可以使用引用

五、二叉搜索树的源码

1、key/value的搜索模型（节点既存key又存value)

key/value搜索模型指每一个key值，都有与之对应的value值，例如英汉互译，一个英文单词可以对应一个翻译字符串。该模型还可以用于统计相同内容出现次数。文章来源地址https://www.toymoban.com/news/detail-636651.html

2、key/value模型的源码

#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include <iostream>
#include <algorithm>
using namespace std;

template <class K,class V>
struct BSTreeNode//生成二叉搜索树的节点
{
	BSTreeNode<K,V>* _left;
	BSTreeNode<K,V>* _right;
	K _key;
	V _value;
	BSTreeNode(const K& key, const V& value)
		:_left(nullptr)
		,_right(nullptr)
		,_key(key)
		,_value(value)
	{}
};

template<class K,class V>
class BSTree//表示整颗二叉搜索树
{
	typedef BSTreeNode<K,V> Node;
public:
	BSTree()
		:_root(nullptr)
	{}

	BSTree(const BSTree<K,V>& t)
	{
		_root = Copy(t._root);
	}

	BSTree<K, V>& operator=(BSTree<K, V> t)
	{
		swap(_root, t._root);
		return *this;
	}
	bool Insert(const K& key, const V& value)
	{
		if (_root == nullptr)
		{
			_root = new Node(key,value);
			return true;
		}

		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_key < key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_key > key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}
		cur = new Node(key,value);
		if (parent->_key > key)
		{
			parent->_left = cur;
		}
		else
		{
			parent->_right = cur;
		}
		return true;
	}

	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}

	Node* Find(const K& key)
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur->_key > key)
			{
				cur = cur->_left;
			}
			else if (cur->_key < key)
			{
				cur = cur->_right;
			}
			else
			{
				return cur;
			}
		}
		return nullptr;
	}
	bool Erase(const K& key)
	{
		Node* cur = _root;
		Node* parent = nullptr;
		while (cur)
		{
			if (cur->_key > key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (cur->_key < key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				if (cur->_left == nullptr)
				{
					if (cur == _root)
					{
						_root = cur->_right;
					}
					else
					{
						if (parent->_right == cur)
						{
							parent->_right = cur->_right;
						}
						else
						{
							parent->_left = cur->_right;
						}
					}
				}

				else if (cur->_right == nullptr)
				{
					if (cur == _root)
					{
						_root = cur->_left;
					}
					else
					{
						if (parent->_left == cur)
						{
							parent->_left = cur->_left;
						}
						else
						{
							parent->_right = cur->_left;
						}
					}
				}

				else
				{
					Node* parent = cur;
					Node* leftMax = cur->_left;
					while (leftMax->_right)
					{
						parent = leftMax;
						leftMax = leftMax->_right;
					}
					swap(cur->_key, leftMax->_key);

					if (parent->_left == leftMax)
					{
						parent->_left = leftMax->_left;
					}
					else
					{
						parent->_right = leftMax->_left;
					}
					cur = leftMax;
				}
				delete cur;
				return true;
			}
		}
		return false;
	}

	Node* FindR(const K& key)
	{
		return _FindR(_root, key);
	}

	bool InsertR(const K& key, const V& value)
	{
		return _InsertR(_root, key,value);
	}

	bool EraseR(const K& key)
	{
		return _EraseR(_root, key);
	}

	~BSTree()
	{
		Destroy(_root);
	}
private:
	void Destroy(Node*& root)
	{
		if (root == nullptr)
		{
			return;
		}

		Destroy(root->_left);
		Destroy(root->_right);
		delete root;
	}
	Node* Copy(Node* root)
	{
		if (root == nullptr)
		{
			return nullptr;
		}
		Node* copynewnode = new Node(root->_key,root->_value);
		copynewnode->_left = Copy(root->_left);
		copynewnode->_right = Copy(root->_right);
		return copynewnode;
	}

	bool _EraseR(Node*& root, const K& key)
	{
		if (root == nullptr)
		{
			return false;
		}

		if (root->_key < key)
		{
			return _EraseR(root->_right, key);
		}
		else if (root->_key > key)
		{
			return _EraseR(root->_left, key);
		}
		else
		{
			Node* del = root;
			if (root->_left == nullptr)
			{
				root = root->_right;
			}
			else if (root->_right == nullptr)
			{
				root = root->_left;
			}
			else
			{
				Node* leftmax = root->_left;
				while (leftmax->_right)
				{
					leftmax = leftmax->_right;
				}

				swap(root->_key, leftmax->_key);
				swap(root->_value, leftmax->_value);


				return _EraseR(root->_left, key);
			}
			delete del;
			return true;
		}

		return false;
	}

	bool _InsertR(Node*& root, const K& key,const V& value)
	{
		if (root == nullptr)
		{
			root = new Node(key,value);
			return true;
		}

		if (root->_key < key)
		{
			return _InsertR(root->_right, key,value);
		}
		else if (root->_key > key)
		{
			return _InsertR(root->_left, key,value);
		}
		else
		{
			return false;
		}
	}
	Node* _FindR(Node* root, const K& key)
	{
		if (root == nullptr)
		{
			return nullptr;
		}

		if (root->_key < key)
		{
			return _FindR(root->_right, key);
		}
		else if (root->_key > key)
		{
			return _FindR(root->_left, key);
		}
		else
		{
			return root;
		}
	}

	void _InOrder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}

		_InOrder(root->_left);
		cout << root->_key << ":" << root->_value << endl;
		_InOrder(root->_right);
	}
private:
	Node* _root;
};

void BSTreeTest()
{
	string arr[] = { "西瓜", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
	BSTree<string, int> countTree;
	for (auto& str : arr)
	{
		auto ret = countTree.FindR(str);
		if (ret == nullptr)
		{
			countTree.InsertR(str, 1);
		}
		else
		{
			ret->_value++;
		}
	}

	countTree.InOrder();
}

到了这里，关于【C++】二叉搜索树的模拟实现的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！