二叉搜索树

前言

二叉树相信对大家而言已经不陌生么，那么本节来学习二叉树的升级版，二叉搜索树。二叉搜索树很简单，比二叉树之多一个条件。那么条件是什么呢？将会在文章的主体部分讲解。

不过内容会比较简单，因为相比于二叉树没有增加什么。

一、二叉搜索树的介绍

1、定义

二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉排序树。二叉搜索树作为一种经典的数据结构，它既有链表的快速插入与删除操作的特点，又有数组快速查找的优势；所以应用十分广泛，例如在文件系统和数据库系统一般会采用这种数据结构进行高效率的排序与检索操作。

2、性质

设x是二叉搜索树中的一个结点。如果y是x左子树中的一个结点，那么y.key≤x.key。如果y是x右子树中的一个结点，那么y.key≥x.key。

在二叉搜索树中：

（1）.若任意结点的左子树不空，则左子树上所有结点的值均不大于它的根结点的值。

（2）.若任意结点的右子树不空，则右子树上所有结点的值均不小于它的根结点的值。

（3）.任意结点的左、右子树也分别为二叉搜索树。

由于这样的性质在搜索或者插入数据的时候就不需要将树的所有节点进行比较，而是只需要比较key的值，小于向左子树移动，大于向右子树移动。

3、意义

不论哪一种操作，所花的时间都和树的高度成正比。因此，如果共有n个元素，那么平均每次操作需要O(logn)的时间。如果所有数据均已排序，那么二叉树将会只有左子树或者右子树。那么搜索的时间复杂度将会还原回O（N）。这是我们所不希望看到的，所以之后还会再二叉搜索树上进行进阶：平衡二叉树、红黑树、B树系列。这些树的存在价值就是降低搜索二叉树左右子树的高度差。

4、实现方法简介

二叉排序树的操作主要有：

1.查找：递归查找是否存在key。

2.插入：原树中不存在key，插入key返回true，否则返回false。

3.构造：循环的插入操作。

4.删除：

（1）叶子节点：直接删除，不影响原树。

（2）仅仅有左或右子树的节点：节点删除后，将它的左子树或右子树整个移动到删除节点的位置就可以，子承父业。

（3）既有左又有右子树的节点：找到须要删除的节点p的直接前驱或者直接后继s，用s来替换节点p，然后再删除节点s。

除此之外我们还会增加中序遍历以及析构函数。中序遍历会以子函数的方式递归实现，析构函数使用的是后序遍历的顺序，也同样会调用子函数。

最难的是删除除了需要查找之外还需要更改父节点的记录指针。

二、二叉树的实现

实现思路参考第一节第四小节内容。和之前所描述的简单二叉搜索树不同，我们这里采用key、value的形式。所以再打印上有所不同。

1、节点结构

#include <iostream>
#include <string>
using namespace std;template<class K, class V>
class BSTreeNode
{typedef BSTreeNode<K, V> Node;
public:K _key;V _value;Node* _left;Node* _right;
public:// 构造函数/默认构造BSTreeNode(const K& key = K(), const V& value = V() /*, const Node*& left = nullptr, const Node*& right = nullptr */):_key(key),_value(value),_left(nullptr),_right(nullptr){}BSTreeNode(const Node& node) {_key = node._key;_value = node._value;_right = node._right;_left = node._left;}~BSTreeNode(){}
};

2、构造函数

template<class K, class V>
class BSTree
{typedef BSTreeNode<K, V> Node;
private:Node* _root = nullptr;
};

3、插入

// 插入数据bool Insert(const K& key, const V& value){if(nullptr == _root){_root = new Node(key, value);return true;}// 搜索到对应节点Node* parent = nullptr;Node* cur = _root;while(cur){parent = cur;if(cur->_key > key){cur = cur->_left;}else if(cur->_key < key){cur = cur->_right;}else{return false;}}// 出循环表示找到了if(parent->_key > key){parent->_left = new Node(key, value);}else if(parent->_key < key){parent->_right = new Node(key, value);}return true;}

需要注意的是，第一次插入需要特殊处理。

4、搜索

// 搜索数据Node* Find(const K& key){// // 无节点单独判断// if(_root == nullptr)// {//     return nullptr;// }Node* cur = _root;while(cur){if(cur->_key > key){cur = cur->_left;}else if(cur->_key < key){cur = cur->_right;}else{return cur; // 找到了}}// 出循环没找到return nullptr;}

