[数据结构与算法] C++之二叉树进阶

之前我们提过普通二叉树价值不大，二叉树要叠加一些性质才能变的非常有价值。

比如查6，比根大在右树去找，比7小在左树去找就找到了，一共三次。

最多查找高度次O(logN) （这是在不极端的情况下，能做到满二叉树或完全二叉树的情况）。eg:10亿个数据最多只需要找30次。全国16亿人如果能将他们建成一个理想情况的二叉搜索树也仅仅需要31次。

但是实际情况不一定会这么理想，他也可能是下图这个样子。这种情况下就是个O(N)。

所以说搜索二叉树是不成熟的，后面就搞出来平衡搜索二叉树（AVLTree,RBTree)。

搜索二叉树中序遍历就是升序的一串数，所以他也叫二叉排序数。

二叉树的实现

定义搜索树的节点

定义二叉搜索树

(1)insert的实现

为什么这有个返回值呢？

我们写个中序遍历验证insert.注意这里的中序要嵌套这些=写，因为我们在类外面是拿不到_root的

(2)Find

(3)Erase

删除有一个孩子或者没有孩子的节点：

删除有两个孩子的节点：

替换节点：右子树的最左节点，这个节点的左孩子一定是空(他自己就是最左了)，右孩子可能是空可能非空。

Find的递归写法

Insert的递归写法

这里的引用非常的巧妙，如果直接是传值，那么该递归就失效了。?

但是Insert是不推荐递归的，如果按照有序的方式插入栈就可能会爆炸！

Erase的递归实现

二叉搜索树实现的完整代码：

二叉搜索树的应用

比如你宿舍楼的门禁系统就是K模型，把这栋楼里的学生的学号都用搜索树存储起来，来人以后刷下校园卡，门禁系统通过读卡器判断你是不是这栋楼的学生，如果是你就可以进去了。

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

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

2. KV 模型：每一个关键码 key ，都有与之对应的值 Value ，即 <Key, Value> 的键值对 。通过一个值查找另外一个值。该种方式在现实生活中非常常见：比如英汉词典就是英文与中文的对应关系 ，通过英文可以快速找到与其对应的中文，英文单词与其对应的中文<word, chinese> 就构成一种键值对；再比如 统计单词次数 ，统计成功后，给定单词就可快速找到其出现的次数，单词与其出现次数就是 <word, count> 就构成一种键值对 。

比如：实现一个简单的英汉词典 dict ，可以通过英文找到与其对应的中文，具体实现方式如下：

< 单词，中文含义 > 为键值对构造二叉搜索树，注意：二叉搜索树需要比较，键值对比较时只比较

Key查询英文单词时，只需给出英文单词，就可快速找到与其对应的key。

比如：高铁站刷身份证进站。身份证上面是没有票的信息的，那为什么用身份证刷了以后可以进站呢？机器刷了身份证，机器找到的是你的个人信息，买票以后是将你的身份信息和车次信息绑定在一起的，刷卡系统是跟铁路局的服务系统绑定在一起的，刷票时读取的是身份证，然后在服务器上去查询这个身份证关联的票，可能会有多张票，然后一次遍历这些票，看看是否与当前刷卡时刻刷卡地点所匹配的票，如果有就开闸放你进去，如果没有进禁止通行。

代码实现：

与上述二叉搜索树的实现近乎相同只是增加了一个v的模板参数

	template<class K, class V>
	//struct BinarySearchTreeNode
	struct BSTteeNode //定义结点
	{
		BSTteeNode<K,V>* _left;
		BSTteeNode<K,V>* _right;
		K _key;
		V _value;

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

	//key可能是身份证号
	//value可能是身份信息 多张票用vector<info> _vinfo
	template<class K, class V>
	struct BSTree
	{
		typedef BSTteeNode<K, V> Node;

	public:
		BSTree()
			:_root(nullptr)
		{}

		bool Insert(const K& key, const V& value)
		{
			//如果根为空
			if (_root == nullptr)
			{
				_root = new Node(key, value);
				return true;
			}

			Node* parent = nullptr; //存储cur上一个位置
			Node* cur = _root;
			while (cur)
			{
				if (key > cur->_key)
				{
					parent = cur;
					cur = cur->_right;
				}
				else if (key < cur->_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;
		}


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

		void InOrder()
		{
			_InOrder(_root);
			cout << endl;
		}
		void _InOrder(Node* root)
		{
			if (root == nullptr)
			{
				return;
			}

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

		bool Erase(const K& key)
		{
			Node* parent = nullptr;
			Node* cur = _root;
			while (cur)
			{
				if (key > cur->_key)
				{
					parent = cur;
					cur = cur->_right;
				}
				else if (key < cur->_key)
				{
					parent = cur;
					cur = cur->_left;
				}
				else
				{
					//找到了准备开始删除

					//删除有一个孩子或者没有孩子的节点
					if (cur->_left == nullptr)
					{
						if (parent == nullptr)
						{
							_root = cur->_right;
						}
						else
						{
							if (parent->_left == cur)
							{
								parent->_left = cur->_right;
							}
							else
							{
								parent->_right = cur->_right;
							}
						}

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

						delete cur;
					}
					else  //删除有两个孩子的节点
					{
						//首先找替代节点
						//替换节点：右子树的最左节点，
						//这个节点的左孩子一定是空(他自己就是最左了)，右孩子可能是空可能非空。
						Node* minparent = cur;
						Node* min = cur->_right;
						while (min->_left)
						{
							minparent = min;
							min = min->_left;
						}

						//找到之后覆盖要删除的节点。
						cur->_key = min->_key;
						cur->_value = min->_value;

						//再将min删除
						if (minparent->_left == min)
						{
							//因为是右子树的最左节点，所以一定是min的右孩子
							minparent->_left = min->_right;
						}
						else
						{
							minparent->_right = min->_right;
						}

						delete min;
					}

					return true;
				}
			}

			return false;
		}


	private:
		Node* _root;

	};

应用1：简易版字典的实现

	void TestBSTree1()
	{
		BSTree<string, string> dict;
		dict.Insert("sort", "排序");
		dict.Insert("left", "左边");
		dict.Insert("right", "右边");
		dict.Insert("map", "地图，映射");
		//...

		string str;
		while (cin >> str)
		{
			BSTteeNode<string, string>* ret = dict.Find(str);
			if (ret)
			{
				cout << "对应的中文解释:" << ret->_value << endl;
			}
			else
			{
				cout << "无此单词" << endl;
			}
		}
	}

?应用2：统计水果出现的次数

	void Test2()
	{
		//统计水果出现的次数
		string arr[] = { "苹果","西瓜","苹果","西瓜","苹果","苹果","西瓜","苹果","香蕉","苹果","香蕉","草莓"};
		      //key是水果名称，value是出现的次数
		BSTree<string, int> countTree;
		for (auto& str: arr)
		{
			BSTteeNode<string, int>* ret = countTree.Find(str);
			if (ret != nullptr)
			{
				ret->_value++;
			}
			else
			{
				countTree.Insert(str, 1);
			}

		}
		countTree.InOrder();
	}