1. Toy模板网首页
  2. > Toy博客

C++ 二叉搜索树

10月前 作者：Han同学 分类：Toy博客 阅读(62) 违法举报

这篇具有很好参考价值的文章主要介绍了C++ 二叉搜索树。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

目录

一、二叉搜索树概念

二、二叉搜索树的实现

1、二叉搜索树的插入

2、中序遍历

3、二叉搜索树的查找

4、二叉搜索树的删除

5、构造

6、拷贝构造

7、析构

8、赋值

三、递归实现二叉搜索树

1、插入

2、查找

3、删除

四、性能分析

五、应用

key-value

测试

完整版

测试函数

一、二叉搜索树概念

二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:
  • 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
  • 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
  • 它的左右子树也分别为二叉搜索树

C++ 二叉搜索树,C++,算法,c++,开发语言

由于这个性质，中序遍历二叉搜索树时，会先遍历左子树，然后输出根节点的值，最后遍历右子树。这样就可以按照从小到大的顺序输出二叉搜索树中的节点值。

中序遍历：1 3 4 6 7 8 10 13 14 

二、二叉搜索树的实现

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 类提供以下公有成员函数：

  1. Insert 函数用于向二叉搜索树中插入一个节点。它接受一个键值 key 作为参数，并根据二叉搜索树的性质找到合适的位置插入节点。

  2. Find 函数用于在二叉搜索树中查找一个节点。它接受一个键值 key 作为参数，并根据二叉搜索树的性质进行查找，返回是否找到该节点。

  3. Erase 函数用于从二叉搜索树中删除一个节点。它接受一个键值 key 作为参数，并根据二叉搜索树的性质找到要删除的节点，并进行删除操作。

  4. _InOrder 函数用于中序遍历，由于二叉搜索树的性质使用中序遍历可以按照升序输出每个节点。

1、二叉搜索树的插入

插入的具体过程如下：
  1. 树为空，则直接新增节点，赋值给root指针
  2. 树不空，按二叉搜索树性质查找插入位置，插入新节点 
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);
}

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

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

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

3、二叉搜索树的查找

  1. 从根开始比较，查找，比根大则往右边走查找，比根小则往左边走查找。
  2. 最多查找高度次，走到到空，还没找到，这个值不存在。
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、二叉搜索树的删除

