【C++与数据结构】搜索二叉树（BinarySearchTree）

一、概念：

二叉搜索树又称为二叉排序树，因为它具有以下性质：

1、如果二叉树的左子树不为空，那么它左子树的任意一个节点的值都小于根节点。

2、如果二叉树的右子树不为空，那么它右子树的任意一个节点的值都大于根节点。

3、并且这个根节点的左子树和右子树都是二叉搜索树。

4、二叉搜索树可以为空树。

二、二叉树的操作：

1、构建二叉树节点：

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

如上就是构建出每一个二叉树的节点，接下来定义一个BSTree类，在里面进行操作的基础实现即可。

在类里面的操作中，有两类函数，一类是在类里面做私有的，另一类是在类里面做公有的，也就是给外界访问的，因为在递归实现中外界不方便访问私有成员_root，这样在类中私有函数作为公有函数的子函数，公有函数只需调用对应的子函数即可。

2、析构与构造：

在BSTree类中只定义一个成员变量_root根节点，在构造函数中进行初始化列表，将_root指向空。

拷贝构造：

思路：

拷贝构造中，直接给_root调用私有函数Copy ，

Copy实现思路：

这里采用递归方式，采用后序遍历

之后在拷贝构造中调用即可。

public:BSTree(const BSTree<K>& t){_root = Copy(t._root);}
private:Node* Copy(Node* root){if (root == nullptr)return nullptr;Node* copynode = new Node(root->_key);copynode->_left = Copy(root->_left);copynode->_right = Copy(root->_right);return copynode;}

析构函数：

和拷贝构造一样，析构函数通过调用子函数的实现，这里依然用后序遍历来进行删除操作.

public:~BSTree(){Destory(_root);}
private:void Destory(Node*& root){if (root == nullptr)return;return Destory(root->_left);return Destory(root->_right);delete root;root = nullptr;}

赋值操作：

采用现代写法直接进行交换

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

3、中序遍历打印：

public:void InOrder(){_InOrder(_root);cout << endl;}
private:void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << (root->_key) << " ";_InOrder(root->_right);}

4、插入操作：

循环实现：

思路：

首先考虑有可能为空树的情况，所以先判断是否为空树，如果是就直接new

如果不是空树，那么就定义两个指针一个cur遍历这个树，另一个为parent，指向cur的父节点

接着循环遍历如果cur->key小于要插入的key那么就往右找，如果cur->key大于要插入的key那么就往左找，如果相等就返回false，不能插入相等节点。

找到之后对cur进行new，接着判断cur是parent的左孩子还是右孩子，最后链接即可。

	bool Insert(const K& key){if (_root == nullptr){_root = new Node(key);return true;}Node* parent = nullptr;Node* cur = _root;while (cur){//这个if是找到nullptr的位置if (cur->_key < key){parent = cur;cur = cur->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}else{return false;}}//找到之后将这个key链接到树中//cur->_key = key;cur = new Node(key);if (parent->_key < key){parent->_right = cur;}else{parent->_left = cur;}return true;}

递归实现：

思路：

在传参数的时候传Node* root的引用，这样在下面递归的时候root就是上一层root的指向左孩子的指针或者是指向右孩子的指针，这样就可以直接改变指向的节点值。

最开始是判断root节点是否为空，这部分和循环实现是一样的，

接着判断key若比root的key大就往右边递归，若比root的key小就往左边递归，下面递归后，root是上一层root的指向左孩子的指针或者是指向右孩子的指针，这样判断发现root的左孩子或者右孩子为空，这样对root的左边的指针或者右边的指针的别名进行赋值就链接上了。

public:bool InsertR(const K& key){return _InsertR(_root, key);}
private: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;}}

5、查找：

循环实现：

定义一个cur从根节点开始遍历，和上面差不多。

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

递归实现：

