c++-第15节-二叉树进阶-创新互联

1. 二叉搜索树 1.1.二叉搜索树概念

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

成都创新互联公司主要从事网站制作、网站建设、网页设计、企业做网站、公司建网站等业务。立足成都服务浦口,十多年网站建设经验,价格优惠、服务专业,欢迎来电咨询建站服务:13518219792

注：

1.搜索二叉树数据的查找效率为O(N)，当搜索二叉树接近完全时，数据的查找效率较高，接近。

2.当使用中序遍历遍历搜索二叉树时，遍历出来的数据是增序的。

1.2.二叉搜索树的实现

二叉搜索树普通实现版本

BinarySearchTree.h文件：

#pragma once

templatestruct BSTreeNode
{
	BSTreeNode* _left;
	BSTreeNode* _right;

	K _key;

	BSTreeNode(const K& key)
		:_left(nullptr)
		, _right(nullptr)
		, _key(key)
	{}
};

templateclass BSTree
{
	typedef BSTreeNodeNode;
private:
	void DestoryTree(Node* root)
	{
		if (root == nullptr)
			return;

		DestoryTree(root->_left);
		DestoryTree(root->_right);
		delete root;
	}

	Node* CopyTree(Node* root)
	{
		if (root == nullptr)
			return nullptr;

		Node* copyNode = new Node(root->_key);
		copyNode->_left = CopyTree(root->_left);
		copyNode->_right = CopyTree(root->_right);

		return copyNode;
	}
public:
	// 强制编译器自己生成构造
	// C++11
	BSTree() = default;

	BSTree(const BSTree& t)
	{
		_root = CopyTree(t._root);
	}

	// t1 = t2
	BSTree& operator=(BSTreet)
	{
		swap(_root, t._root);
		return *this;
	}

	~BSTree()
	{
		DestoryTree(_root);
		_root = nullptr;
	}

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

	//const Node* Find(const K& key)
	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
			{
				// 一个孩子--左为空 or 右为空
				// 两个孩子 -- 替换法
				if (cur->_left == nullptr)
				{
					//if (parent == nullptr)
					if (cur == _root)
					{
						_root = cur->_right;
					}
					else
					{
						if (cur == parent->_left)
						{
							parent->_left = cur->_right;
						}
						else
						{
							parent->_right = cur->_right;
						}
					}
					delete cur;
				}
				else if (cur->_right == nullptr)
				{
					//if (parent == nullptr)
					if (cur == _root)
					{
						_root = cur->_left;
					}
					else
					{
						if (cur == parent->_left)
						{
							parent->_left = cur->_left;
						}
						else
						{
							parent->_right = cur->_left;
						}
					}

					delete cur;
				}
				else // 两个孩子都不为空
				{
					// 右子树的最小节点替代
					Node* minParent = cur;
					Node* minRight = cur->_right;
					while (minRight->_left)
					{
						minParent = minRight;
						minRight = minRight->_left;
					}

					swap(minRight->_key, cur->_key);
					//cur->_key = minRight->_key;
					if (minParent->_left == minRight)
					{
						minParent->_left = minRight->_right;
					}
					else
					{
						minParent->_right = minRight->_right;
					}

					delete minRight;
				}

				return true;
			}
		}

		return false;
	}

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

private:

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

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

void TestBSTree1()
{
	BSTreet;
	int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
	for (auto e : a)
	{
		t.Insert(e);
	}
	t.InOrder();

	t.Insert(16);
	t.Insert(9);

	t.InOrder();
}

void TestBSTree2()
{
	BSTreet;
	int a[] = { 8, 7, 9, 12, 5, 19, 20, 30,7,12 };
	for (auto e : a)
	{
		t.Insert(e);
	}
	t.InOrder();
}

void TestBSTree3()
{
	BSTreet;
	int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
	for (auto e : a)
	{
		t.Insert(e);
	}
	t.InOrder();

	t.Erase(3);
	t.Erase(8);

	t.InOrder();
	t.Erase(14);
	t.Erase(7);
	t.InOrder();

	for (auto e : a)
	{
		t.Erase(e);
	}
	t.InOrder();
}

