二叉搜索树的(查找、插入、删除)

一、二叉搜索树的概念

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

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

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

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

下图就是一个二叉搜索树：

二、二叉树的定义

template<class K>
struct BSTreeNode
{BSTreeNode<K>* _right;BSTreeNode<K>* _left;K _key;BSTreeNode(const K& key = K()):_right(nullptr),_left(nullptr),_key(key){}
};template<class K>
class BSTree
{typedef BSTreeNode<K> Node;
public:bool find(const K& key){}//查找bool insert(const K& key){}//插入 bool erase(const K& key){}//删除
private：Node* _root;
};

三、二叉搜索树的查找节点

非递归写法：

如果root为空，那么查找失败，没有要查找的节点；如果root不为空，比较root->key和要查找的值，如果要查找的值大于root->key，就到右子树接着找，反之，到左子树接着找。找到返回true，没有找到返回false。

    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 true;}}return false;}

递归写法：

查找思想还是和非递归一样的，如果root为空，返回false，如果root->key大于要找的值，那么递归到左子树去找（转换成一个子问题），反之，递归到右子树去找。

    bool findR(const K& key){return _findR(_root, key);}bool _findR(Node* root, const K& key){if (root == nullptr)return false;if (root->_key == key){return true;}else if(root->_key < key){return _findR(root->_right, key);}else{return _findR(root->_left, key);}}

四、二叉搜索树的插入节点

非递归写法：

要插入一个数据，首先得找到插入的位置，所以插入分为两大步：

1、找到要插入的位置

如果树中存在一个节点的key与要插入的数相同，则不会插入。找位置的时候要同时有一个指针记录父节点，走到空就结束

2、插入数据

判断插入的数据比父节点大还是小，如果小则插在左边，反之则插在右边

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

递归写法：

    bool insertR(const K& key){return _insertR(_root, key);}//这里要传引用，我们就不需要找父节点了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;}}

五、二叉搜索树的删除节点

删除节点大致可分为三种情况：

1、要删除节点左右都为空；

2、要删除节点左为空或右为空；

3、要删除节点左右都不为空。

第一点和第二点又可以看成一点。

要注意特殊情况：要删除的节点是根节点。

