C++13:搜索二叉树

目录

搜索二叉树概念

模拟实现搜索二叉树

 插入函数实现

 插入函数实现（递归）

查找函数实现

 删除函数实现

 删除函数实现（递归）

中序遍历实现

 拷贝构造函数实现

 析构函数实现

 赋值重载

---

我们在最开始学习二叉树的时候，最开始接触的就是堆，但那个结构上并不是真正的二叉树，后来又借助链表实现了真正的结构上的二叉树，二叉树不仅仅只是在OJ题上刁难我们，其实当实现了一定的节点逻辑之后，也可以形成效率极高的数据结构，这个二叉树就是搜索二叉树。

搜索二叉树概念

 对于一颗搜索二叉树来说，它的节点内存储的值遵循如下的规则

• 右子树节点的值一定大于当前节点的值
• 左子树节点的值一定小于当前节点的值

 而对于其结构来说

• 搜索二叉树不允许已存在于二叉树内部的值再次插入
• 搜索二叉树的左右子树也必须是搜索二叉树
•  数据插入的顺序不同，搜索二叉树的形状也会不同 

---

 这样的结构让搜索二叉树的效率在平衡的情况下效率变得非常的高

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

 

 但是当插入数据是有序的时候，搜索二叉树会退化成单叉树

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

 其整体的树结构以及逻辑就差不多如上所述了，接下来就是模拟实现。

模拟实现搜索二叉树

 插入函数实现

 首先先定义一下节点的结构，我们加入模板。

	template<class K>struct BSNode{BSNode<K>* _left;BSNode<K>* _right;K _key;BSNode(K val = K()):_left(nullptr), _right(nullptr), _key(val){}};

 接着我们实现插入函数，逻辑并不困难，总结如下：

1.  树为空，则直接新增节点，赋值给root指针
2.  树不空，按二叉搜索树性质查找插入位置，插入新节点
3. 插入有成功与失败一说，假如插入的值已存在于树内，则插入失败
4. 以K值为判定条件插入左子树或者右子树，比K大插右子树，比K小插左子树
5. 需要额外创建一个父节点来链接节点。

		//以K值为判定条件插入左子树或者右子树，比K大插右子树，比K小插左子树//若遇到相等的，插入失败，不插bool Insert(const K& val){if (_root == nullptr){_root = new Node(val);return true;}Node* cur = _root;Node* parent = cur;while (cur){//比K小，往左子树走if (val < cur->_key){parent = cur;cur = cur->_left;}//比K大，往右子树走else if (val > cur->_key){parent = cur;cur = cur->_right;}//相等，插入不了，返回一个falseelse{return false;}}//跳出while时，也就是遇到空了，新建一个节点赋值然后链接节点if (parent->_key < val)parent->_right = new Node(val);else if (parent->_key > val)parent->_left = new Node(val);return true;}

 插入函数实现（递归）

 二叉树的插入也可以是递归，毕竟二叉树的结构本身就适合递归

递归的逻辑：

• 终止条件：遇到了空，那么就是到位了，或者说一个空节点,创建节点准备链接
• 本次递归应该做的事：检查当前插入的值是否大于K，大于走右树，小于走左树
• 返回的信息：同循环版本，返回true Or false

 但是这里有个问题，想要在类内部实现递归轻而易举，直接传递根节点即可，但是它的访问限定符是私有，这意味着我们无法在类外部调用这个递归插入，所以我们还需要额外实现一个GetRoot或者是私有的内嵌递归函数来获取到根。

 其中，传递的形参必须是引用，因为递归的栈帧问题，要        是想要在递归的途中链接节点之间的指针，还需要额外的parent的节点，但会让程序变得冗杂，一个引用则可以非常巧妙地解决问题，因为正好上一层传递下来的引用就是父节点的别名，直接链接即可。

