【c++】【数据结构】二叉搜索树详解

二叉搜索树的定义

二叉搜索树是一种特别的二叉树，是二叉树的搜索特化版。学过排序的都知道，在数组有序的情况下二分查找可以以极高的频率找到指定值，但以数组有序为前提未免太过理想。这时就有人想出了二叉搜索树，二叉搜索树具有以下性质：
1.可以为空树。
2.若左子树不为空，则左子树中所有结点的值都小于根结点的值。
3.若右子树不为空，则右子树中所有结点的值都大于根结点的值。
4.它的左右子树也分别为二叉搜索树。

这样，我们就能通过与根节点比较，小于根节点的值就转移到左子树的根节点，大于就转移到右子树的根节点，通过不断重复此过程的方式就能找到是否有这个数，这样最多只要查找二叉搜索树的高度次，理想情况下就是logN的实际复杂度。这看起来很美好，但是理想很丰满，现实很骨感，

这样一种类似链表的结构也是二叉搜索树，这时它的效率还高吗，跟暴力查找没区别了，虽然这只是一种极端情况，但这也体现出这种普通二叉搜索的问题所在，那就是排不满的话效率会受影响，排的越不满，效率越低，而排的满不满这件事又与根节点以及每个子树的根节点有关，也是一件所随机不可控的事，所以二叉搜索树的查找效率只有N而已，但这个思路无疑是一个好思路，只需要解决结点排不满的问题就能实现logN的效率，后续的AVL树和红黑树就解决了这样的问题，他们也是二叉搜索树。

二叉搜索树的模拟实现

