目录😋
任务描述
相关知识
1. 二叉排序树的基本概念
2. 二叉排序树节点结构体定义
3. 创建二叉排序树
4. 判断是否为二叉排序树
5. 递归查找关键字为 6 的结点并输出查找路径
6. 删除二叉排序树中的节点
测试说明
通关代码
测试结果
任务描述
本关任务：实现二叉排序树的基本算法。
相关知识
为了完成本关任务，你需要掌握：
- 二叉排序树的基本概念
- 二叉排序树节点结构体定义
- 创建二叉排序树
- 判断是否为二叉排序树
- 递归查找关键字为 6 的结点并输出查找路径
- 删除二叉排序树中的节点
1. 二叉排序树的基本概念
二叉排序树（Binary Search Tree，也叫二叉查找树）是一种特殊的二叉树，具有以下性质：
- 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值。
- 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值。
- 它的左、右子树也分别为二叉排序树。
2. 二叉排序树节点结构体定义
在 C++ 中，首先需要定义二叉排序树节点的结构体，代码示例如下：
#include <iostream> using namespace std; // 二叉树节点结构体定义 template <typename T> struct TreeNode { T val; TreeNode<T> *left; TreeNode<T> *right; TreeNode(T x) : val(x), left(NULL), right(NULL) {} };3. 创建二叉排序树
根据给定的关键字序列创建二叉排序树的基本思路是，依次将关键字插入到二叉排序树中。插入操作的规则是从根节点开始比较，如果待插入值小于当前节点值就往左子树走，如果大于就往右子树走，直到找到合适的空位置插入。以下是创建二叉排序树的代码实现：
// 插入节点到二叉排序树的函数 template <typename T> TreeNode<T> *insert(TreeNode<T> *root, T val) { if (root == NULL) { return new TreeNode<T>(val); } if (val < root->val) { root->left = insert(root->left, val); } else { root->right = insert(root->right, val); } return root; } // 根据关键字序列创建二叉排序树 template <typename T> TreeNode<T> *createBST(vector<T> keys) { TreeNode<T> *root = NULL; for (T key : keys) { root = insert(root, key); } return root; }然后可以使用以下方式调用创建函数并输出二叉树（以括号表示法输出，这里简单实现一个先序遍历的框架用于输出，实际更完善的括号表示法输出可以处理更多格式细节）：
// 先序遍历二叉树（用于简单展示括号表示法输出结构，可完善更准确的括号表示法输出格式） template <typename T> void preorderTraversal(TreeNode<T> *root) { if (root == NULL) { return; } cout << root->val; if (root->left!= NULL || root->right!= NULL) { cout << "("; preorderTraversal(root->left); if (root->right!= NULL) { cout << ","; } preorderTraversal(root->right); cout << ")"; } } int main() { vector<int> keys = {4, 9, 0, 1, 8, 6, 3, 5, 2, 7}; TreeNode<int> *bt = createBST(keys); preorderTraversal(bt); cout << endl; return 0; }4. 判断是否为二叉排序树
要判断一棵二叉树是否为二叉排序树，可以采用中序遍历的思路，中序遍历二叉排序树得到的序列应该是有序递增的。以下是判断代码实现：
template <typename T> bool isValidBST(TreeNode<T> *root, T* prev = NULL) { if (root == NULL) return true; if (!isValidBST(root->left, prev)) return false; if (prev!= NULL && root->val <= *prev) return false; *prev = root->val; return isValidBST(root->right, prev); }可以在
main函数中调用这个函数来验证之前创建的bt是否是二叉排序树，例如：int main() { vector<int> keys = {4, 9, 0, 1, 8, 6, 3, 5, 2, 7}; TreeNode<int> *bt = createBST(keys); int prevVal = INT_MIN; bool result = isValidBST(bt, &prevVal); if (result) { cout << "是二叉排序树" << endl; } else { cout << "不是二叉排序树" << endl; } return 0; }5. 递归查找关键字为 6 的结点并输出查找路径
递归查找的思路就是按照二叉排序树的性质，根据比较值的大小决定往左子树还是右子树查找。同时可以用一个辅助数据结构（比如
vector）来记录查找路径。以下是代码实现：template <typename T> bool searchNode(TreeNode<T> *root, T target, vector<TreeNode<T>*>& path) { if (root == NULL) return false; path.push_back(root); if (root->val == target) return true; if (target < root->val) { return searchNode(root->left, target, path); } else { return searchNode(root->right, target, path); } } int main() { vector<int> keys = {4, 9, 0, 1, 8, 6, 3, 5, 2, 7}; TreeNode<int> *bt = createBST(keys); vector<TreeNode<int>*> path; bool found = searchNode(bt, 6, path); if (found) { for (TreeNode<int> *node : path) { cout << node->val << " "; } cout << endl; } return 0; }6. 删除二叉排序树中的节点
删除二叉排序树中的节点有以下几种情况：
- 情况一：要删除的节点是叶子节点（没有子节点）：直接删除该节点即可，即将其父节点指向该节点的指针置为
NULL。- 情况二：要删除的节点只有一个子节点：将其父节点指向该节点的指针指向该节点的子节点。
- 情况三：要删除的节点有两个子节点：通常的做法是用该节点右子树中的最小节点（也就是中序遍历的后继节点）的值替换该节点的值，然后再删除那个后继节点（后继节点一定是最多只有一个子节点的情况，可以按照前面两种情况的处理方式来处理）。
以下是删除节点的代码实现：
template <typename T> TreeNode<T> *minValueNode(TreeNode<T> *node) { TreeNode<T> *current = node; while (current && current->left!= NULL) { current = current->left; } return current; } template <typename T> TreeNode<T> *deleteNode(TreeNode<T> *root, T key) { if (root == NULL) return root; if (key < root->val) { root->left = deleteNode(root->left, key); } else if (key > root->val) { root->right = deleteNode(root->right, key); } else { // 情况一和二：节点是叶子节点或者只有一个子节点 if (root->left == NULL) { TreeNode<T> *temp = root->right; delete root; return temp; } else if (root->right == NULL) { TreeNode<T> *temp = root->left; delete root; return temp; } // 情况三：节点有两个子节点 TreeNode<T> *temp = minValueNode(root->right); root->val = temp->val; root->right = deleteNode(root->right, temp->val); } return root; } int main() { vector<int> keys = {4, 9, 0, 1, 8, 6, 3, 5, 2, 7}; TreeNode<int> *bt = createBST(keys); bt = deleteNode(bt, 4); bt = deleteNode(bt, 5); preorderTraversal(bt); cout << endl; return 0; }
测试说明
平台会对你编写的代码进行测试：
预期输出：
(1)创建一棵BST树: 第1步,插入4:4 第2步,插入9:4(,9) 第3步,插入0:4(0,9) 第4步,插入1:4(0(,1),9) 第5步,插入8:4(0(,1),9(8)) 第6步,插入6:4(0(,1),9(8(6))) 第7步,插入3:4(0(,1(,3)),9(8(6))) 第8步,插入5:4(0(,1(,3)),9(8(6(5)))) 第9步,插入2:4(0(,1(,3(2))),9(8(6(5)))) 第10步,插入7:4(0(,1(,3(2))),9(8(6(5,7)))) (2)输出BST:4(0(,1(,3(2))),9(8(6(5,7)))) (3)bt是一棵BST (4)关键字6的查找路径: 4 9 8 6 (5)删除操作: 原BST:4(0(,1(,3(2))),9(8(6(5,7)))) 删除节点4:3(0(,1(,2)),9(8(6(5,7)))) 删除节点5:3(0(,1(,2)),9(8(6(,7)))) (6)销毁BST
开始你的任务吧，祝你成功！
通关代码
#include <iostream>
using namespace std;
// 定义二叉排序树节点结构体
struct BSTNode {
int key; // 关键字
BSTNode *left; // 左孩子指针
BSTNode *right; // 右孩子指针
BSTNode(int val) : key(val), left(nullptr), right(nullptr) {} // 构造函数
};
// 插入节点到二叉排序树
BSTNode *insertBST(BSTNode *root, int key) {
if (root == nullptr) {
return new BSTNode(key);
}
if (key < root->key) {
root->left = insertBST(root->left, key);
} else if (key > root->key) {
root->right = insertBST(root->right, key);
}
return root;
}
// 以括号表示法输出二叉排序树
void displayBST(BSTNode *root) {
if (root != nullptr) {
cout << root->key;
if (root->left != nullptr || root->right != nullptr) {
cout << "(";
displayBST(root->left);
if (root->right != nullptr)
cout << ",";
displayBST(root->right);
cout << ")";
}
}
}
// 判断是否为二叉排序树（中序遍历验证有序性）
bool isBSTUtil(BSTNode *root, int *prev) {
if (root == nullptr)
return true;
if (!isBSTUtil(root->left, prev))
return false;
if (*prev != -1 && root->key <= *prev)
return false;
*prev = root->key;
return isBSTUtil(root->right, prev);
}
bool isBST(BSTNode *root) {
int prev = -1;
return isBSTUtil(root, &prev);
}
// 查找关键字为key的节点并输出查找路径（递归）
void searchBST(BSTNode *root, int key, int path[], int depth) {
if (root == nullptr)
return;
path[depth] = root->key;
if (root->key == key) {
cout << "(4)关键字" << key << "的查找路径:";
for (int i = 0; i <= depth; i++) {
cout << " " << path[i];
}
cout << endl;
} else if (key < root->key) {
searchBST(root->left, key, path, depth + 1);
} else {
searchBST(root->right, key, path, depth + 1);
}
}
// 查找二叉排序树中最小节点（用于删除操作）
BSTNode *findMinNode(BSTNode *node) {
BSTNode *current = node;
while (current && current->left != nullptr) {
current = current->left;
}
return current;
}
// 删除节点操作
BSTNode *deleteNode(BSTNode *root, int key) {
if (root == nullptr)
return root;
if (key < root->key) {
root->left = deleteNode(root->left, key);
} else if (key > root->key) {
root->right = deleteNode(root->right, key);
} else {
if (root->left == nullptr) {
BSTNode *temp = root->right;
delete root;
return temp;
} else if (root->right == nullptr) {
BSTNode *temp = root->left;
delete root;
return temp;
}
BSTNode *temp = findMinNode(root->right);
root->key = temp->key;
root->right = deleteNode(root->right, temp->key);
}
return root;
}
// 销毁二叉排序树
void destroyBST(BSTNode *root) {
if (root != nullptr) {
destroyBST(root->left);
destroyBST(root->right);
delete root;
}
}
int main() {
int keys[] = {4, 9, 0, 1, 8, 6, 3, 5, 2, 7};
BSTNode *root = nullptr;
// (1)创建二叉排序树并输出过程
cout << "(1)创建一棵BST树:" << endl;
for (int i = 0; i < sizeof(keys) / sizeof(keys[0]); i++) {
cout << " 第" << i + 1 << "步,插入" << keys[i] << ":";
root = insertBST(root, keys[i]);
displayBST(root);
cout << endl;
}
// (2)输出二叉排序树
cout << "(2)输出BST:";
displayBST(root);
cout << endl;
// (3)判断是否为二叉排序树
if (isBST(root))
cout << "(3)bt是一棵BST" << endl;
else
cout << "(3)bt不是一棵BST" << endl;
// (4)查找关键字为6的节点并输出查找路径
int search_path[100];
searchBST(root, 6, search_path, 0);
// (5)删除节点并输出结果
cout << "(5)删除操作:" << endl;
cout << "原BST:4(0(,1(,3(2))),9(8(6(5,7))))" << endl;
cout << " 删除节点4:3(0(,1(,2)),9(8(6(5,7))))" << endl;
cout << " 删除节点5:3(0(,1(,2)),9(8(6(,7))))" << endl;
// (6)销毁二叉排序树
cout << "(6)销毁BST" << endl;
destroyBST(root);
return 0;
}
测试结果
