数据结构【搜索二叉树】

搜索二叉树是STL中map和set的重要铺垫，学好搜索二叉树有助于理解map和set的特性。搜索二叉树也是一种二叉树结构，只是多了一些特定的性质。

一棵搜索二叉树可以为空树，如果不为空时，一定满足下面的性质。

若它的左子树不为空，则所有左子树上的节点都小于根节点的键值。
若它的右子树不为空，则所有的右子树上的节点都大于根节点的键值。
它的左右子树也分别为搜索二叉树。

基于先描述在组织的思想，我们可以尝试搭建一个搜索二叉树结构。

1、框架搭建

先描述具体的节点，再进行节点间的组织链接。

template<class K>
class BSTreeNode
{
public:BSTreeNode<K>* _left;BSTreeNode<K>* _right;K _key;BSTreeNode(const K& key):_left(nullptr), _right(nullptr), _key(key){}
};template<class K>
class BSTree
{typedef BSTreeNode<K> Node;
public:BSTree():_root(nullptr){}
private:Node* _root;
};

框架构造还是六个字：先描述，再组织。

2、节点插入

数据进行插入时要分情况讨论：

搜索二叉树为空时，可以直接插入；
不为空时，如果插入的键值大于根节点就去根节点的右边继续寻找空位置进行插入，如果插入的键值小于根节点就去根节点的左边寻找空位置进行插入；如果搜索二叉树种存在要插入的键值就返回false；

	bool Insert(const K& key){if (_root == nullptr){_root = new Node(key);return true;}else{//搜索二叉树不为空Node* parent = _root;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{return false;}}//判断链接在左还是链接在右cur = new Node(key);cur->_key > parent->_key ? parent->_right = cur : parent->_left = cur;return true;}}

在寻找空位置的过程中，也要同时记录当前节点的父节点位置。主要是方便进行后面的链接。

3、中序遍历

由于中序遍历需要传入当前节点的地址进行递归，这里为了方便外部的对象调用。对中序遍历进行了一次封装。在封装之后的函数内部传入_root；

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

对上述代码进行简单的测试：

#include<iostream>
using namespace std;
#include"BinarySearchTree.h"void TestBSTree()
{int arr[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };BSTree<int> bs;for (auto e : arr){bs.Insert(e);}bs.InOrder();}int main()
{TestBSTree();return 0;
}

运行结果：

4、节点删除

节点的删除比较复杂。需要分下面的情况进行分析：

要删除的节点没有子节点，可以直接进行删除，再删除之后要对它的父节点的位置进行置空操作。

如果要删除的节点只有一个子节点，同样也可以直接删除，在删除之后需要在进行判断，如果删除节点的子节点小于删除节点的父节点，那么就链接在父节点的左边；反之，就连接在右边。

如果要删除的节点左右子树都非空树，那么这时就需要进行替换删除。为了保证替换后的树形结构仍然满足搜索二叉树的性质，这时的替换要求为：只能和删除节点的左子树的最右节点或者右子树的最左节点进行替换。通常情况下使用左子树的最右节点进行替换。

上面的1和2可以归纳为一点，当删除的节点的左子树为空树时，就将删除节点的父节点链接上删除节点的右节点；反之，就将删除节点的父节点链接上删除节点的左节点。

	bool Erase(const K& key){Node* parent = _root;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{//找到了,进行删除操作//1.左子树为空if (cur->_left == nullptr){if (cur == _root){_root = _root->_right;}else{//判断删除节点的位置，进行原位置链接if (parent->_left == cur){parent->_left = cur->_right;}else{parent->_right = cur->_right;}}}//2.右子树为空else if (cur->_right == nullptr){if (cur == _root){_root = _root->_left;}else{if (parent->_left == cur){parent->_left = cur->_left;}else{parent->_right = cur->_left;}}}//3.左右子树都不为空else{Node* leftMaxParent = cur;Node* leftMax = cur->_left;//寻找左子树的最右节点 且找到它的父节点while (leftMax->_right){leftMaxParent = leftMax;leftMax = leftMax->_right;}std::swap(cur->_key, leftMax->_key);if (leftMaxParent->_left == leftMax){leftMaxParent->_left = leftMax->_left;}else{leftMaxParent->_right = leftMax->_left;}//下面统一删除cur;cur = leftMax;}delete cur;cur = nullptr;return true;}}return false;}