同样的，借助二级指针也是可以实现的，但是完全比不上引用。

		bool InsertR(const K& val){return _InsertR(_root, val);}private:bool _InsertR(Node*& root,const K& val){//假如走到了空，那么就是到位了，或者是一个空树,创建节点准备链接if (root == nullptr){root = new Node(val);return true;}//大于，向右走if (val > root->_key)return _InsertR(root->_right, val);else if (val < root->_key)return _InsertR(root->_left, val);elsereturn false;}

查找函数实现

查找的逻辑同插入没什么区别，也可以实现递归版本，在这里就不列出逻辑了。

		//查找函数，找到了返回true，找不到返回falsebool Find(const K& val){Node* cur = _root;while (cur){//大于就向右边找if (val > cur->_key)cur = cur->_right;//小于就向左边查找else if (val < cur->_key)cur = cur->_left;//相等就找着了elsereturn true;}//没找着return false;		}

 删除函数实现

 删除的情况较多且有些复杂，逻辑如下：

        删除有三种情况

1. 删一个有孩子的节点，若其左为空，把右边给父节点，
2. 若右边为空，则把左边的孩子给父节点
3.  删一个带有多个孩子的节点，比较复杂,需要替换删除，期间也需要注意删除根的情况,找右子树的最小节点，也就是右子树的最左边的节点与被删除的节点交换，然后删去右子树最左节点。

情况1,2 示意图

 情况3示意图,图中示意为替换法逻辑，还需要额外处理删除根节点的情况。

 那么代码实现如下

		bool erase(const K& val){Node* cur = _root;Node* parent = nullptr;while (cur){if (val > cur->_key){parent = cur;cur = cur->_right;}else if (val < cur->_key){parent = cur;cur = cur->_left;}//相等就找到了，找到后进行删除else{//左孩子为空,右孩子为空，以及左右都不为空,其中这三种情况下，还需要特殊处理删除根节点的时候//其中只有一个孩子的情况下，只需要托孤即可if (cur->_left == nullptr){//如果左孩子为空，那么先判断一下是不是根节点。if (cur == _root){//是根节点，直接让cur-的右边做根_root = cur->_right;}//删的不是根，直接托孤给parentelse{//需要被托孤的是到if (parent->_left == cur)parent->_left = cur->_right;elseparent->_right = cur->_right;}delete cur;cur = nullptr;}//有左孩子，没右孩子else if (cur->_right == nullptr){//如果是根，就把根给到左孩子if (cur == _root)_root = cur->_left;else{if (parent->_left == cur)parent->_left = cur->_left;elseparent->_right = cur->_left;}delete cur;cur = nullptr;}//左右孩子都不是空，需要替换删除，期间也需要注意删除根的情况else{//找右子树的最小节点，也就是右子树的最左边//先找最小值，有根判根//留一个parent，以防止min后面还有节点Node* minparent = cur;Node* min = cur->_right;while (min->_left){minparent = min;min = min->_left;}cur->_key = min->_key;//给完跟在删除min之前还要把min后面的节点都街上if (minparent->_left == min)minparent->_left = min->_right;elseminparent->_right = min->_right;delete min;min = nullptr;}return true;}}//没找着return false;}

 删除函数实现（递归）

 主体逻辑同循环版本差不太多，需要注意的是替换法删除的部分，可以很巧妙的再次调用一次递归去删除被替换的节点。

		bool _earseR(Node*& root, const K& val){if (root == nullptr)return false;if (root->_key > val){return _earseR(root->_left, val);}else if(root->_key < val){return _earseR(root->_right, val);}else//找到了{//叶子节点无需特殊处理，在处理单子树的过程中顺带解决了//没有左孩子,那么一定有右孩子,直接链接右孩子到父节点,这种情况是根节点的完全没有左子树，也就是直接更新根//用一个节点保存前根，Node* del = root;if (root->_left == nullptr){root = root->_right;}else if (root->_right == nullptr){root = root->_left;}else//交换，但是走的是递归，可以很巧妙的交换两个节点的值，然后再走递归去删掉替死鬼。{Node* min = root->_right;while (min->_left)min = min->_left;swap(root->_key, min->_key);return _earseR(root->_right, val);}delete del;del = nullptr;return true;}}Node* _root = nullptr;};

中序遍历实现

 这块就没啥好说的，除了记得需要额外内嵌一个递归函数。

		void InOrder(){Node* root = GetRoot();_inorder(root);}void _inorder(Node* _root){if (_root == nullptr){return;}_inorder(_root->_left);cout << _root->_key << " ";_inorder(_root->_right);}

 拷贝构造函数实现

 由于搜索二叉树的插入顺序会对形状产生影响，我们使用递归来对其节点挨个拷贝。

		//拷贝构造//拷贝构造走一个前序遍历构建，走一个递归。每前序遍历一个节点就新建一个节点BSTree(const BSTree<K>& t2){_root = Copy(t2._root);}// 1.终止条件?走到空结束// 2.这次递归应该完成的任务？创建节点，// 3.返回的信息？返回节点的指针，空反指针并将节点链接起来//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(){Destory();_root = nullptr;}//销毁void Destory(){while (_root)erase(_root->_key);}

 赋值重载

 同vector一样，我们使用摇人打工法实现赋值重载。

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

那么以上就是一个具有最基本功能的搜索二叉树了，接下来我们尝试实现一下其KV结构。 

KV结构，也就是类似于Pair的结构，一个Key绑定对应的Val，通过对比Key来找到对应的Val。

template<class K, class V>class KVTree{public:typedef KVNode<K,V> Node;bool Insert(const K& key,const V& val){if (_root == nullptr){_root = new Node(key,val);return true;}Node* cur = _root;Node* parent = cur;while (cur){//比K小，往左子树走if (key < cur->_key){parent = cur;cur = cur->_left;}//比K大，往右子树走else if (key > cur->_key){parent = cur;cur = cur->_right;}//相等，插入不了，返回一个falseelse{return false;}}//跳出while时，也就是遇到空了，新建一个节点赋值然后链接节点if (parent->_key < key){parent->_right = new Node(key,val);}else if (parent->_key > key){parent->_left = new Node(key,val);}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(){Node* root = GetRoot();_inorder(root);}void _inorder(Node* _root){if (_root == nullptr)return;_inorder(_root->_left);cout << _root->_key << ":"<< _root->_val<<endl;_inorder(_root->_right);}private:Node* GetRoot(){return _root;}Node* _root = nullptr;};

借助一个统计水果出现的次数来测试一下

	void TextKVtree1(){KVTree<string, int> KV;string str[] ={ "菠萝","荔枝","草莓","菠萝","菠萝" ,"西瓜" ,"草莓" ,"橙子" ,"荔枝" ,"牛油果" ,"西瓜" ,"西瓜" };for (auto& e : str){KVNode<string, int>* ret = KV.Find(e);if (ret){ret->_val++;}else{KV.Insert(e,1);}}KV.InOrder();}

 如上就是一个二叉搜索树的基本实现