5、删除

    Node* DDSwapTreeNode(Node* cur){Node* right = cur->_left;Node* rightParent = cur;while(right->_right) // 左子树中找最大的右节点{rightParent = right;right = right->_right;}// 替换左子树最大节点cur->_key = right->_key;// 父节点链接最小节点的左子树，需要判断接在那一边if(rightParent->_left == right){rightParent->_left = right->_left;}else{rightParent->_right = right->_left;}return right; // 返回需要删除的节点}bool Erase(const K& key){Node* cur = _root;Node* parent = cur;// 先找到对应节点while(cur){if(cur->_key > key){parent = cur;cur = cur->_left;}else if(cur->_key < key){parent = cur;cur = cur->_right;}else{// 分为2种情况// 1. 该节点的孩子不超过1个// 2. 该节点的左右均有孩子// _root节点单独处理if(cur == _root){if(cur->_left == nullptr){_root = cur->_right;}else if(cur->_right == nullptr){_root = cur->_left;}else{cur = DDSwapTreeNode(cur);}delete cur;}else // cur != _root{   // 左子树为空if(cur->_left == nullptr){// 将子节点的非空子树给父节点if(parent->_left == cur){parent->_left = cur->_right;}else{parent->_right = cur->_right;}}else if(cur->_right == nullptr) // 右子树为空{// 将子节点的非空子树给父节点if(parent->_left == cur){parent->_left = cur->_left;}else{parent->_right = cur->_left;}}else // 左右子树均存在{cur = DDSwapTreeNode(cur);}delete cur;}return true;}}// 出循环表示节点不存在return false;}

这里构建了子函数减少了重复代码的代码量、和插入不同得到地方在于移动指针需要在判断之后。

6、中序遍历

	void InOrder(){// 母函数加载子函数_InOrder(_root);cout << endl;}private:void _InOrder(Node* root){// 中序遍历if(root == nullptr){return;}_InOrder(root->_left);cout << root->_key << " : " << root->_value << " ";_InOrder(root->_right);}

7、析构函数

    ~BSTree(){DeleteBSTree(_root);_root = nullptr;}
private:void DeleteBSTree(Node* root){// 后序遍历， 释放资源if(root == nullptr){return;}DeleteBSTree(root->_left);DeleteBSTree(root->_right);delete root;}

三、代码测试

测试代码分别检查所有函数的可用性。

void TestBSTree1()
{BSTree<string, string> dict;dict.Insert("insert", "插入");dict.Insert("erase", "删除");dict.Insert("left", "左边");dict.Insert("string", "字符串");string str;while (cin>>str){auto ret = dict.Find(str);if (ret){cout << str << ":" << ret->_value << endl;}else{cout << "单词拼写错误" << endl;}}
}void TestBSTree2()
{string strs[] = { "苹果", "西瓜", "苹果", "樱桃", "苹果", "樱桃", "苹果", "樱桃", "苹果" };// 统计水果出现的次BSTree<string, int> countTree;for (auto str : strs){auto ret = countTree.Find(str);if (ret == nullptr){countTree.Insert(str, 1);}else{ret->_value++;}}countTree.InOrder();
}void TestBSTree3()
{BSTree<int, int> bt;int arr[] = {8, 6, 12, 22, 33, 21, 1, 5, 7, 10};for(auto num : arr){bt.Insert(num, 1);}bt.InOrder();bt.Erase(8);bt.InOrder();bt.Erase(1);bt.InOrder();bt.Erase(22);bt.InOrder();
}
int main()
{// TestBSTree3();TestBSTree2();TestBSTree1();return 0;
}

删除经过TestBSTree3测试后表示无误，这里没有给图是因为打印需要修改。

作者结语

比较简单的奖励博客，难的在平衡二叉树高度上，之后的删除会更加麻烦和复杂。

本文最难的地方就在于删除的时候左右子树均存在，其他的和普通二叉树的结构一样。

二叉搜索树也相当于是逻辑树和实际结构相同的一种应用，这选的上是进步。对于大型数据的储存的基本逻辑也和二叉搜索树相似，只是会更加复杂一些，效率更高。

前言