数据结构-考研难点代码突破（C++实现树型查找-二叉搜索树（二叉排序树））

1.二叉搜索树基本操作

二叉排序树是具有下列特性的二叉树：

1. 若左子树非空，则左子树上所有结点的值均小于根结点的值。
2. 若右子树非空，则右子树上所有结点的值均大于根结点的值。
3. 左、右子树也分别是一棵二叉排序树

根据二叉排序树的定义，左子树结点值< 根结点值< 右子树结点值。
所以对二叉排序树进行中序遍历，可以得到一个递增的有序序列。

二叉排序树的搜索：

1. 从根结点开始，沿某个分支逐层向下比较的过程。
2. 若二叉排序树非空，先将给定值与根结点的关键字比较，若相等，则查找成功
3. 若不等,如果小于根结点的关键字，则在根结点的左子树上查找，否则在根结点的右子树上查找。

这个过程可以通过递归或者非递归实现实现

二叉排序树的插入：

1. 若原二叉排序树为空，则直接插入结点
2. 若关键字k小于根结点值，则插入到左子树，若关键字k大于根结点值，则插入到右子树。

插入的结点一定是一个新添加的叶结点，且是查找失败时的查找路径上访问的最后一个结点的左孩子或右孩子.

二叉排序树的删除

在二叉排序树中删除一个结点时，不能把以该结点为根的子树上的结点都删除，必须先把被删除结点从存储二叉排序树的链表上摘下，将因删除结点而断开的二叉链表重新链接起来，同时确保二叉排序树的性质不会丢失。删除操作的实现过程按3种情况来处理

1. 若被删除结点z是叶结点，则直接删除，不会破坏二叉排序树的性质

2. 若结点z只有一棵左子树或右子树，则让z的子树成为z父结点的子树，替代z的位置

3. 若结点z有左、右两棵子树，则令z的直接后继（或直接前驱）替代z，然后从二叉排序树中删去这个直接后继（或直接前驱），这样就转换成了第一或第二种情况。可以使用递归解决这个问题。

   直接后继：节点右子树中最左节点（右子树最小节点）

   删除流程图：具体看代码流程
   

二叉搜索树的效率分析

二叉排序树的查找效率，主要取决于树的高度。

1. 若二叉排序树的左、右子树的高度之差的绝对值不超过1（这样的二叉排序树称为平衡二叉树）它的平均查找长度为O(logN)

2. 若二叉排序树是一个只有右(左)孩子的单支树(类似于有序的单链表)，则其平均查找长度为O(N)

a图的平均搜索成功长度ASL：类似折半查找（1x1 + 2x2+……h×2^h-1) ）（每层的节点不一定放满，需要针对题目灵活处理）
(1×1+2×2+3×4+4×3)÷10=2.9

b图的平均搜索成功长度ASL：(1+10)/2=5.5
因为此时搜索二叉树由树型退化为线型，平均搜索长度为（n+1）/2

二叉排序树与二分查找相似。就平均时间性能而言，二叉排序树上的查找和二分查找差不多。

但二分查找的判定树唯一，而二叉排序树的查找不唯一，相同的关键字其插入顺序不同可能生成不同的二叉排序树。

二叉排序树与二分搜索：

1. 二叉排序树无须移动结点，只需修改指针即可完成插入和删除操作， 平均执行时间为O(logN)
2. 二分查找的对象是有序顺序表，若有插入和删除结点的操作，所花的代价是O(n)。
3. 当有序表是静态查找表时，宜用顺序表作为其存储结构，采用二分查找实现其查找操作；若有序表是动态查找表，则应选择二叉排序树作为其逻辑结构.

2. C++实现

// 二叉搜索树头文件实现
#include <iostream>
#include <vector>
#include <algorithm>struct TreeNode
{int _val;TreeNode *_left;TreeNode *_right;TreeNode(int val) : _val(val), _left(nullptr), _right(nullptr) {}
};class SearchTree
{
private:TreeNode *root = nullptr;/*** @brief 在二叉搜索树中查找节点值为val的节点** @param val 查找节点的值* @param node 如果找到了这个节点，node就是这个节点的地址，否则为null* @param part part这个节点的父亲，如果这个节点为null,这个参数输出null*/void _find(int val, TreeNode *&node, TreeNode *&part){TreeNode *ptr = root;TreeNode *prev = nullptr;while (ptr != nullptr){if (ptr->_val == val){node = ptr;break;}else if (ptr->_val > val){prev = ptr;ptr = ptr->_left;}else{prev = ptr;ptr = ptr->_right;}}node = ptr;part = prev;}bool _erase(int val, TreeNode *&node){if (node == nullptr){return false;}else{if (node->_val > val){_erase(val, node->_left);}else if (node->_val < val){_erase(val, node->_right);}else{if (node->_left == nullptr){TreeNode *del = node;node = node->_right;delete del;}else if (node->_right == nullptr){TreeNode *del = node;node = node->_left;delete del;}else{// 找要删除节点的后继TreeNode *right_min_node = node->_right;while (right_min_node->_left != nullptr){right_min_node = right_min_node->_left;}// 记录right_min_node这个节点的值，吧这个节点的值和node节点交换，在删除right_min_node这个节点即可// right_min_node这个节点的左子树一定为空，在上面顶点流程会处理int tmp = right_min_node->_val;_erase(tmp, node->_right);node->_val = tmp;}}return true;}}// 判断一棵树是否是二叉搜索树,检查每个节点是否满足节点值的取值范围bool _isSearchTree(TreeNode *node, int min, int max){if (node == nullptr)return true;if (node->_val < min || node->_val > max){return false;}return _isSearchTree(node->_left, min, node->_val - 1) && _isSearchTree(node->_right, node->_val + 1, max);}void _display_inorder(TreeNode *node){if (node == nullptr)return;_display_inorder(node->_left);std::cout << node->_val << " ";_display_inorder(node->_right);}int _max(){TreeNode *node = root;while (node->_right != nullptr){node = node->_right;}return node->_val;}int _min(){TreeNode *node = root;while (node->_left != nullptr){node = node->_left;}return node->_val;}public:SearchTree() = default;SearchTree(const std::vector<int> &buff){for (int i = 0; i < buff.size(); i++){insert(buff[i]);}}// 不允许重复插入相同的值bool insert(int val){if (root == nullptr){root = new TreeNode(val);return true;}else{TreeNode *pos = nullptr;TreeNode *prev = nullptr;_find(val, pos, prev);if (pos != nullptr){// 之前插入过，值重复return false;}else{// pos==nullptr;if (prev->_val > val){prev->_left = new TreeNode(val);}else{prev->_right = new TreeNode(val);}return true;}}}// 查找节点值为val的节点bool find(int val){TreeNode *node;TreeNode *part;_find(val, node, part);return node != nullptr;}// 删除搜索二叉树节点bool erase(int val){return _erase(val, root);}// 判断这颗树是否为二叉搜索树bool isSearchTree(){return _isSearchTree(root, _min(), _max());}// 中序遍历二叉搜索树void inorder(){_display_inorder(root);std::cout << "\n";}
};

测试代码：

#include "SearchTree.h"
#include <time.h>using namespace std;#define TIMES 10int main(int argc, char const *argv[])
{srand((unsigned int)time(0));// vector<int> ret = {1, 2, 3};vector<int> ret;for (int i = 0; i < TIMES; i++){ret.push_back(rand() % 100);}SearchTree tree(ret);tree.inorder();tree.insert(40);tree.inorder();cout << tree.isSearchTree() << endl;tree.insert(1);tree.erase(40);tree.inorder();cout << tree.isSearchTree() << endl;return 0;
}