首先查找元素是否在二叉搜索树中，如果不存在，则返回, 否则要删除的结点可能分下面四种情
况：
  1. 要删除的结点无孩子结点
  2. 要删除的结点只有左孩子结点
  3. 要删除的结点只有右孩子结点
  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 InsertR(const K& key)
	{
		return _InsertR(_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实现递归删除。

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

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

2、查找

public:
	bool FindR(const K& key)
	{
		return _FindR(_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实现递归删除。

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

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实现递归删除。

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

四、性能分析

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

C++ 二叉搜索树,C++,算法,c++,开发语言

然而，在最坏的情况下，如果树完全不平衡（例如，每个节点都只有一个子节点，形成了一条线），那么树的高度就是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;
}

C++ 二叉搜索树,C++,算法,c++,开发语言

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;
}

C++ 二叉搜索树,C++,算法,c++,开发语言

完整版

#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;
}

C++ 二叉搜索树,C++,算法,c++,开发语言文章来源地址https://www.toymoban.com/news/detail-814635.html

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

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • C++ 二叉搜索树

    C++ 二叉搜索树

    目录 一、二叉搜索树概念 二、二叉搜索树的实现 1、二叉搜索树的插入 2、中序遍历 3、二叉搜索树的查找 4、二叉搜索树的删除 5、构造 6、拷贝构造 7、析构 8、赋值 三、递归实现二叉搜索树 1、插入 2、查找 3、删除 四、性能分析 五、应用 key-value 测试 完整版 测试函数 二

    2024年01月22日
    浏览(62)
  • 二叉搜索树（C++）

    二叉搜索树（C++）

    在使用C语言写数据结构阶段时，对二叉树进行了讲解。本节内容是对二叉树的深入探索，也是二叉树部分的收尾 二叉搜索树也称二叉排序树（BST，Binary Search Tree）： 空树 非空树（要具有以下性质） 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值 若它的右

    2024年02月11日
    浏览(34)
  • 【C++入门到精通】C++入门 ——搜索二叉树（二叉树进阶）

    【C++入门到精通】C++入门 ——搜索二叉树（二叉树进阶）

    前面我们讲了C语言的基础知识，也了解了一些初阶数据结构，并且讲了有关C++的命名空间的一些知识点以及关于C++的缺省参数、函数重载，引用 和 内联函数也认识了什么是类和对象以及怎么去new一个 ‘对象’ ，也了解了C++中的模版，以及学习了几个STL的结构也相信大家都

    2024年02月07日
    浏览(30)
  • 【C++】二叉树进阶之二叉搜索树

    【C++】二叉树进阶之二叉搜索树

    作者简介：დ旧言~，目前大二，现在学习Java，c，c++，Python等 座右铭：松树千年终是朽，槿花一日自为荣。 目标：熟练掌握二叉搜索树，能自己模拟实现二叉搜索树 毒鸡汤：不断的努力，不断的去接近梦想，越挫越勇，吃尽酸甜苦辣，能够抵御寒冬，也能够拥抱春天，这样

    2024年03月16日
    浏览(83)
  • C++二叉搜索树剖析

    C++二叉搜索树剖析

    二叉搜索树，又称为二叉排序树，是一种特殊的二叉树。它要么是一棵空树，要么具有以下性质： 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值； 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值； 它的左右子树也分别为二叉搜索树。

    2024年02月14日
    浏览(40)
  • 二叉搜索树 --- C++实现

    二叉搜索树 --- C++实现

    目录 1.二叉搜索树的概念 2.二叉搜索树的操作 3. 二叉树的实现 4.二叉搜索树的应用 5. 二叉树的性能分析 6. 二叉树进阶练习题 二叉搜索树又称二叉排序树 ，它或者是一棵空树，或者是具有以下性质的二叉树： 若它的 左子树 不为空，则左子树上所有节点的值都 小于 根节点的

    2024年02月04日
    浏览(30)

  • 算法刷题Day 20 最大二叉树+合并二叉树+二叉搜索树中的搜索+验证二叉搜索树

    递归 递归 迭代 递归 迭代 遇到两个坑的地方： 递归的时候，不能光验证左子树的根节点小于当前根节点，右子树的根节点大于但当前根节点，别忘了左子树上的每一个节点都要求比根节点要小，右子树上的每一个节点都要求比根节点大。 根节点跟左（右）子树中的某一个节

    2024年02月16日
    浏览(44)
  • 【ONE·C++ || 二叉搜索树】

    【ONE·C++ || 二叉搜索树】

      二叉树进阶：主要介绍二叉搜索树相关内容。          1）、概念与性质介绍   二叉搜索树又称二叉排序树，它可以是一棵空树，也可以是具有以下性质的二叉树:   1、若它的左子树不为空，则左子树上所有节点的值都小于根节点的值。   2、若它的右子树

    2024年02月02日
    浏览(33)
  • 【C++】二叉搜索树BST

    【C++】二叉搜索树BST

    二叉搜索树又称二叉排序树，具有以下 性质 : 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值 它的左右子树也分别为二叉搜索树 搜索二叉树不允许数据冗余，也就是说其中 没有重复的数据

    2023年04月25日
    浏览(44)
  • 力扣第96题 不同的二叉搜索树 c++ 二叉搜索树 动态规划 + 数学思维

    力扣第96题 不同的二叉搜索树 c++ 二叉搜索树 动态规划 + 数学思维

    96. 不同的二叉搜索树 中等 相关标签 树   二叉搜索树   数学   动态规划   二叉树 给你一个整数  n  ，求恰由  n  个节点组成且节点值从  1  到  n  互不相同的  二叉搜索树  有多少种？返回满足题意的二叉搜索树的种数。 示例 1： 示例 2： 提示： 1 = n = 19 vectorint

    2024年02月06日
    浏览(35)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包