二叉搜索树

1.基础概念介绍

二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:

1.若它的左子树不为空，则左子树上所有节点的值都小于根节点的值

2.若它的右子树不为空，则右子树上所有节点的值都大于根节点的值

3.它的左右子树也分别为二叉搜索树

如图所示就是一颗二叉树，其先从根开始找起（一般走中序遍历），因为节点左边的值总比节点小，右边的值总比节点打，所以遍历完一遍还没有找到的话，说明这个数字不存在。

2.二叉搜索树的基本功能实现

2.1单个节点类

tmeplate<class K>
strust BSTreeNode
{BSTreeNode* _left;BSTreeNode* _right;K _key;BSTreeNode(const K& key):_left(nullptr),_rihgt(nullptr),_ket(key){}     
};

2.2BS树主体

tmepalte<class k>
class BSTree
{typedef BSTreeNode<K> Node;  //其实还是那老一套，这里的封装就相对简单多了BSTree():_root(nullptr){}private:Node* _root
};

2.3插入

bool insert(const k& key)
{if(_root == nullptr){Node* cur = new Node(kety);return true;}Node* cur = _root;Node* parent = nullptr;while(cur){if(cur->_key < key){parent = cur;cur = cur->_right;}else if{parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(key);if(parent->_key > key){parent->_left = parent;}else{parent->_right = parent;}return true;
}

2.4删除

bool Erase(const k& key)
{Node* parent = nullptr;Node* cur = _root;while(cur){if(cur->_key < key){parent = cur;cur = cur->left;}else if(cur->_key > key){parent = cur;cur = cur->right;}else{//找到准备开始删除if(cur->_left == nullptr){if(parent == nullptr){_root->cur->_right;}else {if(parent->_left == cur)parent->_left = cur->_right;elseparent->_right = cur->_right;}delete cur;}if(cur->_right == nullptr){if(parent == nullptr){_root->cur->_left;}else {if(parent->_left == cur)parent->_left = cur->_left;elseparent->_right = cur->_left;}delete cur;}if(cur->_right != nullptr && cur->_left != nullptr){Node* minParent = cur;Node* min = cur->right;while(min->left){minParent = min;min = min->left;}cur->_key = min->_key;if (minParent->_left == min)minParent->_left = min->_right;elseminParent->_right = min->_right;delete min;}return true;}}return false;
}

这棵树的重点其实就是删除功能，可以看到上图我们一共会出现这三种情况（当然这里的图画的不完全，但是大致我们可以分为3类）：

我们先来讲解一二两类：

如一二两图所示当出现这种情况时候我们优先考虑：

1.此时要删除的节点是否为根节点（根节点要是变化了需要更改）

2.删除后我们将其左结点或者右结点和其父结点相互连接，此时应该去区分是父结点的右和我相互关联还是左。

而碰到图三的情况我将讲解下这里用到的代码细节和思路：

1.其实我们遇到图三这种情况，处理方法无非是找其左端的最大值，或者右端的最小值，而这里我们采用的是寻找右端最小数值的方法（可以画图比较一下这两方法我为什么选择后者）

2.其次这里不需要考虑删除的是否为根结点的问题（因为我实际操作是不可能去删根结点的）

3.在我使用第二种方法后，其依旧需要判断一下父结点是连哪个方向（具体参考下面这张图）

2.5查找

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;
}

基本功能到这里已经实现完成了，当然这里会有一个递归的版本，但是正常情况下我们不会去使用递归的这种方法去实现，当递归深度足够大时栈容易溢出。