C++ 二叉搜索树

namespace hbr
{
    template<class K>
    struct BSTreeNode
    {
    	BSTreeNode<K>* _left;
	    BSTreeNode<K>* _right;
    	K _key;
    	BSTreeNode(const K& key)
    		:_left(nullptr)
    		, _right(nullptr)
    		, _key(key)
    	{}
    };
  
    template<class K>
    class BSTree
    {
    typedef BSTreeNode<K> Node;
    public:
        bool Insert(const K& key){}
        bool Find(const K& key){}
        bool Erase(const K& key){}
        void _InOrder(Node* root){}

    private:
		Node* _root = nullptr;
	};
}

首先，定义了一个?BSTreeNode?结构体，表示二叉搜索树的节点。每个节点包含一个键值?_key，以及指向左子节点?_left?和右子节点?_right?的指针。

接下来，定义了一个?BSTree?类，表示二叉搜索树。该类包含一个私有成员?_root，指向树的根节点。

BSTree?类提供以下公有成员函数：

Insert?函数用于向二叉搜索树中插入一个节点。它接受一个键值?key?作为参数，并根据二叉搜索树的性质找到合适的位置插入节点。
Find?函数用于在二叉搜索树中查找一个节点。它接受一个键值?key?作为参数，并根据二叉搜索树的性质进行查找，返回是否找到该节点。
Erase?函数用于从二叉搜索树中删除一个节点。它接受一个键值?key?作为参数，并根据二叉搜索树的性质找到要删除的节点，并进行删除操作。
Ino

1、二叉搜索树的插入

插入的具体过程如下：

树为空，则直接新增节点，赋值给root指针
树不空，按二叉搜索树性质查找插入位置，插入新节点

bool Insert(const K& key)
{
	if (_root == nullptr)
	{
		_root = new Node(key);
		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);
	if (parent->_key < key) {
		parent->_right = cur;
	}
	else {
		parent->_left = cur;
	}
	return true;
}

2、中序遍历

二叉搜索树之所以常常使用中序遍历，是因为中序遍历可以按照从小到大的顺序输出二叉搜索树中的节点值。

void InOrder()
{
	_InOrder(_root);
	cout << endl;
}
//缺省值必须是全局变量或常量或静态变量
//void _InOrder(Node* root = _root)
void _InOrder(Node* root)
{
	if (root == nullptr)
		return;
	_InOrder(root->_left);
	cout << root->_key << " ";
	_InOrder(root->_right);
}

具体的中序遍历过程如下：

首先判断当前节点是否为空，如果为空则返回。
递归调用_InOrder函数遍历当前节点的左子树。
输出当前节点的值。
递归调用_InOrder函数遍历当前节点的右子树。

在代码中，_InOrder函数的调用是在InOrder函数中完成的，它将根节点作为参数传入。InOrder函数用于启动中序遍历，并在遍历完成后输出换行符。

3、二叉搜索树的查找

从根开始比较，查找，比根大则往右边走查找，比根小则往左边走查找。
最多查找高度次，走到到空，还没找到，这个值不存在。

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

4、二叉搜索树的删除

首先查找元素是否在二叉搜索树中，如果不存在，则返回, 否则要删除的结点可能分下面四种情

况：

要删除的结点无孩子结点
要删除的结点只有左孩子结点
要删除的结点只有右孩子结点
要删除的结点有左、右孩子结点

看起来有待删除节点有4中情况，实际情况a可以与情况b或者c合并起来，因此真正的删除过程

? 如下：

情况2：删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点--直接删除
情况3：删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点--直接删除
情况4：在它的右子树中寻找中序下的第一个结点(关键码最小)，用它的值填补到被删除节点

中，再来处理该结点的删除问题--替换法删除 ?

