专题讨论2：树与查找

在讨论前先回顾一下定义：

 

BST树的定义

二叉搜索树是一种特殊的二叉树，对于树中的任意一个节点：

若它存在左子树，那么左子树中所有节点的值都小于该节点的值。

若它存在右子树，那么右子树中所有节点的值都大于该节点的值。

它的左、右子树也分别是二叉搜索树。

总结就是：左＜根＜右

特性

有序性：二叉搜索树对节点值的大小关系有严格规定，这使得它天然具备了一定的有序性。

例如，对二叉搜索树进行中序遍历，会得到一个升序排列的节点值序列。

查找高效性：基于其节点值的大小关系特性，在二叉搜索树中查找一个节点时，平均情况下时间复杂度为，其中 n 是树中节点的数量。这是因为每次比较都能排除大约一半的搜索空间，类似于二分查找。

那既然回顾好了相关概念我们就可以进入正题了。如何用代码实现BST树上的查找、添加与删除呢？

基本思路

查找：从根节点开始，将目标值与当前节点值比较。若相等则找到；若目标值小于当前节点值，就到左子树继续查找；若大于，则到右子树查找。

添加（插入）：同样从根节点开始比较，若目标值小于当前节点值且当前节点左子树为空，就在此处插入；若左子树不为空，就继续在左子树重复该过程。若目标值大于当前节点值，操作类似，只是在右子树进行。

删除：删除节点情况相对复杂。若删除的是叶子节点，直接删除即可；若节点只有一个子树，用子树替代该节点；若节点有两个子树，通常找到其右子树中的最小节点（或左子树中的最大节点）来替代它，然后再删除该替代节点 。

自然语言描述

1、二叉搜索树的节点结构：

定义一个 TreeNode 结构体来表示二叉搜索树的节点。每个节点包含三个成员：

val：存储节点的值。

left：指向该节点左子节点的指针，初始化为 nullptr。

right：指向该节点右子节点的指针，初始化为 nullptr。

构造函数 TreeNode(int x)：用于方便地创建节点并初始化其值，同时将左右子节点指针初始化为 nullptr。

2、查找节点函数 search

1）首先判断根节点 root 是否为空，或者根节点的值是否等于要查找的值 val ，如果满足条件则直接返回当前根节点（如果为空表示没找到，如果值相等表示找到了）。

2）根节点不为空且值不等于 val 的话，就比较 val 和根节点的值 root->val ：

• 若 val 小于 root->val ，则递归地在根节点的左子树中查找，即 return search(root->left, val) 。
• 若 val 大于 root->val ，则递归地在根节点的右子树中查找，即 return search(root->right, val) 。

3、插入节点函数 insert

1）首先判断根节点 root 是否为空，如果为空，就创建一个新节点并返回，新节点的值为 val。

2）根节点不为空的话，就比较 val 和根节点的值 root->val：

• 若 val 小于 root->val ，则递归地在根节点的左子树中插入新节点，即 root->left = insert(root->left, val) 。
• 若 val 大于等于 root->val ，则递归地在根节点的右子树中插入新节点，即 root->right = insert(root->right, val) 。

3）返回插入节点后的根节点。
 

4、查找最小节点函数 findMin（为删除函数做准备）

函数 findMin 用于在给定的子树中找到值最小的节点。因为在二叉搜索树中，最左下方的节点值最小，所以通过一个循环不断向左子节点移动，直到左子节点为空，此时当前节点就是该子树中值最小的节点，然后返回该节点。

5、删除节点函数 deleteNode

1）首先判断根节点 root 是否为空，如果为空，直接返回 root 。

2）根节点不为空的话，就比较 val 和根节点 root->val ：

• 若 val 小于 root->val ，则递归地在根节点的左子树中删除值为 val 的节点，即 root->left = deleteNode(root->left, val) 。
• 若 val 大于 root->val ，则递归地在根节点的右子树中删除值为 val 的节点，即 root->right = deleteNode(root->right, val) 。
• 若 val 等于 root->val ，说明找到了要删除的节点，此时应分情况处理：
  • 如果当前节点的左子树为空，那就直接用右子节点替换当前节点。（将右子节点的指针保存到临时变量 temp 中，然后释放当前节点的内存，最后返回 temp）
  • 如果当前节点的右子树为空，那么用左子节点替换当前节点。（先将左子节点的指针保存到 temp 中，释放当前节点的内存，最后返回 temp）
  • 当左右子树都不为空时，找到右子树中的最小节点（该节点的值小于右子树所有节点的值且大于左子树中所有节点的值），用该最小节点的值替换当前节点的值，然后递归地在右子树中删除这个最小节点。

