目录
1.二叉树的概念
二叉搜索树也叫二叉排序数（因为按照中序遍历是有序的），对于非空二叉树满足以下性质
a.非空左子树的所有键值（key）都小于根节点的键值；b.非空右子树的所有健值都大于根节点的键值c.根节点的左右子树都是二叉搜索树。如图就是一颗二叉搜索树
2.二叉搜索树的操作
2.1二叉搜索树的结构
a.构建二叉搜索树需要定义一个struct BSTNode 节点信息，节点中包括val值，右子树节点地址，左子树节点地址。并完成构造函数b.构建二叉搜索树，还需要树本体，里面存储root根节点信息，并包装各种接口实现对其的增删查改管理。
template<class K>
struct BSTNode
{
BSTNode(const K& key):_key(key):_left(nullptr):_right(nullptr)
{}
K _key;
BSTNode<K>* _left;
BSTNode<K>* _right;
};
template<class K>
class BSTree
{
typedef BSTNode<K> Node;
public:
//接口实现
private:
Node* _root=nullptr;
};
2.2实现节点的查找（find）
find实现可分为以下步骤：①比我小，那么迭代到左节点寻找，如果比我大，那么迭代到右节点寻找。②如果在cur为空前，都没找到，那么就没有此节点。
bool find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (key > cur->_key)
cur = cur->right;
else if (key < cur->_key)
cur = cur->left;
else
return false;
}
return true;
}2.3实现增加节点（insert）
insert的实现可分为以下步骤：①如果二叉树为空（头节点为空），直接将new的新节点赋值给_root即可②如果为非空树，那么先find找到位置（如果存在），用双指针法找，当前驱指针为空时，后继节就是我们要插入节点的父节点。
bool insert(const K& key)
{
if (_root == nullptr)
{
_root = new Node(key);
return true;
}
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
{
return false;
}
}
if (key > prev->_key)
{
prev->_right = new Node(key);
}else
{
prev->_left = new Node(key);
}
return true;
}2.4实现删除节点（erase）
erase的实现比较复杂，需要考虑一下几点：通过find找到要删的节点（如果有），①如果要删除的节点左子树为空树，那么将其右树的节点代替其位置与父建立连接。②如果要删除的节点右树为空树，那么将其左树代替其位置与父建立连接。③如果左右都无子树，且有父节点，那么可复用上述①②。④如果左无子树，且无父节点，那么直接将_root置为其右树节点，同样如果无右子树，且无父节点，那么直接将_root置为其左子树节点，如果左右无子树，且无父节点，可复用。⑤如果左树与右数都不为空，那么用将其置换为左树的最右节点或者右树的最左节点，然后删除被置换的节点，注意要继承被删除节点的左子树或者右子树⑥注意在完成第⑤步骤时，可能左树的最右节点就是左树的跟（因为左树没有右子树），同理，可能右树的最左节点就是右树的跟（因为右树没有左子树）。
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 //找到了要删除的erase节点,此时cur是我们要删除的节点，prev是其父节点
{
if (cur->_left == nullptr)
{
if (prev == nullptr)
{
_root = cur->_right;
delete cur;
}
else
{
if (prev->_left == cur)
{
prev->_left = cur->_right;
}
else if (prev->_right == cur)
{
prev->_right = cur->_right;
}
delete cur;
}
}
else if (cur->_right == nullptr)
{
if (prev == nullptr)
{
_root = cur->_left;
delete cur;
}
else
{
if (prev->_left == cur)
{
prev->_left = cur->_left;
}
else if (prev->_right == cur)
{
prev->_right = cur->_left;
}
delete cur;
}
}
else if (cur->_left != nullptr && cur->_right != nullptr)
{
Node* right2left = cur->_right;
Node* newprev = cur;
while (right2left->_left)
{
newprev = right2left;
right2left = right2left->_left;
}
swap(cur->_key, right2left->_key);
if (newprev->_left == right2left)
{
newprev->_left = right2left->_right;
}
else if (newprev->_right == right2left)
{
newprev->_right = right2left->_right;
}
delete right2left;
}
return true;
}
}
return false;
}2.5析构函数
二叉树的析构函数，可以利用函数递归到底层，再逐步删除节点利用后序遍历可以保证跟节点最后delete。
~BSTree() // 析构函数，利用函数递归进行析构
{
destroy_bst(_root);
}
void destroy_bst(Node* root)
{
if (root == nullptr) return;
destroy_bst(root->_left);
destroy_bst(root->_right);
delete root;
}2.6二叉搜索树的完整实现
#include<iostream>
using namespace std;
template<class K>
struct BSTNode
{
BSTNode(const K& key):_key(key),_left(nullptr),_right(nullptr)
{}
K _key;
BSTNode<K>* _left;
BSTNode<K>* _right;
};
template<class K>
class BSTree
{
typedef BSTNode<K> Node;
public:
//接口实现
~BSTree() // 析构函数，利用函数递归进行析构
{
destroy_bst(_root);
}
void destroy_bst(Node* root)
{
if (root == nullptr) return;
destroy_bst(root->_left);
destroy_bst(root->_right);
delete root;
}
bool find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (key > cur->_key)
cur = cur->right;
else if (key < cur->_key)
cur = cur->left;
else
return false;
}
return true;
}
bool insert(const K& key)
{
if (_root == nullptr)
{
_root = new Node(key);
return true;
}
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
{
return false;
}
}
if (key > prev->_key)
{
prev->_right = new Node(key);
}else
{
prev->_left = new Node(key);
}
return true;
}
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 //找到了要删除的erase节点,此时cur是我们要删除的节点，prev是其父节点
{
if (cur->_left == nullptr)
{
if (prev == nullptr)
{
_root = cur->_right;
delete cur;
}
else
{
if (prev->_left == cur)
{
prev->_left = cur->_right;
}
else if (prev->_right == cur)
{
prev->_right = cur->_right;
}
delete cur;
}
}
else if (cur->_right == nullptr)
{
if (prev == nullptr)
{
_root = cur->_left;
delete cur;
}
else
{
if (prev->_left == cur)
{
prev->_left = cur->_left;
}
else if (prev->_right == cur)
{
prev->_right = cur->_left;
}
delete cur;
}
}
else if (cur->_left != nullptr && cur->_right != nullptr)
{
Node* right2left = cur->_right;
Node* newprev = cur;
while (right2left->_left)
{
newprev = right2left;
right2left = right2left->_left;
}
swap(cur->_key, right2left->_key);
if (newprev->_left == right2left)
{
newprev->_left = right2left->_right;
}
else if (newprev->_right == right2left)
{
newprev->_right = right2left->_right;
}
delete right2left;
}
return true;
}
}
return false;
}
void _InOrder(Node* root)
{
if (root == nullptr) return;
_InOrder(root->_left);
cout << root->_key << " ";
_InOrder(root->_right);
}
void InOrder()
{
_InOrder(_root);
cout << endl;
}
private:
Node* _root=nullptr;
};3.二叉搜索树的应用
3.1 K模型
即二叉搜索树的节点中只存储key一个关键码。代码就是我们上述实现的普通二叉树。
它应用在查找一个key在不在节点中，例如门禁系统：我们或是通过人脸识别，或是通过RFID射频识别技术获得一个关键码key，如果find找到在BSTree中，那么就识别成功，否则识别失败。他的速度非常快，O（log N），意味着13亿人，最多只需要31次就能找到具体的一个人。
3.2KV模型
即二叉搜索树的节点中除了key，还存储了val，通过key可以通过find映射到val。它的代码实现如下，与K模型非常相似。（它的find，erase和insert都是通过key实现的）
template<class K,class V>
struct BSTNode //binary search node
{
BSTNode(const K& key,const V& val )
:_key(key),_left(nullptr),_right(nullptr),_val(val)
{}
BSTNode<K,V>* _left;
BSTNode<K,V>* _right;
K _key;
V _val;
};
template<class K,class V>
class BSTree
{
typedef BSTNode<K,V> Node;
public:
bool insert(const K& key,const V& val)
{
if (_root == nullptr)
{
_root = new Node(key,val);
}
Node* cur = _root;
Node* prev = nullptr;
while (cur)
{
if (cur->_key > key)
{
prev = cur;
cur = cur->_left;
}
else if (cur->_key < key)
{
prev = cur;
cur = cur->_right;
}
else
{
return false;
}
}
if (key < prev->_key)
prev->_left = new Node(key,val);
else
prev->_right = new Node(key,val);
return true;
}
void _InOrder(Node* root) //中序遍历
{
if (root == nullptr)
return;
_InOrder(root->_left);
cout << root->_key << "->"<<root->_val<<" ";
_InOrder(root->_right);
}
void InOrder()
{
_InOrder(_root);
}
Node* find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (key > cur->_key)
cur = cur->_right;
else if (key < cur->_key)
cur = cur->_left;
else
return cur;
}
return nullptr;
}
bool erase(const K& key)
{
Node* prev = nullptr;
Node* cur = _root;
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;
delete cur;
}
else
{
if (prev->_left == cur)
prev->_left = cur->_right;
else if (prev->_right == cur)
prev->_right = cur->_right;
delete cur;
}
}
else if (cur->_right == nullptr)
{
if (cur == _root)
{
_root = cur->_left;
delete cur;
}else
{
if (prev->_left == cur)
prev->_left = cur->_left;
else if (prev->_right == cur)
prev->_right = cur->_left;
delete cur;
cur = nullptr;
}
}
else
{
//需要考虑特殊情况，当leftmax的右为空时
Node* prev_leftmax = cur;
Node* leftmax = cur->_left;
while (leftmax->_right)
{
prev_leftmax = leftmax;
leftmax = leftmax->_right;
}
cur->_key = leftmax->_key;
if (prev_leftmax->_left == leftmax)
prev_leftmax->_left = leftmax->_left;
else
prev_leftmax->_right = leftmax->_left;
delete leftmax;
leftmax = nullptr;
}
return true;
}
}
if (cur == nullptr)
return false;
}
public:
Node* _root = nullptr;
};
4.二叉搜索树的性能分析
值得注意的是，一组数据，通过不同顺序输入所构建的二叉搜索树不同。
如果构建的是一颗完全二叉树，或者接近完全二叉树，那么其查找的效率就很高，O（logN）；
如果输入的数据是有序的，那么构建的二叉树就会退化为单支二叉树，那么效率就会降低，接近O（N）
后续我们学习了AVL树和红黑树就可以解决这个问题，实现一颗左右接近平衡的二叉树
标签：right,cur,二叉,二叉树,key,left,prev,root,进阶 From： https://blog.csdn.net/klausur31/article/details/143457150