bool Erase(const K& key)
{
	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 {// 1、左为空
			if (cur->_left == nullptr) {
				if (cur == _root) {
					_root = cur->_right;
				}
				else {
					if (parent->_left == cur) {
						parent->_left = cur->_right;
					}
					else {
						parent->_right = cur->_right;
					}
				}
				delete cur;
			}// 2、右为空
			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;
					}
				}
				delete cur;
			}
			else {
				// 找右树最小节点替代，也可以是左树最大节点替代
				Node* pminRight = cur;
				Node* minRight = cur->_right;
				while (minRight->_left) {
					pminRight = minRight;
					minRight = minRight->_left;
				}
				cur->_key = minRight->_key;
				if (pminRight->_left == minRight) {
					pminRight->_left = minRight->_right;
				}
				else {
					pminRight->_right = minRight->_right;
				}
				delete minRight;
			}
			return true;
		}
	}
	return false;
}

5、构造

/*BSTree()
	:_root(nullptr)
	{}*/

BSTree() = default; // 制定强制生成默认构造

BSTree() = default;?是C++11引入的新特性，它告诉编译器生成一个默认的构造函数。这是一种特殊的成员函数声明，它要求编译器提供一个默认的实现。

在这个例子中，BSTree() = default;?告诉编译器生成一个默认的构造函数，这个构造函数不做任何事情，只是创建一个BSTree对象。因为在这个类中，所有的成员变量都有默认的初始化值（例如，_root被初始化为nullptr），所以默认的构造函数就足够了。

如果你没有提供任何构造函数，编译器也会为你生成一个默认的构造函数。但是，如果你提供了其他的构造函数（例如，一个接受参数的构造函数），编译器就不会再生成默认的构造函数，除非你明确地要求它这样做，就像在这个例子中那样。

6、拷贝构造

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

protected:
	Node* Copy(Node* root)
	{
		if (root == nullptr)
			return nullptr;
		Node* newRoot = new Node(root->_key);
		newRoot->_left = Copy(root->_left);
		newRoot->_right = Copy(root->_right);
		return newRoot;
	}

BSTree(const BSTree<K>& t)，它接受一个现有的BST对象t作为参数，并创建一个新的BST对象，该对象是t的副本。在这个拷贝构造函数中，新对象的根节点_root是通过调用Copy(t._root)函数得到的，Copy函数会递归地复制t的所有节点。

7、析构

public:
    ~BSTree()
    {
    	Destroy(_root);
    	//_root = nullptr;
    }
protected:
	void Destroy(Node*& root)
	{
		if (root == nullptr)
			return;
		Destroy(root->_left);
		Destroy(root->_right);
		delete root;
		root = nullptr;
	}

BSTree()，它用于销毁BST对象。在这个析构函数中，所有的节点都被销毁，这是通过调用Destroy(_root)函数完成的，Destroy函数会递归地销毁所有的节点。

8、赋值

BSTree<K>& operator=(BSTree<K> t)
{
	swap(_root, t._root);
	return *this;
}

BSTree<K>& operator=(BSTree<K> t)函数接受一个参数t，这个参数是按值传递的，所以在函数开始时，会调用拷贝构造函数创建一个新的BSTree对象，这个新对象是t的副本。

然后，函数使用swap函数交换当前对象（*this）的根节点_root和新对象t的根节点。这样，当前对象就获得了t的内容，而t获得了当前对象原来的内容。

最后，函数返回当前对象的引用，这样就可以支持连续赋值，例如a = b = c。

当函数结束时，新对象t会被销毁，由于t现在拥有当前对象原来的内容，所以这实际上会释放当前对象原来的内存

三、递归实现二叉搜索树

1、查找

public:
	bool FindR(const K& key)
	{
		return _FindR(_root, key);
	}
protected:
	bool _InsertR(Node*& root, const K& key)
	{
		if (root == nullptr){
			root = new Node(key);
			return true;
		}
		if (root->_key < key){
			return _InsertR(root->_right, key);
		}
		else if (root->_key > key){
			return _InsertR(root->_left, key);
		}
		else{
			return false;
		}
	}