伪代码

// 定义二叉搜索树的节点结构
结构体 TreeNode:整数 val指针 left 指向 TreeNode指针 right 指向 TreeNode构造函数 TreeNode(整数 x):val = xleft = 空指针right = 空指针// 查找操作
函数 search(指针 root 指向 TreeNode, 整数 val):如果 root 为空指针 或者 root->val 等于 val:返回 root如果 val < root->val:返回 search(root->left, val)否则:返回 search(root->right, val)// 插入操作
函数 insert(指针 root 指向 TreeNode, 整数 val):如果 root 为空指针:返回 新创建的 TreeNode(val)如果 val < root->val:root->left = insert(root->left, val)否则:root->right = insert(root->right, val)返回 root// 查找最小节点
函数 findMin(指针 node 指向 TreeNode):当 node->left 不为空指针 时:node = node->left返回 node// 删除操作
函数 deleteNode(指针 root 指向 TreeNode, 整数 val):如果 root 为空指针:返回 root如果 val < root->val:root->left = deleteNode(root->left, val)否则 如果 val > root->val:root->right = deleteNode(root->right, val)否则:如果 root->left 为空指针:临时指针 temp 指向 root->right删除 root返回 temp否则 如果 root->right 为空指针:临时指针 temp 指向 root->left删除 root返回 temp临时指针 temp 指向 findMin(root->right)root->val = temp->valroot->right = deleteNode(root->right, temp->val)返回 root

代码实现

#include <iostream>
using namespace std;// 定义二叉搜索树的节点结构
struct TreeNode {int val;TreeNode* left;TreeNode* right;TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};// 查找
TreeNode* search(TreeNode* root, int val) {if (root == nullptr || root->val == val) {return root;}if (val < root->val) {return search(root->left, val);}else {return search(root->right, val);}
}// 插入
TreeNode* insert(TreeNode* root, int val) {if (root == nullptr) {return new TreeNode(val);}if (val < root->val) {root->left = insert(root->left, val);}else {root->right = insert(root->right, val);}return root;
}
// 找到最小值
TreeNode* findMin(TreeNode* node) {while (node->left != nullptr) {node = node->left;}return node;
}
// 删除
TreeNode* deleteNode(TreeNode* root, int val) {if (root == nullptr) {return root;}if (val < root->val) {root->left = deleteNode(root->left, val);}else if (val > root->val) {root->right = deleteNode(root->right, val);}else {if (root->left == nullptr) {TreeNode* temp = root->right;delete root;return temp;}else if (root->right == nullptr) {TreeNode* temp = root->left;delete root;return temp;}TreeNode* temp = findMin(root->right);root->val = temp->val;root->right = deleteNode(root->right, temp->val);}return root;
}// 中序遍历打印树
void inorder(TreeNode* root) {if (root != nullptr) {inorder(root->left);cout << root->val << " ";inorder(root->right);}
}int main() {TreeNode* root = nullptr;int num;cout << "输入一系列整数来构建二叉搜索树，输入 -1 结束输入：" << endl;while (true) {cin >> num;if (num == -1) break;root = insert(root, num);}cout << "中序遍历构建的二叉搜索树：";inorder(root);cout << endl;while (true) {cout << "请选择操作：" << endl;cout << "1. 查找节点" << endl;cout << "2. 插入节点" << endl;cout << "3. 删除节点" << endl;cout << "4. 退出程序" << endl;int choice;cin >> choice;if (choice == 1) {cout << "请输入要查找的节点值：";cin >> num;TreeNode* found = search(root, num);if (found != nullptr) {cout << "找到节点：" << found->val << endl;}else {cout << "未找到节点。" << endl;}}else if (choice == 2) {cout << "请输入要插入的节点值：";cin >> num;root = insert(root, num);cout << "插入成功，插入后的中序遍历结果：";inorder(root);cout << endl;}else if (choice == 3) {cout << "请输入要删除的节点值：";cin >> num;root = deleteNode(root, num);cout << "删除操作完成，删除后的中序遍历结果：";inorder(root);cout << endl;}else if (choice == 4) {break;}else {cout << "无效的选择，请重新输入。" << endl;}}return 0;
}