#define _CRT_SECURE_NO_WARNINGS 1#include<iostream>#include<string>using namespace std;template<class K, class V>
struct BSTreeNode
{K _key;V _value;BSTreeNode* _left;BSTreeNode* _right;BSTreeNode(K key = K(), V value = V()) :_key(key),_value(value),_left(nullptr),_right(nullptr){}
};template<class K, class V>
class BSTree
{typedef BSTreeNode<K, V> Node;
public:BSTree():_root(nullptr){}BSTree(const BSTree<K, V>& t){copy(_root, t._root);}~BSTree(){Destroy(_root);}BSTree<K, V>& operator=(BSTree<K, V> t){swap(_root, t._root);return *this;}bool Insert(const K& key, const V& value){if (_root == nullptr){_root = new Node(key, value);return true;}Node* cur = _root;Node* prev = nullptr;while (cur){if (key < cur->_key){prev = cur;cur = cur->_left;}else if (key > cur->_key){prev = cur;cur = cur->_right;}else{return false;}}Node* newnode = new Node(key, value);if (key > prev->_key)prev->_right = newnode;elseprev->_left = newnode;return true;}bool Find(const K& key){Node* cur = _root;while (cur){if (key < cur->_key){cur = cur->_left;}else if (key > cur->_key){cur = cur->_right;}else{return true;}}return false;}bool Erase(const K& key){Node* cur = _root;Node* prev = nullptr;while (cur){if (key > cur->_key){prev = cur;cur = cur->_right;}else if (key < cur->_key){prev = cur;cur = cur->_left;}else//找到了{if (cur->_left == nullptr){if (cur == _root){_root = cur->_right;}else{if (prev->_left == cur)prev->_left = cur->_right;elseprev->_right = cur->_right;}}else if (cur->_right == nullptr){if(cur == _root){_root = cur->_right;}else{if (prev->_left == cur)prev->_left = cur->_left;elseprev->_right = cur->_left;}}else{Node* leftmax = cur->_left;Node* leftmax_prev = cur;while (leftmax->_right){leftmax_prev = leftmax;leftmax = leftmax->_right;}swap(leftmax->_key, cur->_key);swap(leftmax->_value, cur->_value);if (leftmax_prev->_left == leftmax)leftmax_prev->_left = leftmax->_left; elseleftmax_prev->_right = leftmax->_left;cur = leftmax;}delete cur;return true;}}return false;}void InOrder()//中序遍历，结果是顺序{_InOrder(_root);}bool InsertR(const K& key, const V& value){return _InsertR(_root, key, value);}bool EraseR(const K& key){return _Erase(_root, key);}bool FindR(const K& key){return _Find(_root, key);}
private:void copy(Node*& root, Node* const& t){if (t == nullptr) return;root = new Node(t->_key, t->_value);copy(root->_left, t->_left);copy(root->_right, t->_right);}void Destroy(Node*& root){if (root == nullptr) return;Destroy(root->_left);Destroy(root->_right);delete root;root = nullptr;}bool _Find(Node*& root, const K& key){if (root == nullptr) return false;if (root->_key == key) return true;if (key > root->_key) return _Find(root->_right, key);if (key < root->_key) return _Find(root->_left, key);}bool _Erase(Node*& root, const K& key){if (root == nullptr) return false;if (key > root->_key){_Erase(root->_right, key);}else if (key < root->_key){_Erase(root->_left, key);}else{Node* prev = root;if (root->_left == nullptr) {root = root->_right;}else if (root->_right == nullptr) {root = root->_left;}else{Node* leftmax = root->_left;while (leftmax->_right){leftmax = leftmax->_right;}swap(leftmax->_key, root->_key);swap(leftmax->_value, root->_value);return _Erase(root->_left, key);//leftmax不能传,交换完成之后二叉的位置被破坏，必须传root->_left，不然就往右边找了}delete prev;return true;}}bool _InsertR(Node*& root, const K& key, const V& value){if (root == nullptr) {root = new Node(key, value);return true;}if (key > root->_key){return _InsertR(root->_right, key, value);}else if (key < root->_key){return _InsertR(root->_left, key, value);}else{return false;}}void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_key << " " << root->_value << endl;_InOrder(root->_right);}Node* _root;
};

首先二叉搜索的结点采用了Key-Value（键值对）模型。Key作为查找的索引，而Value是与其映射的数据，通过这样的方式，可以实现数据的高效管理。其次，由于二叉搜索的结构，一些函数我写出了循环实现与递归实现的版本。

查找函数

循环版

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

循环实现的思路非常简单，创建一个指向根节点的指针cur，比较Key，要查找的Key小于当前根节点的就将根节点的左指针赋值给cur，要查找的Key大于当前根节点的就将根节点的右指针赋值给cur，不断被重复直到找到了或者cur指向空，找到返回true，没找到返回false。

递归版

	Node* FindR(const K& key){return _Find(_root, key);}
private:Node* _Find(Node*& root, const K& key){if (root == nullptr) return nullptr;if (root->_key == key) return root;if (key > root->_key) return _Find(root->_right, key);if (key < root->_key) return _Find(root->_left, key);}

由于类外无法访问私有变量且为了接口统一，所以这里又封装了一层。递归版的实现也很简单，指针为空就返回false表示没找到，指针是要找的值就返回true,都不是就比较Key向子树转移。

插入函数

循环版

bool Insert(const K& key, const V& value)
{if (_root == nullptr){_root = new Node(key, value);return true;}Node* cur = _root;Node* prev = nullptr;while (cur){if (key < cur->_key){prev = cur;cur = cur->_left;}else if (key > cur->_key){prev = cur;cur = cur->_right;}else{return false;}}Node* newnode = new Node(key, value);if (key > prev->_key)prev->_right = newnode;elseprev->_left = newnode;return true;
}

对于插入函数，我们首先要考虑空树的情况，根结点指针为空的情况就直接创建根节点返回就行了。如果不是空树，创建两个结点指针，因为是要插入，需要知道插入位置的父节点所以要有两个指针。之后只需要像查找函数一样不断比较当前节点的Key与要插入的值，然后向左子树或右子树转移就行，如果遇到了相同的值，就停止插入返回false表示插入失败，因为我们这里实现的是没有相同值的二叉搜索树。如果指针为空了就表示找到空位了，这时根据父结点的值与要插入的值插入左边或者右边就行。

递归版

	bool InsertR(const K& key, const V& value){return _InsertR(_root, key, value);}
private:bool _InsertR(Node*& root, const K& key, const V& value){if (root == nullptr) {root = new Node(key, value);return true;}if (key > root->_key){return _InsertR(root->_right, key, value);}else if (key < root->_key){return _InsertR(root->_left, key, value);}else{return false;}}

同样是先对接口封装一层，递归先对终止情况进行判断，如果为空就创建结点赋值给root，注意这里就不需要用两个指针记录父节点，因为这里用的是引用，root就是父节点对应指针（左或者右，原本还要判断的）的引用，修改root也就完成了对于父节点指针的修改，非常巧妙的完成了一个参数两用（循环就不能完成这样的操作，因为c++的引用是不能改变所指向的对象的，所以不能，循环通过不断开辟函数栈帧传值引用实现了多个引用模拟可以改变指向的引用的情况）。如果不为空就比较Key的大小做出对应操作。

删除函数

循环版

bool Erase(const K& key)
{Node* cur = _root;Node* prev = nullptr;while (cur){if (key > cur->_key){prev = cur;cur = cur->_right;}else if (key < cur->_key){prev = cur;cur = cur->_left;}else//找到了{if (cur->_left == nullptr){if (cur == _root){_root = cur->_right;}else{if (prev->_left == cur)prev->_left = cur->_right;elseprev->_right = cur->_right;}}else if (cur->_right == nullptr){if(cur == _root){_root = cur->_right;}else{if (prev->_left == cur)prev->_left = cur->_left;elseprev->_right = cur->_left;}}else{Node* leftmax = cur->_left;Node* leftmax_prev = cur;while (leftmax->_right){leftmax_prev = leftmax;leftmax = leftmax->_right;}swap(leftmax->_key, cur->_key);swap(leftmax->_value, cur->_value);if (leftmax_prev->_left == leftmax)leftmax_prev->_left = leftmax->_left; elseleftmax_prev->_right = leftmax->_left;cur = leftmax;}delete cur;return true;}}return false;
}

删除函数是实现最为复杂的一个函数，首先是创建两个指针，删除同样需要知道父结点的地址用来改变父结点指向删除位置的指针。再之后就是循环，首先我们先找到要删除的值，所以还是和查找函数一样，先循环查找，找到了再进入下一个问题，怎么删？我们将找到的结点的情况分为四种，没有子结点也就是叶子节点，有一个右节点，有一个左节点，有两个节点。没有子节点的话，直接删除再将对应父节点的指针置空就好了，因为没有子结点的情况的处理方式与只有一个子节点的处理方式一样，都是删除节点然后将父节点的对应指针指向自己的子节点（叶子节点的子节点为空），所以没有写单独的判断，无论是作为只有作为左结点还是只有右节点的情况处理都是可以的；只有左节点的话，注意删除再将父节点的对应指针只想自己的左节点就好了，，要注意要删除的就是根节点自己这种情况，因为根节点没有父节点，所以要特殊判断处理，处理的方式也很简单，就是不必处理父结点的指针，而是将根节点指针指向左节点；只有右节点的话，和只有左节点对应，删除再将父节点的对应指针只想自己的右节点，再将根节点指向右节点就好了；有两个节点的话就会比较麻烦，直接删会多出来左右子树，只有一个还好，可以直接给删除结点的父结点，但是有两个的话就麻烦了，所以这里采取和堆的思路一样，先找一个替换上来，之后删除替换下去的那个。那要找哪个才能保证能维持住原本的结构呢？答案是左子树的最大值和右子树的最小值，左子树的最大值替换上来后比左子树的所有元素都要大，比右子树中的所有数都要小，右子树的最小值也是同理。这里我选择了左子树的最大值。想找到左节点的最大值，之后交换结点的值，然后就要分两种情况讨论，一种是删除位置的父节点的右指针指向自己，一种是删除位置的父节点的左指针指向自己。可能会有人疑问既然是最大值为什么还有位于父节点的左边这种情况，如图所示，

可能会出现要删除的位置的左子树的根节点没有右子树导致自己就是最大的，此时就要特殊处理。面对这两种情况要将对应的父结点的指针指向删除位置的子节点的左指针（因为最大，所以只会有左节点存在的可能，也可能不存在）。

递归版

	bool EraseR(const K& key){return _Erase(_root, key);}
private:bool _Erase(Node*& root, const K& key){if (root == nullptr) return false;if (key > root->_key){_Erase(root->_right, key);}else if (key < root->_key){_Erase(root->_left, key);}else{Node* prev = root;if (root->_left == nullptr) {root = root->_right;}else if (root->_right == nullptr) {root = root->_left;}else{Node* leftmax = root->_left;while (leftmax->_right){leftmax = leftmax->_right;}swap(leftmax->_key, root->_key);swap(leftmax->_value, root->_value);return _Erase(root->_left, key);//leftmax不能传,交换完成之后二叉的位置被破坏，必须传root->_left，不然就往右边找了}delete prev;return true;}}

递归的思路大致与循环相同，将查找的过程用循环实现，找到根据对应的节点然后删除，这里同样使用了引用父节点指针达到一个参数两用的做法，所以只需要将对应的指针赋值给root就好了，在有两个子结点交换删除的最后还复用了自己，但要注意参数传根节点的左节点（左子树的根节点），因为传的是根节点会因为交换打乱次序的问题找不到要删的结点，注意此时不要穿局部参数，因为会用到引用的特性，如果传局部参数就无法改变根节点的内部指针了。

剩下的函数较为简单，不过多赘述。