在类外部通过调用InsertR函数调用_InsertR实现递归删除。

首先判断当前子树的根节点是否为空，如果为空，则创建一个新的节点，并将其作为根节点，然后返回true。
如果当前子树的根节点不为空，则比较要插入的键值与根节点的键值的大小关系：
- 如果要插入的键值大于根节点的键值，则递归调用_InsertR函数，将要插入的键值插入到右子树中。
- 如果要插入的键值小于根节点的键值，则递归调用_InsertR函数，将要插入的键值插入到左子树中。
- 如果要插入的键值等于根节点的键值，则表示已经存在相同的键值，返回false表示插入失败。
插入完成后，返回插入成功的标志。

该函数的作用是将新的节点按照二叉搜索树的规则插入到正确的位置上，保持二叉搜索树的有序性。

2、插入

public:
	bool InsertR(const K& key)
	{
		return _InsertR(_root, key);
	}
protected:
	bool _FindR(Node* root, const K& key)
	{
		if (root == nullptr)
			return false;
		if (root->_key == key)
			return true;
		if (root->_key < key)
			return _FindR(root->_right, key);
		else
			return _FindR(root->_left, key);
	}

在类外部通过调用Find函数调用_FindR实现递归删除。

首先判断当前子树的根节点是否为空，如果为空，则表示已经遍历到叶子节点仍未找到匹配的键值，返回false表示查找失败。
如果当前子树的根节点不为空，则比较要查找的键值与根节点的键值的大小关系：
- 如果要查找的键值等于根节点的键值，则表示找到了匹配的键值，返回true表示查找成功。
- 如果要查找的键值大于根节点的键值，则递归调用_FindR函数，在右子树中继续查找。
- 如果要查找的键值小于根节点的键值，则递归调用_FindR函数，在左子树中继续查找。
根据递归调用的结果，返回查找成功或失败的标志。

3、删除

public:
	bool EraseR(const K& key)
	{
		return _EraseR(_root, key);
	}
protected:
	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->_right == nullptr) {
				root = root->_left;
			}
			else if (root->_left == nullptr) {
				root = root->_right;
			}
			else {
				Node* maxleft = root->_left;
				while (maxleft->_right) {
					maxleft = maxleft->_right;
				}
				swap(root->_key, maxleft->_key);
				return _EraseR(root->_left, key);
			}
			delete del;
			return true;
		}
	}

在类外部通过调用EraseR函数调用_EraseR实现递归删除。

首先判断当前子树的根节点是否为空，如果为空，则表示已经遍历到叶子节点仍未找到匹配的键值，返回false表示删除失败。
如果当前子树的根节点不为空，则比较要删除的键值与根节点的键值的大小关系：
- 如果要删除的键值大于根节点的键值，则递归调用_EraseR函数，在右子树中继续删除。
- 如果要删除的键值小于根节点的键值，则递归调用_EraseR函数，在左子树中继续删除。
- 如果要删除的键值等于根节点的键值，则表示找到了要删除的节点。
对于要删除的节点，有以下几种情况：
- 如果要删除的节点没有左子树，则直接将右子树作为当前子树的根节点。
- 如果要删除的节点没有右子树，则直接将左子树作为当前子树的根节点。
- 如果要删除的节点既有左子树又有右子树，则找到左子树中的最大节点（即左子树中的最右节点），将其键值与要删除的节点的键值进行交换，然后递归调用_EraseR函数，在左子树中删除交换后的键值。
删除完成后，释放要删除的节点的内存空间，并返回true表示删除成功。

四、性能分析

二叉搜索树是一种特殊的二叉树，它的性能主要取决于树的高度。理想情况下，如果树是完全平衡的，那么它的高度就是log(n)，其中n是树中节点的数量。在这种情况下，BST的主要操作（插入、删除、查找）的时间复杂度都是O(log n)。

然而，在最坏的情况下，如果树完全不平衡（例如，每个节点都只有一个子节点，形成了一条线），那么树的高度就是n，此时BST的主要操作的时间复杂度都是O(n)。

