搜索二叉树 Binary Search Tree（BST）

【提醒】本章内容需掌握二叉树结构的基本概念和特性，不然可能阅读起来比较费劲。

一、 概念

        什么是搜索二叉树？搜索二叉树和普通二叉树的却别是什么？

       答： 二叉搜索树又称二叉排序树，它或者是一棵空树

或者是具有以下性质的二叉树:

• 非空的左子树，树上所有节点的值都小于根节点的值
• 非空的右子树，树上所有节点的值都大于根节点的值
• 它的左右子树也分别为二叉搜索树

 搜索二叉树 最重要的特性之一：搜索二叉树 中序遍历可以得到一个有序的序列。

把文字转换成图形：下面是一颗搜索二叉树

 

下面再来看两个例子更深刻地理解什么是搜索二叉树：

 二、搜索二叉树的增删查改

1. 搜索二叉树插入节点（增）

搜索二叉树的插入分为三个步骤：

1. 从根节点开始。

2. 如果插入的值小于当前节点，移动到左子节点；如果大于，移动到右子节点。

3. 重复步骤2，直到找到一个空位置插入新值。

 以下用一个插入建树的详细图解说明：

以数值{8 ，3 ，1 ，10 ，1}为例：

【注意】：二叉搜索树中，如果插入的值已经存在，处理方式可以有几种，现阶段采用第一种：

1. 忽略重复值：简单地不插入重复值，保留原有节点。

2. 计数重复值：在每个节点中增加一个计数器，如果插入相同值则增加计数器，而不是新建节点。

3. 允许重复值：按某种规则插入，如将相同值插入到右子树。

---

2. 搜索二叉树节点的删除

        搜索二叉树阶段的删除相较于插入是要复杂一点的，需要分情况讨论。

节点的删除:

        首先查找元素是否在二叉搜索树中，如果不存在，则返回 false。

元素存在的情况，则分以下四种情况分别处理（假设要删除的结点为 N）：

1. 要删除的结点 N 左右孩子均为空。

2. 要删除的结点 N 左孩子为空，右孩子结点不为空。

3. 要删除的结点 N 右孩子为空，左孩子结点不为空。

4. 要删除的结点 N 左右孩子结点均不为空。

 结合图形举例说明删除节点时会遇到的4种情况：

 

 

为了解决以上4种情况，分别对应4种解决方案：

1.左右孩子均为空：

• 把 N 结点的父节点对应孩子指针指向空，直接删除 N 结点（情况 1 可以当成 2 或者 3 处理，效果是一样的）。

2.左孩子为空，右孩子不为空：

• 把 N 结点的父节点对应孩子指针指向 N 的右孩子，直接删除 N 结点。

3.右孩子为空，左孩子不为空：

• 把 N 结点的父节点对应孩子指针指向 N 的左孩子，直接删除 N 结点。

4.左右孩子结点均不为空：

• 无法直接删除 N 结点，因为 N 的两个孩子无处安放，只能用替换法删除。

• 找 N 左子树的值最大结点 R（最右结点）或者 N 右子树的值最小结点 R（最左结点）替代 N。

• 因为这两个结点中任意一个，放到 N 的位置，都满足二叉搜索树的规则。

• 替代 N 的意思就是 N 和 R 两个结点的值交换，转而变成删除 R 结点，R 结点符合情况 2 或情况 3，可以直接删除。

 同样结合图形可以更好的理解4总处理方式：

 

 

 3. 搜索二叉树节点的查找

        搜索二叉树的查找逻辑很简单，其实在上面插入节点，已经使用过：

查找步骤：

1. 从根节点开始。

2. 比较值：如果查找的值小于当前节点，移动到左子节点；如果大于，移动到右子节点。

3. 找到值：重复步骤2，直到找到值或访问到空节点。

 4. 搜索二叉树节点的更改

       搜索二叉树节点的修改，如果直接修改可能会破坏BST的结构，使树不再满足搜索树的性质。

        所以在BST节点的修改，应该遵循以下步骤；

修改：

1. 删除原节点：首先，删除需要修改的节点。

2. 插入新值：然后，插入修改后的新值。

三、搜索二叉树的模拟实现

下面是搜索二叉树的模拟实现：（出自鄙人，如有错误愿联系指正）【仅参考非源码】