因为要实现大数据插入并可视化展现，不知道为啥我这里安装不了那个应用，于是乎我让 AI 帮我修改了一下我的代码：

修改后的代码如下

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;// 定义二叉搜索树的节点结构
struct TreeNode {int val;TreeNode* left;TreeNode* right;TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};// 查找，同时统计比较次数
int search(TreeNode* root, int val, int& comparisons) {comparisons++;if (root == nullptr || root->val == val) {return comparisons;}if (val < root->val) {return search(root->left, val, comparisons);}else {return search(root->right, val, comparisons);}
}// 插入
TreeNode* insert(TreeNode* root, int val) {if (root == nullptr) {return new TreeNode(val);}if (val < root->val) {root->left = insert(root->left, val);}else {root->right = insert(root->right, val);}return root;
}// 找到最小值
TreeNode* findMin(TreeNode* node) {while (node->left != nullptr) {node = node->left;}return node;
}// 删除
TreeNode* deleteNode(TreeNode* root, int val) {if (root == nullptr) {return root;}if (val < root->val) {root->left = deleteNode(root->left, val);}else if (val > root->val) {root->right = deleteNode(root->right, val);}else {if (root->left == nullptr) {TreeNode* temp = root->right;delete root;return temp;}else if (root->right == nullptr) {TreeNode* temp = root->left;delete root;return temp;}TreeNode* temp = findMin(root->right);root->val = temp->val;root->right = deleteNode(root->right, temp->val);}return root;
}// 计算树的高度
int treeHeight(TreeNode* root) {if (root == nullptr) {return 0;}int leftHeight = treeHeight(root->left);int rightHeight = treeHeight(root->right);return max(leftHeight, rightHeight) + 1;
}// 中序遍历打印树
void inorder(TreeNode* root) {if (root != nullptr) {inorder(root->left);cout << root->val << " ";inorder(root->right);}
}int main() {srand(static_cast<unsigned int>(time(nullptr)));TreeNode* root = nullptr;const int numToGenerate = 100000;const int rangeMin = 1;const int rangeMax = 1000000;// 生成并插入随机数构建BSTfor (int i = 0; i < numToGenerate; ++i) {int randomNum = rangeMin + rand() % (rangeMax - rangeMin + 1);root = insert(root, randomNum);}cout << "二叉搜索树构建完成，树的高度为：" << treeHeight(root) << endl;const int numToSearch = 10000;int totalComparisons = 0;for (int i = 0; i < numToSearch; ++i) {int randomSearchNum = rangeMin + rand() % (rangeMax - rangeMin + 1);int comparisons = 0;search(root, randomSearchNum, comparisons);totalComparisons += comparisons;}double averageComparisons = static_cast<double>(totalComparisons) / numToSearch;cout << "随机查找的平均比较次数为：" << averageComparisons << endl;// 计算ASL（这里简单遍历所有节点，实际可根据具体需求优化）int aslTotalComparisons = 0;int nodeCount = 0;// 辅助函数进行遍历计算，这里省略具体实现// 假设已有函数countASL遍历树计算总比较次数和节点数// countASL(root, aslTotalComparisons, nodeCount);double asl = static_cast<double>(aslTotalComparisons) / nodeCount;cout << "该树的ASL为：" << asl << endl;return 0;
}

修改的地方分别是：

1）生成随机数并构建 BST：使用<cstdlib>和<ctime>库，利用rand()函数在指定范围内生成 10 万个随机数，调用insert函数构建二叉搜索树。

2）输出树的高度：编写计算二叉搜索树高度的函数，通过递归计算左右子树高度并取较大值加 1（根节点自身占一层），在构建树后调用该函数输出高度。

3）随机查找并统计平均比较次数：生成 1 万个随机数，对每个随机数调用search函数查找，在search函数中添加计数变量统计比较次数，最后求平均比较次数。

4）计算 ASL（平均查找长度）：可以遍历所有节点，计算每个节点查找时的比较次数，再求平均值得到 ASL 。

 

 

各函数的时间复杂度和空间复杂度：

 1、insert 函数

时间复杂度：

空间复杂度：

2、search 函数

时间复杂度：

空间复杂度：

3、findMin 函数

时间复杂度：

空间复杂度：

4、deleteNode 函数

时间复杂度：

空间复杂度：

5、 inorder 函数

时间复杂度：

空间复杂度：

运行结果