因此，为了保持BST的高效性，需要尽可能保持树的平衡。有一些特殊的BST，如AVL树和红黑树，它们在插入和删除节点时会自动调整树的结构，以保持树的平衡，从而保证操作的时间复杂度始终是O(log n)。

空间复杂度方面，BST需要为每个节点存储一些额外的信息（如指向子节点的指针），所以它的空间复杂度是O(n)。

五、应用

1. K模型：K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到

的值。

比如：给一个单词word，判断该单词是否拼写正确，具体方式如下：

以词库中所有单词集合中的每个单词作为key，构建一棵二叉搜索树
在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。

2. KV模型：每一个关键码key，都有与之对应的值Value，即<Key, Value>的键值对。该种方

式在现实生活中非常常见：

比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英文单词与其对应的中文<word, chinese>就构成一种键值对；
再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出现次数就是<word, count>就构成一种键值对。

key-value

namespace key_value
{
	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:

		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->_right = cur;
			}
			else
			{
				parent->_left = cur;
			}

			return true;
		}

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

			return nullptr;
		}

		bool Erase(const K& key)
		{
			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
				{
					// 删除
					// 1、左为空
					if (cur->_left == nullptr)
					{
						if (cur == _root)
						{
							_root = cur->_right;
						}
						else
						{
							if (parent->_left == cur)
							{
								parent->_left = cur->_right;
							}
							else
							{
								parent->_right = cur->_right;
							}
						}

						delete cur;

					} // 2、右为空
					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;
							}
						}

						delete cur;
					}
					else
					{
						// 找右树最小节点替代，也可以是左树最大节点替代
						Node* pminRight = cur;
						Node* minRight = cur->_right;
						while (minRight->_left)
						{
							pminRight = minRight;
							minRight = minRight->_left;
						}

						cur->_key = minRight->_key;

						if (pminRight->_left == minRight)
						{
							pminRight->_left = minRight->_right;
						}
						else
						{
							pminRight->_right = minRight->_right;
						}

						delete minRight;
					}

					return true;
				}
			}

			return false;
		}


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

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

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

测试

void TestBSTree4()
{
    key_value::BSTree<string, string> dict;
    dict.Insert("apple", "苹果");
    dict.Insert("banana", "香蕉");
    dict.Insert("carrot", "胡萝卜");
    dict.Insert("dog", "狗");
    dict.Insert("elephant", "大象");
    dict.Insert("flower", "花");

    string str;
    while (cin >> str)
    {
        auto ret = dict.Find(str);
        if (ret)
        {
            cout << ":" << ret->_value << endl;
        }
        else
        {
            cout << "无此单词" << endl;
        }
    }
}
int main()
{
	TestBSTree4();

	return 0;
}

void TestBSTree5()
{
	string arr[] = { "橙子", "葡萄", "橙子", "香蕉", "橙子", "葡萄", "橙子", "香蕉", "苹果", "葡萄", "苹果", "草莓" };

	key_value::BSTree<string, int> countTree;
	for (auto str : arr)
	{
		//key_value::BSTreeNode<string, int>* ret = countTree.Find(str);
		auto ret = countTree.Find(str);
		if (ret == nullptr)
		{
			countTree.Insert(str, 1);
		}
		else
		{
			ret->_value++;
		}
	}

	countTree.InOrder();
}
int main()
{
	TestBSTree5();

	return 0;
}

完整版

#pragma once

namespace test
{
	template<class K>
	struct BSTreeNode
	{
		BSTreeNode<K>* _left;
		BSTreeNode<K>* _right;
		K _key;
		BSTreeNode(const K& key)
			:_left(nullptr)
			, _right(nullptr)
			, _key(key)
		{}
	};
	template<class K>
	class BSTree
	{
		typedef BSTreeNode<K> Node;
	public:
		/*BSTree()
			:_root(nullptr)
			{}*/