// BST.h#include <iostream>
#include <string>
using namespace std;namespace key
{template<class K>class BSTreeNode {public:BSTreeNode<K>* _leftNode;BSTreeNode<K>* _rightNode;K _key;BSTreeNode(const K& key):_key(key), _leftNode(nullptr), _rightNode(nullptr) {}};template<class K>class BinarySearchTree{typedef BSTreeNode<K> Node;public:BinarySearchTree() :_root(nullptr){}~BinarySearchTree(){Destroy(_root);}BinarySearchTree(const BinarySearchTree<K>& tree) {_root = Copy(tree._root);}BinarySearchTree<K>& operator=(BinarySearchTree<K> tree) {swap(_root, tree._root);return *this;}//节点插入bool Insert(const K& key){if (_root == nullptr) {_root = new Node(key);return true;}Node* parent = nullptr;Node* current = _root;while (current){if (current->_key < key) {parent = current;current = current->_rightNode;}else if (current->_key > key) {parent = current;current = current->_leftNode;}else { //搜索二叉树不允许值相等return false;}}if (parent->_key > key) {parent->_leftNode = new Node(key);return true;}else if (parent->_key < key) {parent->_rightNode = new Node(key);return true;}return false;}//查找（循环版）Node* Find(const K& key){Node* curr = _root;while (curr) {if (curr->_key < key) {curr = curr->_rightNode;}else if (curr->_key > key) {curr->_leftNode;}else {return curr;}}return nullptr;}bool Erase(const K& key) {Node* parent = nullptr;Node* curr = _root;while (curr) {if (curr->_key < key){parent = curr;curr = curr->_rightNode;}else if (curr->_key > key){parent = curr;curr = curr->_leftNode;}else {//等于情况下就删除 找到了if (curr->_leftNode == nullptr) {if (curr == _root) {//如果根就是要删除的节点_root = curr->_rightNode;}else {//判断现在找到的节点 是父的左还是右if (parent->_leftNode == curr) {parent->_leftNode = curr->_rightNode;}else {parent->_rightNode = curr->_rightNode;}}}else if (curr->_rightNode == nullptr) {if (curr == _root) {//如果根就是要删除的节点_root = curr->_leftNode;}else {//判断现在找到的节点 是父的左还是右if (parent->_leftNode == curr) {parent->_leftNode = curr->_leftNode;}else {parent->_rightNode = curr->_leftNode;}}}else { //两边都有Node* leftNodeParent = curr;Node* leftMaxNode = curr->_leftNode;//找左边树最大的节点代替while (leftMaxNode->_rightNode) {leftNodeParent = leftMaxNode;leftMaxNode = leftMaxNode->_rightNode;}// 交换要删除节点和左子树最大节点的键值curr->_key = leftMaxNode->_key;// 更新父节点指针，删除左子树的最大节点if (leftNodeParent->_leftNode == leftMaxNode) {leftNodeParent->_leftNode = leftMaxNode->_leftNode;}else {leftNodeParent->_rightNode = leftMaxNode->_leftNode;}curr = leftMaxNode;}delete curr;return true;}}return false;}//查找（递归版）bool FindR(const K& key){_FindR(_root, key);}//插入节点（递归版）bool InsertR(const K& key) {return _InsertR(_root, key); }//删除节点（递归版）bool EraseR(const K& key) {return _EraseR(_root, key);}//中序遍历打印void InOrder() {_InOrder(_root);}private://递归寻找子函数bool _FindR(Node* root, const K& key) {if (root == nullptr)return false;if (root->_key > key) {return _FindR(root->_leftNode, key);}else if (root->_key < key) {return _FindR(root->_rightNode, key);}else {return true;}}//递归删除子函数bool _EraseR(Node*& root, const K& key){if (root == nullptr)return false;if (root->_key > key) {return _EraseR(root->_leftNode, key);}else if (root->_key < key) {return _EraseR(root->_rightNode, key);}else {//找到了删除Node* deleteNode = root;if (root->_leftNode == nullptr) {root = root->_rightNode;}else if (root->_rightNode == nullptr) {root = root->_leftNode;}else {//左右都有Node* leftMax = root->_leftNode;while (leftMax->_rightNode) {leftMax = leftMax->_rightNode;}swap(root->_key, leftMax->_key);return _EraseR(root->_leftNode, key);}delete deleteNode;return true;}}//递归插入子函数bool _InsertR(Node*& root, const K& key){if (root == nullptr) {root = new Node(key);return true;}if (root->_key > key) {return _InsertR(root->_leftNode, key);}else if (root->_key < key) {return _InsertR(root->_rightNode, key);}else {return false; //相同的返回false}}//中序遍历打印子函数void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_leftNode);cout << root->_key << " ";_InOrder(root->_rightNode);}void Destroy(Node* root){if (root == nullptr)return;Destroy(root->_leftNode);Destroy(root->_rightNode);delete root;root = nullptr;}Node* Copy(const Node* root){if (root == nullptr)return nullptr;Node* copyRoot = new Node(root->_key);copyRoot->_leftNode = Copy(root->_leftNode);copyRoot->_rightNode = Copy(root->_rightNode);return copyRoot;}Node* _root = nullptr;};void TestBSTree1();
}

//main.h
#include "binarysearchtree.h"
#include <iostream>namespace key {void TestBSTree1(){int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };BinarySearchTree<int> t;for (auto e : a){t.InsertR(e);}t.InOrder();cout << endl;t.Erase(4);t.InOrder();cout << endl;t.EraseR(6);t.InOrder();cout << endl;t.EraseR(7);t.InOrder();cout << endl;t.EraseR(3);t.InOrder();cout << endl;for (auto e : a){t.EraseR(e);}t.InOrder();}
}int main() 
{key::TestBSTree1();return 0;
}

程序运行结果：

1 3 4 6 7 8 10 13 14
1 3 6 7 8 10 13 14
1 3 7 8 10 13 14
1 3 8 10 13 14
1 8 10 13 14