void TestBSTree4()
{
	BSTreet;
	int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
	for (auto e : a)
	{
		t.Insert(e);
	}
	t.InOrder();

	BSTreecopy = t;
	copy.InOrder();
}

test.cpp文件：

#define _CRT_SECURE_NO_WARNINGS 1
#includeusing namespace std;

#include "BinarySearchTree.h"

int main()
{
	TestBSTree3();

	return 0;
}

注：

1. 二叉搜索树的查找介绍 a.从根开始比较，查找，比根大则往右边走查找，比根小则往左边走查找。 b.最多查找高度次，走到到空，还没找到，这个值不存在。 2. 二叉搜索树的插入介绍 插入的具体过程如下： a.树为空，则直接新增节点，赋值给root指针 b.树不空，按二叉搜索树性质查找插入位置，插入新节点 具体思路为：定义两个指针parent和cur，cur查找插入位置，parent记录cur上一个位置，当cur找到插入位置时（cur为空时），开辟节点给cur并和parent进行链接。

注：

（1）搜索二叉树一般不允许插入和里面数据相同的数据，会造成冗余。

（2）搜索二叉树数据插入的顺序不同，树的形状一般也不同，当以近似有序的数据顺序依次插入，那么二叉树的形状近似一个链表，搜索的时间复杂度接近O(N)

3. 二叉搜索树的删除介绍  

首先查找元素是否在二叉搜索树中，如果不存在，则返回, 否则要删除的结点可能分下面四种情况： a. 要删除的结点无孩子结点 b. 要删除的结点只有左孩子结点 c. 要删除的结点只有右孩子结点 d. 要删除的结点有左、右孩子结点 看起来有待删除节点有4中情况，实际情况a可以与情况b或者c合并起来，因此真正的删除过程如下： 情况b：删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点--直接删除 情况c：删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点--直接删除 情况d：在删除结点的左子树中寻找大值结点（左子树中序下的最后一个结点），或者删除结点的右子树中寻找最小值结点（右子树中序下的第一个结点），用左子树大值结点的值或右子树最小值结点的值填补到被删除节点中，再来处理左子树大值结点或右子树最小值结点的删除问题--替换法删除

情况b和情况c的实现代码（情况a融合在情况b中）如果如下图一所示，那么是有BUG的，如下图二所示的搜索树要删除根节点，此时parent指针指向空指针，parent->left或者parent->right会访问空指针，程序报错。解决方法是让搜索树的_root成员变量指向根结点的那个孩子结点即可，如下图三所示。

情况d的代码实现如果如下图一所示，那么是错误的，因为Swap交换之后该树不再是一个搜索二叉树，交换之后再递归调用Erase函数删除key是找不到key值结点并返回false的，所以我们应该手动去删除。

我们利用minRight指针找到右子树最小值结点，minParent指针指向minRight指针指向结点的父节点，然后将minRight指针指向结点的值（右子树最小值）赋值给cur指针指向的结点值，minParent指针指向结点的_left指针和minRight指针指向结点的_right指针链接（此时一定是minParent指针指向结点的_left指针指向minRight指针指向的结点，minRight指针指向结点的_left指针一定是NULL，_right指针可能为空可能指向其他结点，所以要删除minRight指针指向结点直接将minParent指针指向结点的_left指针指向minRight指针指向结点的_right指针指向的地址，然后释放minRight指针指向结点即可），释放minRight指针指向的结点，如下图三所示。

上面图三所示的代码是有BUG的，因为有可能删除结点的右子树的根就是最小结点，如下图一所示，要删除值为8的结点（根节点），此时该节点右子树的根（值为10的结点）就是最小结点。开始minRight指向值为10的结点，while循环判断条件为假不进入循环，minRight最终指向值为10的结点，也就是右子树的最小结点，而minParent指针为空，minParent指针应该为值为8的结点，所以应该用cur对minParent指针初始化。并且此时minParent指针指向结点的_right指针和minRight指针指向结点的_right指针链接（此时一定是minParent指针指向结点的_right指针指向minRight指针指向的结点，minRight指针指向结点的_left指针一定是NULL，_right指针可能为空可能指向其他结点，所以要删除minRight指针指向结点直接将minParent指针指向结点的_right指针指向minRight指针指向结点的_right指针指向的地址，然后释放minRight指针指向结点即可），释放minRight指针指向的结点。代码中，因为最后minRight指针指向结点既有可能是minParent指针指向结点的左节点也有可能是minParent指针指向结点的右节点，因此需要进行判断，如下图二所示。