非递归写法：

    bool erase(const K& key){Node* cur = _root;Node* parent = cur;while (cur){if (key > cur->_key){parent = cur;cur = cur->_right;}else if (key < cur->_key){parent = cur;cur = cur->_left;}//找到要被删的节点了else{//1、要删除的这个节点是叶子节点或度为1（可直接删除）if (cur->_left == nullptr){if (cur == _root){_root = cur->_right;}else{if (parent->_right == cur){parent->_right = cur->_right;}else{parent->_left = cur->_right;}}}else if(cur->_right == nullptr){if (cur == _root){_root = cur->_left;}else{if (parent->_right = cur){parent->_right = cur->_left;}else{parent->_left = cur->_left;}}}//2、要删除的这个节点度为2（替换法）else{//找左树中的最大值或右树中的最小值与被删节点交换，再删除//找左树中的最大值Node* leftMax = cur->_left;Node* PLeftMax = cur;while (leftMax->_right){PLeftMax = leftMax;leftMax = leftMax->_right;}swap(cur->_key, leftMax->_key);//交换值//删除leftMaxif (PLeftMax->_right == leftMax){if (leftMax->_right == nullptr){PLeftMax->_right = leftMax->_left;}else{PLeftMax->_right = leftMax->_right;}}if (PLeftMax->_left == leftMax){if (leftMax->_right == nullptr){PLeftMax->_left = leftMax->_left;}else{PLeftMax->_left = leftMax->_right;}}cur = leftMax;}delete cur;return true;}}return false;}

递归写法：

    bool eraseR(const K& key){return _eraseR(_root, key);}bool _eraseR(Node*& root, const K& key){if (root == nullptr)return false;if (root->_key < key){return _eraseR(root->_right, key);}else if (root->_key > key){return _eraseR(root->_left, key);}else{Node* del = root;//找到了被删除节点//1、左为空或右为空或左右都为空if (root->_left == nullptr){root = root->_right;}else if (root->_right == nullptr){root = root->_left;}//2、左右都不为空else{//左树找最大值Node* LeftMax = root->_left;while (LeftMax->_right){LeftMax = LeftMax->_right;}swap(root->_key, LeftMax->_key);//删除LeftMax节点return _eraseR(root->_left, key);}delete del;return true;}}

六、二叉搜索树的应用

1、K模型（也就是我们后面学是set）：K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到的值。

2、KV模型（也就是我们后面学是map）：每一个关键码key，都有与之对应的值Value，即<Key, Value>的键值对。

七、二叉搜索树的实现

template<class K>
struct BSTreeNode
{BSTreeNode<K>* _right;BSTreeNode<K>* _left;K _key;BSTreeNode(const K& key = K()):_right(nullptr),_left(nullptr),_key(key){}
};template<class K>
class BSTree
{typedef BSTreeNode<K> Node;
public:BSTree():_root(nullptr){}BSTree(const BSTree<K>& tree){_root = Copy(tree._root);}BSTree<K>& operator=(BSTree<K> tmp){swap(_root, tmp._root);return *this;}~BSTree(){Destory(_root);}bool insert(const K& key){if (_root == nullptr){_root = new Node(key);}else{Node* cur = _root;Node* parent = cur;while (cur){if (key > cur->_key){parent = cur;cur = cur->_right;}else if (key < cur->_key){parent = cur;cur = cur->_left;}else{return false;}}if (key > parent->_key){parent->_right = new Node(key);}else{parent->_left = new Node(key);}}return true;}void InOrder(){_InOrder(_root);cout << endl;}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 true;}}return false;}bool erase(const K& key){Node* cur = _root;Node* parent = cur;while (cur){if (key > cur->_key){parent = cur;cur = cur->_right;}else if (key < cur->_key){parent = cur;cur = cur->_left;}//找到要被删的节点了else{//1、要删除的这个节点是叶子节点或度为1（可直接删除）if (cur->_left == nullptr){if (cur == _root){_root = cur->_right;}else{if (parent->_right == cur){parent->_right = cur->_right;}else{parent->_left = cur->_right;}}}else if(cur->_right == nullptr){if (cur == _root){_root = cur->_left;}else{if (parent->_right = cur){parent->_right = cur->_left;}else{parent->_left = cur->_left;}}}//2、要删除的这个节点度为2（替换法）else{//找左树中的最大值或右树中的最小值与被删节点交换，再删除//找左树中的最大值Node* leftMax = cur->_left;Node* PLeftMax = cur;while (leftMax->_right){PLeftMax = leftMax;leftMax = leftMax->_right;}swap(cur->_key, leftMax->_key);//交换值//删除leftMaxif (PLeftMax->_right == leftMax){if (leftMax->_right == nullptr){PLeftMax->_right = leftMax->_left;}else{PLeftMax->_right = leftMax->_right;}}if (PLeftMax->_left == leftMax){if (leftMax->_right == nullptr){PLeftMax->_left = leftMax->_left;}else{PLeftMax->_left = leftMax->_right;}}cur = leftMax;}delete cur;return true;}}return false;}//-----------------------------------递归写法---------------------------------------bool findR(const K& key){return _findR(_root, key);}bool insertR(const K& key){return _insertR(_root, key);}bool eraseR(const K& key){return _eraseR(_root, key);}private:bool _eraseR(Node*& root, const K& key){if (root == nullptr)return false;if (root->_key < key){return _eraseR(root->_right, key);}else if (root->_key > key){return _eraseR(root->_left, key);}else{Node* del = root;//找到了被删除节点//1、左为空或右为空或左右都为空if (root->_left == nullptr){root = root->_right;}else if (root->_right == nullptr){root = root->_left;}//2、左右都不为空else{//左树找最大值Node* LeftMax = root->_left;while (LeftMax->_right){LeftMax = LeftMax->_right;}swap(root->_key, LeftMax->_key);//删除LeftMax节点return _eraseR(root->_left, key);}delete del;return true;}}Node* Copy(Node* root){if (root == nullptr)return nullptr;Node* Croot = new Node(root->_key);Croot->_left = Copy(root->_left);Croot->_right = Copy(root->_right);return Croot;}void Destory(Node*& root){if (root == nullptr){return;}/*if (root->_left == nullptr && root->_right == nullptr){delete root;root = nullptr;return;}*/Destory(root->_left);Destory(root->_right);delete root;root = nullptr;}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;}}bool _findR(Node* root, const K& key){if (root == nullptr)return false;if (root->_key == key){return true;}else if(root->_key < key){return _findR(root->_right, key);}else{return _findR(root->_left, key);}}void _InOrder(Node* root){//中序if (root == nullptr){return;}_InOrder(root->_left);cout << root->_key << " ";_InOrder(root->_right);}private:Node* _root;
};