实验 9 —— 二叉搜索树（BST）

姓名、学号：
日期： 2026 年 1 月 2 日
课程： 程序设计导论（冬季学期 2025/26）
实验页码： 第 9 页
总分： 14 分

题目 1：二叉搜索树（14 分）

a) 基础框架、插入与查找（5 分）

在本次实验中，你需要实现一个二叉搜索树（Binary Search Tree, BST）。
二叉搜索树是一种数据结构，其中每个节点包含一个值，并最多有两个子节点（左子节点和右子节点）。对于任意节点，其左子树中的所有值都小于该节点的值，而右子树中的所有值都大于该节点的值。

背景知识可参考维基百科：https://de.wikipedia.org/wiki/Bin%C3%A4rer_Suchbaum

任务要求：

请补充文件 bst.cpp 中的以下函数：

• void insert(BinaryTree* tree, int value)
  将新值按排序规则插入到树中。
• 若树为空，则新节点成为根节点。
• 否则，从根开始比较：若 value 小于当前节点值，则向左走；否则向右走。

• 不允许重复值（即如果值已存在，则不插入）。

• Node* search(BinaryTree* tree, int value)
  在树中查找值 value。

• 若找到，返回指向该节点的指针；否则返回 nullptr。

• 利用 BST 的性质（小 → 左，大 → 右）进行高效查找。

• void destroy_tree(BinaryTree* tree)
  释放整棵树所占用的内存。

• 建议使用递归后序遍历（先删除子树，再删除当前节点）。

提示：print_tree 函数已提供，可用于打印树结构以验证你的实现。

b) 辅助函数与分析（4 分）

扩展你的实现，加入用于查找极值和分析树的函数：

• Node* find_min(BinaryTree* tree)
  返回树中最小值节点的指针。
• 若树为空，返回 nullptr。

• 提示：最小值位于最左侧的节点。

• Node* find_max(BinaryTree* tree)
  返回树中最大值节点的指针。

• 若树为空，返回 nullptr。

• 提示：最大值位于最右侧的节点。

• int sum(BinaryTree* tree)
  计算树中所有节点值的总和。

• 可使用任意遍历方式（如中序、前序或后序）访问所有节点并累加。

c) 删除元素（5 分）

最后，实现从 BST 中删除节点的功能：

• void remove(BinaryTree* tree, int value)
  若值 value 存在于树中，则删除对应节点。
  删除时需处理以下三种情况：

• 叶子节点（无子节点）：直接删除。

• 只有一个子节点：用其子节点替代它。
• 有两个子节点：
  • 用其中序后继（右子树中的最小值）或中序前驱（左子树中的最大值）替换当前节点的值。
  • 然后递归删除那个后继/前驱节点（该节点最多只有一个子节点，可简化处理）。

/* * 二叉搜索树（BST）实现 - 完整版 */
#include <iostream>
#include <iomanip> // 用于 std::setw 控制输出格式
using namespace std;

/**
 * @brief 树节点结构体
 */
struct Node {
    int data;          // 节点存储的整数值
    Node* left;        // 指向左子节点的指针
    Node* right;       // 指向右子节点的指针
};

/**
 * @brief 二叉搜索树结构体
 */
struct BinaryTree {
    Node* root;        // 指向根节点的指针
};

// ========== 辅助函数声明（用于递归实现）==========
void destroy_tree_recursive(Node* node);
Node* insert_recursive(Node* node, int value);
Node* remove_recursive(Node* node, int value);
Node* find_min_node(Node* node);
Node* find_max_node(Node* node);
int sum_recursive(Node* node);

// ========== 主要功能函数实现 ==========

/**
 * @brief 释放整棵树占用的内存
 * @param tree 指向二叉搜索树的指针
 */
void destroy_tree(BinaryTree* tree) {
    destroy_tree_recursive(tree->root); // 递归释放所有节点
    tree->root = nullptr;               // 将根指针置空，防止悬空指针
}

/**
 * @brief 递归释放以 node 为根的子树
 * 使用后序遍历：先释放左右子树，再释放当前节点
 */
void destroy_tree_recursive(Node* node) {
    if (node == nullptr) return;
    destroy_tree_recursive(node->left);
    destroy_tree_recursive(node->right);
    delete node;
}

/**
 * @brief 向二叉搜索树中插入一个值（不允许重复）
 * @param tree 指向二叉搜索树的指针
 * @param value 要插入的整数值
 */
void insert(BinaryTree* tree, int value) {
    tree->root = insert_recursive(tree->root, value);
}

/**
 * @brief 递归插入函数
 * 若当前节点为空，则创建新节点；
 * 否则根据 BST 性质向左或向右递归插入。
 */
Node* insert_recursive(Node* node, int value) {
    if (node == nullptr) {
        // 创建新节点（无子节点）
        Node* newNode = new Node{value, nullptr, nullptr};
        return newNode;
    }
    if (value < node->data) {
        node->left = insert_recursive(node->left, value);
    } else if (value > node->data) {
        node->right = insert_recursive(node->right, value);
    }
    // 如果 value == node->data，说明值已存在，不插入（去重）
    return node;
}

/**
 * @brief 在树中查找指定值
 * @param tree 指向二叉搜索树的指针
 * @param value 要查找的整数值
 * @return 若找到，返回指向该节点的指针；否则返回 nullptr
 */
Node* search(BinaryTree* tree, int value) {
    Node* current = tree->root;
    while (current != nullptr) {
        if (value == current->data) {
            return current;
        } else if (value < current->data) {
            current = current->left;   // 值更小，向左子树查找
        } else {
            current = current->right;  // 值更大，向右子树查找
        }
    }
    return nullptr; // 未找到
}