4.搜索二叉树上面这种结构允许增删查功能，不允许改，修改一个节点的数值那么这个树很可能不再是搜索二叉树。

5.搜索二叉树的拷贝构造函数和赋值运算符重载函数需要进行深拷贝，这里深拷贝不能复用insert插入函数，因为插入的顺序不同搜索二叉树也不同。我们写一个CopyTree函数来递归创建一个相同的树，如下图一所示，然后搜索二叉树的拷贝构造函数复用CopyTree函数即可，如下图二所示

如果写了构造函数，那么系统自动生成的默认构造函数就不会再自动生成了，拷贝构造函数也是构造函数，如果我们写了拷贝构造函数，系统自动生成的默认构造函数不再生成，我们需要自己去显式的写构造函数。在c++11中，可以使用default关键字强制编译器自己生成默认构造函数，如下图所示

搜索二叉树的赋值运算符重载函数可以复用拷贝构造函数来进行现代写法的代码实现，如下图所示

搜索二叉树的析构函数，我们写一个DestoryTree函数来销毁释放树，如下图一所示，然后二叉树的析构函数复用DestoryTree函数即可，如下图二所示

二叉搜索树递归实现版本

BinarySearchTree.h文件：

#pragma once

template//struct BinarySearchTreeNode
struct BSTreeNode
{
	BSTreeNode* _left;
	BSTreeNode* _right;

	K _key;

	BSTreeNode(const K& key)
		:_left(nullptr)
		, _right(nullptr)
		, _key(key)
	{}
};

templateclass BSTree
{
	typedef BSTreeNodeNode;
private:
	void DestoryTree(Node* root)
	{
		if (root == nullptr)
			return;

		DestoryTree(root->_left);
		DestoryTree(root->_right);
		delete root;
	}

	Node* CopyTree(Node* root)
	{
		if (root == nullptr)
			return nullptr;

		Node* copyNode = new Node(root->_key);
		copyNode->_left = CopyTree(root->_left);
		copyNode->_right = CopyTree(root->_right);

		return copyNode;
	}
public:
	// 强制编译器自己生成构造
	// C++11
	BSTree() = default;

	BSTree(const BSTree& t)
	{
		_root = CopyTree(t._root);
	}

	// t1 = t2
	BSTree& operator=(BSTreet)
	{
		swap(_root, t._root);
		return *this;
	}

	~BSTree()
	{
		DestoryTree(_root);
		_root = nullptr;
	}

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

private:
	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* minRight = root->_right;
				while (minRight->_left)
				{
					minRight = minRight->_left;
				}

				swap(root->_key, minRight->_key);

				return _EraseR(root->_right, key);
			}

			delete del;
			return true;
		}
	}

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

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

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

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

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

void TestBSTree1()
{
	BSTreet;
	int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
	for (auto e : a)
	{
		t.InsertR(e);
	}
	t.InOrder();

	t.InsertR(9);

	BSTreecopy = t;
	copy.InOrder();
}

void TestBSTree2()
{
	BSTreet;
	int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
	for (auto e : a)
	{
		t.InsertR(e);
	}
	t.InOrder();
	t.EraseR(3);
	t.EraseR(8);

	t.InOrder();
	t.EraseR(14);
	t.EraseR(7);
	t.InOrder();

	for (auto e : a)
	{
		t.EraseR(e);
	}
	t.InOrder();
}

test.cpp文件：

#define _CRT_SECURE_NO_WARNINGS 1
#includeusing namespace std;

#include "BinarySearchTree.h"

int main()
{
	TestBSTree2();

	return 0;
}

注：

1.搜索二叉树插入函数的递归实现，用要插入的值和根结点值进行比较，如果要插入的值大于根结点值，则转换成根节点的右子树插入该值，如果要插入的值小于根结点值，则转换成根节点的左子树插入该值，要删除的值等于根结点值则返回false（搜索二叉树内不允许有相同数值的结点），如果根节点为空，则创建一个值为要插入值的结点，然后和父亲结点进行链接即可，但是如何和父亲结点进行链接呢？