		BSTree() = default; // 制定强制生成默认构造
		
		BSTree(const BSTree<K>& t)
		{
			_root = Copy(t._root);
		}

		BSTree<K>& operator=(BSTree<K> t)
		{
			swap(_root, t._root);
			return *this;
		}

		~BSTree()
		{
			Destroy(_root);
		}

		bool Insert(const K& key)
		{
			if (_root == nullptr)
			{
				_root = new Node(key);
				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);
			if (parent->_key < key) {
				parent->_right = cur;
			}
			else {
				parent->_left = cur;
			}
			return true;
		}

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

		bool Erase(const K& key)
		{
			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 {// 1、左为空
					if (cur->_left == nullptr) {
						if (cur == _root) {
							_root = cur->_right;
						}
						else {
							if (parent->_left == cur) {
								parent->_left = cur->_right;
							}
							else {
								parent->_right = cur->_right;
							}
						}
						delete cur;
					}// 2、右为空
					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;
							}
						}
						delete cur;
					}
					else {
						// 找右树最小节点替代，也可以是左树最大节点替代
						Node* pminRight = cur;
						Node* minRight = cur->_right;
						while (minRight->_left) {
							pminRight = minRight;
							minRight = minRight->_left;
						}
						cur->_key = minRight->_key;
						if (pminRight->_left == minRight) {
							pminRight->_left = minRight->_right;
						}
						else {
							pminRight->_right = minRight->_right;
						}
						delete minRight;
					}
					return true;
				}
			}
			return false;
		}

		//缺省值必须是全局变量或常量或静态变量
		//void _InOrder(Node* root = _root)
		void _InOrder(Node* root)
		{
			if (root == nullptr)
				return;
			_InOrder(root->_left);
			cout << root->_key << " ";
			_InOrder(root->_right);
		}

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

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

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

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

	protected:
		Node* Copy(Node* root)
		{
			if (root == nullptr)
				return nullptr;
			Node* newRoot = new Node(root->_key);
			newRoot->_left = Copy(root->_left);
			newRoot->_right = Copy(root->_right);
			return newRoot;
		}

		void Destroy(Node*& root)
		{
			if (root == nullptr)
				return;
			Destroy(root->_left);
			Destroy(root->_right);
			delete root;
			root = nullptr;
		}

	private:
		Node* _root = nullptr;
	};
}

测试函数

#include <iostream>
#include "BSTree.h" // 假设BSTree类在名为BSTree.h的头文件中定义

using namespace std;
using namespace test;

int main() {
    BSTree<int> tree;

    // 测试插入
    cout << "向树中插入元素 5, 2, 8, 1, 3, 7, 9。" << endl;
    tree.Insert(5);
    tree.Insert(2);
    tree.Insert(8);
    tree.Insert(1);
    tree.Insert(3);
    tree.Insert(7);
    tree.Insert(9);

    // 测试中序遍历
    cout << "树的中序遍历结果: ";
    tree.InOrder();

    // 测试查找
    cout << "查找元素 3: " << (tree.Find(3) ? "找到" : "未找到") << endl;
    cout << "查找元素 10: " << (tree.Find(10) ? "找到" : "未找到") << endl;

    // 测试删除
    cout << "从树中删除元素 2。" << endl;
    tree.Erase(2);

    // 删除后的中序遍历
    cout << "删除元素 2 后的中序遍历结果: ";
    tree.InOrder();

    // 测试复制构造函数
    BSTree<int> treeCopy(tree);
    cout << "复制树的中序遍历结果: ";
    treeCopy.InOrder();

    // 测试赋值运算符
    BSTree<int> treeAssign;
    treeAssign = tree;
    cout << "赋值树的中序遍历结果: ";
    treeAssign.InOrder();

    return 0;
}

文章来源:https://blog.csdn.net/m0_73800602/article/details/135538388
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：chenni525@qq.com进行投诉反馈，一经查实，立即删除！