和上面大差不差，在最前面加上判空返回，接着如果待查找key大于此时cur的key，那么就向右递归走，如果小于就向左递归走。

	
public:bool FindR(const K& key){return _FindR(_root, key);}
private: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;}}

6、删除操作：

循环实现：

思路：

删除操作需要cur从root开始寻找待删除的，找到后会有三种情况，

1、待删除的节点左边是空，

2、右边是空，

3、或者两边都不是空，

如果两边都是空可以看做左边是空或者右边是空，就不需要考虑这种情况了，

如果是左边为空，那么在这个if里面，在进行判断，毕竟可能是根节点，此时parent就是nullptr，如果不是就判断cur在parent的左边还是右边，在左边就把parent的左指针指向cur的右孩子，在右边就把parent的右指针指向cur的右孩子。

 

如果是右边为空和左边思路是一样的。

 

如果是两边都不为空，就比较麻烦了，不能够直接删除，这样的话二叉树的结构就会被破坏了，所以需要将待删除节点的左子树的最大节点或者右子树的最小节点和待删除节点交换，之后再删除待删除的节点，这样就不会破坏二叉树的结构了。

 

下面在实现的时候采用待删除的左边的最大节点和待删除节点交换，交换后依然要判断此时左边最大是在父节点的左边还是右边，最后记得将左边最大的赋值个cur，毕竟最后是delete cur的。

	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//cur->key == key就是找到了删除的位置{//左边为空if (cur->_left == nullptr){if (cur == _root){_root = cur->_+right;}else{//在判断此时的cur在parent的左边还是右边if (parent->_right == cur){parent->_right = cur->_right;}else//cur在parent的左边{parent->_left = cur->_right;}}}//右边为空else if (cur->_right == nullptr){if (cur == _root){_root = cur->_left;}else{//在判断此时的cur在parent的左边还是右边if (parent->_right == cur){parent->_right = cur->_left;}else//cur在parent的左边{parent->_left = cur->_left;}}}else//左右都不为空{parent = cur;Node* leftMax = cur->_left;//找到最左边的最大节点while (leftMax->_right){parent = leftMax;leftMax = leftMax->_right;}//找到后和待删除节点交换swap(leftMax->_key, cur->_key);if (parent->_left == leftMax){parent->_left = leftMax->_left;}else{parent->_right = leftMax->_left;}cur = leftMax;}delete cur;return true;}}return false;}

递归实现：

在形参中也传Node* root的引用，这样后面直接修改指针就可以了。

首先，在递归最开始如果碰到空就返回false，没找到，接着总体思路是差不多的，

先找key的值，如果找的key比此时root大就往右边递归，小就往左边递归，找到了之后在删除之前保存root的值，这样的话才在后面可以直接删除，不然的话在后面就找不到了，

依然是上面的那几种情况，这里就不用父节点了，有引用直接修改指向就可以了。

public:bool EraseR(const K& key){return _EraseR(_root, key); }
private:bool _EraseR(Node*& root, const K& key){//在递归中如果没找到就返回falseif (root == nullptr)return false;//找key的值if (root->_key < key){return _EraseR(root->_right, key);}else if (root->_key > key){return _EraseR(root->_left, key);}else//找到了{//找到了之后就进行交换删除//在删除之前保存root的值，这样的话才在后面可以直接删除，不然的话在后面就找不到了Node* del = root;//依然是3种情况//1、左边为空//2、右边为空//3、左右都不为空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);return _EraseR(root->_left, key);}delete del;return true;}}

三、二叉树的应用：

1. K模型：K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到的值。
比如：给一个单词word，判断该单词是否拼写正确，具体方式如下：
以词库中所有单词集合中的每个单词作为key，构建一棵二叉搜索树
在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。
2. KV模型：每一个关键码key，都有与之对应的值Value，即<Key, Value>的键值对。该种方
式在现实生活中非常常见：
比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英
文单词与其对应的中文<word, chinese>就构成一种键值对；
再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出
现次数就是<word, count>就构成一种键值对。