方法一：可以给_InsertR函数加一个parent指针参数，如下图所示，每次调用_InsertR函数的时候除了将root的左子树和右子树传过去也将root传过去，那么每次parent指针指向的都是本次root结点的父结点，最后如果根节点为空，则创建一个值为要插入值的结点，然后和parent指针指向的结点进行链接即可。

方法二：可以给_InsertR函数的root参数加上引用，如下图所示，这样如果根节点为空时，则创建一个值为要插入值的结点，将结点指针赋值给root，因为这里root是上一层父节点的_left或_right的引用，那么赋值的时候就已经和父结点进行了链接。

因为方法二的实现更加简洁，我们使用方法二的思路来实现递归版本的插入函数，如下图所示

2.如下图所示是搜索二叉树删除函数的递归实现，用要删除入的值和根结点值进行比较，如果要删除的值大于根结点值，则转换成根节点的右子树删除该值，如果要删除的值小于根结点值，则转换成根节点的左子树删除该值，如果要删除的值等于根结点值，则和普通搜索二叉树删除函数一样，需要分三种情况（要删除的结点无孩子结点的情况融合在要删除的结点只有左孩子结点的情况内）

（1）要删除的结点只有左孩子结点，递归找到要删除的结点，此时root指向要删除的结点，那么需要将root指针指向结点的_left指针指向结点和root指针指向结点的父节点进行链接，然后释放root指针指向的结点，这里直接将root->_left赋值给root就可以完成除释放结点以外的其他工作，因为这里root是上一层父节点的_left或_right的引用，那么赋值的时候就已经将root指针指向结点的_left指针指向结点和root的父结点进行了链接。 （2）要删除的结点只有右孩子结点，递归找到要删除的结点，此时root指向要删除的结点，那么需要将root指针指向结点的_right指针指向结点和root指针指向结点的父节点进行链接，然后释放root指针指向的结点，这里直接将root->_right赋值给root就可以完成除释放结点以外的其他工作，因为这里root是上一层父节点的_left或_right的引用，那么赋值的时候就已经将root指针指向结点的_right指针指向结点和root的父结点进行了链接。 （3）要删除的结点有左、右孩子结点，与普通搜索二叉树那里一样，递归找到要删除的结点，此时root指向要删除的结点，使用minRight指针找到要删除结点的右子树最小值结点（找左子树大值结点也行，这里以右子树最小值结点为例），将minRight指针指向的右子树最小值结点的值与root指向的要删除结点的值交换，然后释放minRight指针指向的结点即可。释放minRight指针指向的结点有两种方式。一种方式和普通搜索二叉树那里一样，使用minParent指针来找到要删除结点右子树最小值结点的父节点，将该父节点和右子树最小值结点的子节点进行链接然后释放minRight指针指向的右子树最小值结点。另一种方式是调用递归删除函数，删除root指向的要删除结点右子树中的要删除的值（因为原本要删除结点的右子树最小值结点交换后此时存的值是要删除的值）（交换后root指向的要删除结点右子树依然是一颗搜索树）

注：先使用del指针将root指针的内容保存起来，那么del指针和root指针此时指向相同的结点，最后要释放root指针指向结点的时候，此时root指针已经被修改，delete del就释放了原root指针指向的结点

1.3.二叉搜索树的应用

1.K模型：K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到的值。 比如：给一个单词word，判断该单词是否拼写正确，具体方式是以词库中所有单词集合中的每个单词作为key，构建一棵二叉搜索树  。在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。 K模型二叉搜索树代码实现：

#pragma once

