C++——二叉树排序树

1 二叉搜索树概念

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

• 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
• 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
• 它的左右子树也分别为二叉搜索树
• 一般情况下二叉搜索树的数据是不能重复的
  

2 二叉搜索树操作与模拟实现

完整代码K模型和KV模型代码链接
结点定义：

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

2.1 二叉搜索树的查找

a、从根开始比较，查找，比根大则往右边走查找，比根小则往左边走查找。
b、最多查找高度次，走到到空，还没找到，这个值不存在。

代码实现：

非递归版本

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

递归版本

bool _FindR(Node* root, const K& key)
{if (root == nullptr)//没找到return false;if (root->_key < key)//被查找到的值大于当前结点，去右树找return _FindR(root->_right, key);else if (root->_key > key)//被查找到的值小于当前结点，去左树找return _FindR(root->_left, key);else//找到了return true;
}

2.2 二叉搜索树的插入

插入的具体过程如下：
a. 树为空，则直接新增节点，给root指针赋值
b. 树不空，按二叉搜索树性质查找插入位置，插入新节点

代码实现：

非递归版本

bool Insert(const K& key)
{if (_root == nullptr){_root = new Node(key);return true;}Node* parent = nullptr;//记录父节点Node* cur = _root;//_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此时为nullptr//父节点parent也被记录cur = new Node(key);if (parent->_key < key)//寻找该正确的插入位置{parent->_right = cur;}else{parent->_left = cur;}return true;
}

递归版本

可以考虑再增加一个parent参数。
但下面的方法更加巧妙
下面代码传root的引用两个用处：
1、如果传进来的就是一颗空树，直接给root赋值就可以了，比较容易理解.
2、因为传的是引用，所以root也是上一步递归传入的root->right或者root->_left的别名，非常巧妙的是root = new Node(key);就等价于root->right=new Node(key);或者root->_left=new Node(key);，刚好把结点就赋值到正确的位置，省去了上面非递归方法的还需要记录父节点的步骤。

bool _InsertR(Node*& root, const K& key)//注意细节传的是root的引用
{	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//插入的值和当前结点的值相等，不需要插入，返回falsereturn false;
}

下面是插入9的代码调试，可以发现确实root和上一步root->left的地址是一样的，可见引用在C++中的作用是多么大。

2.3 二叉搜索树的删除

首先查找元素是否在二叉搜索树中，如果不存在，则返回, 否则要删除的结点可能分下面四种情况：
a. 要删除的结点无孩子结点（例如1、4、7、13）
b. 要删除的结点只有左孩子结点（例如14）
c. 要删除的结点只有右孩子结点（例如10）
d. 要删除的结点有左、右孩子结点（例如3、6、8）
看起来删除节点有4种情况，实际情况a可以与情况b或者c合并起来，因此真正的删除过程如下：

• 情况b：删除该结点，并且使该删除节点的双亲结点指向该删除节点的左孩子结点——直接删除（托孤）
• 情况c：删除该结点，并且使该删除节点的双亲结点指向该删除结点的右孩子结点——直接删除（托孤）
• 情况d：
  找被删除结点 左子树的最大 或者 右子树的最小 用它的值填补到被删除节点中(这样才能保证二叉排序树的结构不被破坏)，再来删除这个 左子树最大 或者 右子树最小结点——替换法删除。

针对情况d，下面图中，想删除8用左子树的最大或者右子树的最小
那么由于二叉排序树特殊的结构其实
左子树的最大 也就是 左子树的最右结点——从上往下遍历，第一个没有右孩子的结点——7
右子树的最小 也就是 右子树的最左结点——从上往下遍历，第一个没有左孩子的结点——10

代码实现：
提前声明：下面非递归和递归版本都用的是右子树的最小结点来进行替换删除的。
具体细节详解在下面代码注释中：一边看图一边看代码注释效果更佳！

非递归版本

bool Erase(const K& key)
{Node* parent = nullptr;//记录父节点Node* cur = _root;//_root成员变量while (cur){//能找到开始删除if (cur->_key < key){parent = cur;cur = cur->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}else//被删除目标已经找到，就存在cur里{if (cur->_left == nullptr)//被删除结点的左为空——只有右孩子{//if (parent == nullptr)//如果被删除的就是根节点if (cur == _root)//如果被删除的就是根节点{_root = cur->_right;}else{if (parent->_left == cur)//如果我是父亲结点的左孩子{parent->_left = cur->_right;}else//如果我是父亲结点的右孩子{parent->_right = cur->_right;}}delete cur;}else if (cur->_right == nullptr)//被删除结点右为空——只有左孩子{//if (parent == nullptr)//如果被删除的就是根节点if (cur == _root)//如果被删除的就是根节点{_root = cur->_left;}else{if (parent->_left == cur){parent->_left = cur->_left;}else{parent->_right = cur->_left;}}delete cur;}else//被删除的结点左右子树都不为空，替换删除{// 开始找右子树的最小节点Node* parent = cur; //细节赋值curNode* minRight = cur->_right;while (minRight->_left){parent = minRight;minRight = minRight->_left;}//运行到这里已经找到了右子树最小结点cur->_key = minRight->_key;//直接覆盖被删除结点的值，或者让右子树和被删除结点交换都可以//minRight是右子树的最左结点——一定没有左孩子//而且要特别注意：删除3和删除8结点是不一样的，一定要考虑全面if (minRight == parent->_left)//删除8结点的情况，对于10结点的处理{parent->_left = minRight->_right;}else//删除3结点的情况，对于4结点的处理{parent->_right = minRight->_right;}delete minRight;}return true;}}//找不到需要被删除的节点返回falsereturn false;
}

递归版本

bool _EraseR(Node*& root, const K& key)
{if (root == nullptr)//没有找到 或者 root一开始传入的就是一个空树{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;//记录当前结点，方便后面delete//被删除结点只有左孩子，例如14if (root->_right == nullptr){root = root->_left;//被赋值的root也是上一层递归root->_right的别名}//被删除结点只有右孩子，例如：10else if (root->_left == nullptr){root = root->_right;//被赋值的root也是上一层递归root->_left的别名}else//被删除结点有两个孩子{Node* minRight = root->_right;//找右子树的最左——最小while (minRight->_left){minRight = minRight->_left;}//让被删除结点跟最小值交换swap(root->_key, minRight->_key);// 交换完右子树还是一颗二叉排序树// 转换成在子树中去删除节点return _EraseR(root->_right, key);}delete del;return true;}
}

完整代码K模型和KV模型代码链接

3 二叉搜索树的应用（K模型、KV模型）

1. K模型：K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到的值。比如：给一个单词word，判断该单词是否拼写正确，具体方式如下：

• 以词库中所有单词集合中的每个单词作为key，构建一棵二叉搜索树
• 在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。

2. KV模型：每一个关键码key，都有与之对应的值Value，即<Key, Value>的键值对。该种方式在现实生活中非常常见：

• 比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英文单词与其对应的中文<word, chinese>就构成一种键值对；
• 再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出现次数就是<word, count>就构成一种键值对。

4 二叉搜索树的性能分析

插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。
对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多。
但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树：

最优情况下，二叉搜索树为完全二叉树(或者接近完全二叉树)，其平均比较次数为：$lo{g}_{2}N$。
最差情况下，二叉搜索树退化为单支树(或者类似单支)，其平均比较次数为：$N$。