/**
 * @brief 查找树中的最小值节点
 * @param tree 指向二叉搜索树的指针
 * @return 最小值节点指针；若树为空，返回 nullptr
 */
Node* find_min(BinaryTree* tree) {
    if (tree->root == nullptr) return nullptr;
    return find_min_node(tree->root);
}

/**
 * @brief 从给定节点开始，一路向左找到最小值节点
 */
Node* find_min_node(Node* node) {
    while (node->left != nullptr) {
        node = node->left;
    }
    return node;
}

/**
 * @brief 查找树中的最大值节点
 * @param tree 指向二叉搜索树的指针
 * @return 最大值节点指针；若树为空，返回 nullptr
 */
Node* find_max(BinaryTree* tree) {
    if (tree->root == nullptr) return nullptr;
    return find_max_node(tree->root);
}

/**
 * @brief 从给定节点开始，一路向右找到最大值节点
 */
Node* find_max_node(Node* node) {
    while (node->right != nullptr) {
        node = node->right;
    }
    return node;
}

/**
 * @brief 从树中删除指定值的节点
 * @param tree 指向二叉搜索树的指针
 * @param value 要删除的整数值
 */
void remove(BinaryTree* tree, int value) {
    tree->root = remove_recursive(tree->root, value);
}

/**
 * @brief 递归删除函数，处理三种情况：
 * 1. 叶子节点：直接删除
 * 2. 有一个子节点：用子节点替代
 * 3. 有两个子节点：用中序后继（右子树最小值）替换，再删除后继
 */
Node* remove_recursive(Node* node, int value) {
    if (node == nullptr) return nullptr;

    if (value < node->data) {
        node->left = remove_recursive(node->left, value);
    } else if (value > node->data) {
        node->right = remove_recursive(node->right, value);
    } else {
        // 找到要删除的节点
        if (node->left == nullptr && node->right == nullptr) {
            // 情况1：叶子节点
            delete node;
            return nullptr;
        } else if (node->left == nullptr) {
            // 情况2：只有右孩子
            Node* temp = node->right;
            delete node;
            return temp;
        } else if (node->right == nullptr) {
            // 情况2：只有左孩子
            Node* temp = node->left;
            delete node;
            return temp;
        } else {
            // 情况3：两个孩子
            // 找到右子树中的最小值（中序后继）
            Node* successor = find_min_node(node->right);
            node->data = successor->data; // 用后继值覆盖当前节点
            // 递归删除后继节点（它最多只有一个右孩子）
            node->right = remove_recursive(node->right, successor->data);
        }
    }
    return node;
}

/**
 * @brief 计算树中所有节点值的总和
 * @param tree 指向二叉搜索树的指针
 * @return 所有节点值之和
 */
int sum(BinaryTree* tree) {
    return sum_recursive(tree->root);
}

/**
 * @brief 递归计算以 node 为根的子树的节点值总和
 */
int sum_recursive(Node* node) {
    if (node == nullptr) return 0;
    return node->data + sum_recursive(node->left) + sum_recursive(node->right);
}

// --- 以下为预提供的打印函数（无需修改）---

/**
 * @brief 递归打印树的结构（横向显示）
 */
void print_tree_recursive(Node* node, int indent) {
    if (node != nullptr) {
        if (node->right) {
            print_tree_recursive(node->right, indent + 4);
        }
        if (indent) {
            cout << setw(indent) << " ";
        }
        if (node->right) cout << " /" << endl << setw(indent) << " ";
        cout << node->data << endl;
        if (node->left) {
            cout << setw(indent) << " " << " \\" << endl;
            print_tree_recursive(node->left, indent + 4);
        }
    }
}

/**
 * @brief 打印整棵树
 */
void print_tree(BinaryTree* tree) {
    if (tree->root == nullptr) {
        cout << "(空树)" << endl;
    } else {
        print_tree_recursive(tree->root, 0);
    }
}

// --- 主函数：用于测试所有功能 ---
int main() {
    BinaryTree tree;
    tree.root = nullptr;

    cout << "插入值: 50, 30, 20, 40, 70, 60, 80" << endl;
    insert(&tree, 50);
    insert(&tree, 30);
    insert(&tree, 20);
    insert(&tree, 40);
    insert(&tree, 70);
    insert(&tree, 60);
    insert(&tree, 80);

    cout << "\n当前树结构：" << endl;
    print_tree(&tree);

    cout << "\n查找测试：" << endl;
    cout << "查找 40: " << (search(&tree, 40) ? "找到" : "未找到") << endl;
    cout << "查找 90: " << (search(&tree, 90) ? "找到" : "未找到") << endl;

    Node* minNode = find_min(&tree);
    if (minNode) cout << "最小值: " << minNode->data << endl;

    Node* maxNode = find_max(&tree);
    if (maxNode) cout << "最大值: " << maxNode->data << endl;

    cout << "所有节点值之和: " << sum(&tree) << endl;

    cout << "\n删除 20（叶子节点）：" << endl;
    remove(&tree, 20);
    print_tree(&tree);

    cout << "\n删除 30（仅有一个子节点）：" << endl;
    remove(&tree, 30);
    print_tree(&tree);

    cout << "\n删除 50（有两个子节点，且为根节点）：" << endl;
    remove(&tree, 50);
    print_tree(&tree);

    cout << "\n释放整棵树内存..." << endl;
    destroy_tree(&tree);
    cout << "完成。" << endl;

    return 0;
}

题库练习：

https://hlcoding.com/solution/description/6193/

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com