#includenamespace key
{
	template//struct BinarySearchTreeNode
	struct BSTreeNode
	{
		BSTreeNode* _left;
		BSTreeNode* _right;

		K _key;

		BSTreeNode(const K& key)
			:_left(nullptr)
			, _right(nullptr)
			, _key(key)
		{}
	};

	templateclass BSTree
	{
		typedef BSTreeNodeNode;
	private:
		void DestoryTree(Node* root)
		{
			if (root == nullptr)
				return;

			DestoryTree(root->_left);
			DestoryTree(root->_right);
			delete root;
		}

		Node* CopyTree(Node* root)
		{
			if (root == nullptr)
				return nullptr;

			Node* copyNode = new Node(root->_key);
			copyNode->_left = CopyTree(root->_left);
			copyNode->_right = CopyTree(root->_right);

			return copyNode;
		}
	public:
		// 强制编译器自己生成构造
		// C++11
		BSTree() = default;

		BSTree(const BSTree& t)
		{
			_root = CopyTree(t._root);
		}

		// t1 = t2
		BSTree& operator=(BSTreet)
		{
			swap(_root, t._root);
			return *this;
		}

		~BSTree()
		{
			DestoryTree(_root);
			_root = nullptr;
		}

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

	private:
		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* minRight = root->_right;
					while (minRight->_left)
					{
						minRight = minRight->_left;
					}

					swap(root->_key, minRight->_key);

					return _EraseR(root->_right, key);
				}

				delete del;
				return true;
			}
		}

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

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

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

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

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

	void TestBSTree1()
	{
		BSTreet;
		int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
		for (auto e : a)
		{
			t.InsertR(e);
		}
		t.InOrder();

		t.InsertR(9);

		BSTreecopy = t;
		copy.InOrder();
	}

	void TestBSTree2()
	{
		BSTreet;
		int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
		for (auto e : a)
		{
			t.InsertR(e);
		}
		t.InOrder();
		t.EraseR(3);
		t.EraseR(8);

		t.InOrder();
		t.EraseR(14);
		t.EraseR(7);
		t.InOrder();

		for (auto e : a)
		{
			t.EraseR(e);
		}
		t.InOrder();
	}

}

2.KV模型：每一个关键码key，都有与之对应的值Value，即的键值对。该种方式在现实生活中非常常见： 比如：英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英 文单词与其对应的中文就构成一种键值对。 比如：统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出 现次数就是就构成一种键值对。 KV模型二叉搜索树代码实现：

#pragma once

#includenamespace key_value
{
#pragma once

	templatestruct BSTreeNode
	{
		BSTreeNode* _left;
		BSTreeNode* _right;

		const K _key;
		V _value;

		BSTreeNode(const K& key, const V& value)
			:_left(nullptr)
			, _right(nullptr)
			, _key(key)
			, _value(value)
		{}
	};

	templateclass BSTree
	{
		typedef BSTreeNodeNode;
	public:

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

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

	private:
		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* minRight = root->_right;
					while (minRight->_left)
					{
						minRight = minRight->_left;
					}

					swap(root->_key, minRight->_key);

					return _EraseR(root->_right, key);
				}

				delete del;
				return true;
			}
		}

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

	void TestBSTree1()
	{
		BSTreeECDict;
		ECDict.InsertR("root", "根");
		ECDict.InsertR("string", "字符串");
		ECDict.InsertR("left", "左边");
		ECDict.InsertR("insert", "插入");
		//...
		string str;
		while (cin >>str)  //while (scanf() != EOF)
		{
			//BSTreeNode* ret = ECDict.FindR(str);
			auto ret = ECDict.FindR(str);
			if (ret != nullptr)
			{
				cout<< "对应的中文:"<< ret->_value<< endl;
			}
			else
			{
				cout<< "无此单词，请重新输入"<< endl;
			}
		}
	}

	void TestBSTree2()
	{
		string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
		// 水果出现的次数
		BSTreecountTree;
		for (const auto& str : arr)
		{
			auto ret = countTree.FindR(str);
			if (ret == nullptr)
			{
				countTree.InsertR(str, 1);
			}
			else
			{
				ret->_value++;  // 修改value
			}
		}

		countTree.InOrder();
	}
}

注：

1.在KV模型的搜索二叉树中插入、查找、删除函数仍然都是以key为依据进行的操作的。 2.KV模型的搜索二叉树中，每个节点的value值可能相同，每个节点的key值都不相同 3.与K模型搜索二叉树不同的是，KV模型在_FindR搜索函数中返回值应该为找到的结点指针。K模型搜索二叉树_FindR搜索函数不返回结点指针的原因是不能修改key的值，否则很可能不再是一个搜索树，KV模型搜索二叉树_FindR搜索函数返回结点指针的原因是key的值不能修改，但是可以修改value值，因此找到对应结点后需要返回结点的指针，为了保证返回结点指针后key值不被修改，将结点的_key成员变量用const修饰，这样建立结点的时候可以对key值进行初始化，后面无法再被修改，如下图所示。 4.代码while (cin >>str)和代码while (scanf() != EOF)的功能相同，都是持续输入输出内容。当scanf函数读取控制台数据时遇到文件结束/文件读取失败标志EOF时会返回EOF；string类里面重载的operator>>流提取函数返回的是cin，如下图一所示，cin是istream类的对象。 ios类中有两个函数c++98中的operator void* ()和c++11中的operator bool()如下图一二所示，这两个函数的功能是判断是否提取到文件结束/文件读取失败标志EOF，提取到EOF则返回真，没有提取到EOF则返回假。 istream类是继承ios类的，因此istream类的对象cin也有operator void* ()和operator bool()两个函数。当cin >>str代码返回cin进行while循环条件判断的时候，c++98中cin对象会进行隐式类型转换，会cin.operator void*调用operator void* ()函数，该函数判断是否遇见文件结束/文件读取失败标志EOF，如果是EOF标志就返回空指针，如果不是EOF就返回非空指针；c++11中cin对象会进行隐式类型转换，会cin.operator bool调用operator bool()函数，该函数判断是否遇见文件结束/文件读取失败标志EOF，如果是EOF标志就返回0，如果不是EOF就返回1。

如果想手动输入EOF标志来退出持续输入输出状态可以使用Ctrl+z，Ctrl z控制台就会输入EOF，然后回车让scanf或>>进行读取即可。

ctrl+c也可以退出持续输入输出状态，ctrl c的功能是直接结束进程。

下图一所示的代码与上面while (cin >>str)部分的原理类似，while的判断部分是A类的对象a，在判断的时候对象a会进行隐式类型转换，自动去调用对象a里面的operator bool函数，operator bool函数的返回值作为while循环的判断条件。其中代码while(a)与while(a.operator bool)是等价的。

如下图二所示，这里while(a)中a对象的隐式类型转换和A aa = 10中的隐式类型转换相同。A aa = 10代码因为类型不同，会先调用A类的构造函数构造成员变量_a为10的对象，此时类型相同，再拷贝构造给aa（编译器优化成直接用10对aa对象调用构造函数进行构造）；while(a)代码因为对象a和真假判断的bool类型不同，会先调用A类的operator bool函数，operator bool函数返回一个bool类型的值，此时类型相同可以进行while循环的判断。那么代码bool ret = a，使用A类型的对象a初始化bool类型的对象ret也是可以的，这里类型不同，发生隐式类型转换，对象a调用operator bool函数返回一个bool类型的值，赋值给ret。

我们发现库中的operator bool函数是用explicit关键字修饰的，如下图一所示，explicit关键字限制不能使用该函数进行隐式类型转换，那为什么我们前面使用代码while (cin >>str)，cin对象还能调用其operator bool函数呢？

其实explicit关键字只限制类似A aa = 10和bool ret = a这种调用explicit所修饰的函数进行隐式类型转换初始化的情况，而不会去限制while(a)这种的隐式类型转换，如下图一所示。

其实也可以使用类似operator int()的函数来满足类似int y = a和while(a)，将A类型的对象a隐式类型转换成对应类型的功能，如下图二所示。

3.二叉搜索树具有去重+排序功能。将所有的数据依次插入到二叉搜索树中（去重），然后进行中序遍历（排序），得到的结果就是对数据集去重排序后的结果，整个去重排序的效率可以达到（搜索树是完全二叉树的情况）。

注：

1.搜索二叉树如果插入顺序不同，树的形状也不同，如果形状近似一个完全二叉树，那么无论是K模型、KV模型的搜索效率还是去重排序的效率都很高，但是如果形状近似一个链表，那么K模型、KV模型的搜索效率和去重排序的效率都很低。

2.我们后面会学到平衡树，平衡树是对搜索二叉树的一种改进，使得插入数据后树的形状接近完全二叉树

3.K模型搜索二叉树对应std库中的数据结构是set，KV模型搜索二叉树对应std库中的数据结构是map

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

网站标题：c++-第15节-二叉树进阶-创新互联
转载来于：http://cqcxhl.com/article/pdodg.html