C++二叉搜索树增删查函数调用报错及功能实现求助

核心错误点 #

• 函数调用不匹配：你定义的insert函数需要两个Node*参数（待插入节点和树根），但main里直接传了整数，而且部分调用写成了大写Insert（C++区分大小写）
• 未初始化树根：main里没有定义tree_root变量，也没有初始化第一个节点作为根
• 未实现/声明打印函数：main里调用的PrintTree函数既没声明也没实现
• delete_node空指针风险：当删除根节点时，tree_root->p是NULL，访问tree_root->p->left会触发空指针异常

修复后的完整代码 #

#include <iostream>
#include <cstddef>

using std::cout;
using std::endl;

class Node {
public:
    int value;
    Node* left;       // left child
    Node* right;      // right child
    Node* p;          // parent
    Node(int data) {
        value = data;
        left = NULL;
        right = NULL;
        p = NULL;
    }
    ~Node() {}
    int d() {
        return value;
    }
    void print() {
        std::cout << value << std::endl;
    }
};

// 中序遍历打印树（替代未定义的PrintTree）
void inorder_print(Node* root) {
    if (root == NULL) return;
    inorder_print(root->left);
    cout << root->value << " ";
    inorder_print(root->right);
}

// 封装insert：直接传入数值和树根引用，自动创建节点
void insert(int value, Node*& tree_root) {
    Node* new_node = new Node(value);
    if (tree_root == NULL) {
        tree_root = new_node;
        return;
    }
    Node* current = tree_root;
    Node* parent = NULL;
    while (current != NULL) {
        parent = current;
        if (value < current->d()) {
            current = current->left;
        } else {
            current = current->right;
        }
    }
    new_node->p = parent;
    if (value < parent->d()) {
        parent->left = new_node;
    } else {
        parent->right = new_node;
    }
}

void delete_node(int value, Node*& tree_root) {
    // 先定位要删除的节点
    Node* target = tree_root;
    Node* parent = NULL;
    while (target != NULL && target->d() != value) {
        parent = target;
        if (value < target->d()) {
            target = target->left;
        } else {
            target = target->right;
        }
    }
    if (target == NULL) return; // 未找到目标节点，直接返回

    // 情况1：叶子节点
    if (target->left == NULL && target->right == NULL) {
        if (target == tree_root) {
            tree_root = NULL;
        } else if (parent->left == target) {
            parent->left = NULL;
        } else {
            parent->right = NULL;
        }
        delete target;
    }
    // 情况2：只有右子树
    else if (target->left == NULL) {
        if (target == tree_root) {
            tree_root = target->right;
        } else if (parent->left == target) {
            parent->left = target->right;
        } else {
            parent->right = target->right;
        }
        if (target->right != NULL) target->right->p = parent;
        delete target;
    }
    // 情况3：只有左子树
    else if (target->right == NULL) {
        if (target == tree_root) {
            tree_root = target->left;
        } else if (parent->left == target) {
            parent->left = target->left;
        } else {
            parent->right = target->left;
        }
        if (target->left != NULL) target->left->p = parent;
        delete target;
    }
    // 情况4：有两个子树，用右子树最小节点替代
    else {
        Node* min_right = target->right;
        Node* min_parent = target;
        while (min_right->left != NULL) {
            min_parent = min_right;
            min_right = min_right->left;
        }
        target->value = min_right->value;
        // 删除min_right节点
        if (min_parent->left == min_right) {
            min_parent->left = min_right->right;
        } else {
            min_parent->right = min_right->right;
        }
        if (min_right->right != NULL) {
            min_right->right->p = min_parent;
        }
        delete min_right;
    }
}

Node* search(int value, Node* tree_root) {
    Node* current = tree_root;
    while (current != NULL && current->d() != value) {
        if (value < current->d()) {
            current = current->left;
        } else {
            current = current->right;
        }
    }
    return current;
}

int main(int argc, const char* argv[])
{
    Node* tree_root = NULL;

    // 插入指定列表[3,1,5,7,9,2]
    int insert_list[] = {3,1,5,7,9,2};
    for (int num : insert_list) {
        insert(num, tree_root);
    }

    cout << "插入后中序遍历结果：";
    inorder_print(tree_root);
    cout << endl;

    // 删除两个元素，示例删除3和7
    delete_node(3, tree_root);
    cout << "删除3后中序遍历结果：";
    inorder_print(tree_root);
    cout << endl;

    delete_node(7, tree_root);
    cout << "删除7后中序遍历结果：";
    inorder_print(tree_root);
    cout << endl;

    // 搜索指定数字，示例搜索5和8
    Node* found = search(5, tree_root);
    if (found != NULL) {
        cout << "找到数字：" << found->value << endl;
    } else {
        cout << "未找到数字5" << endl;
    }

    found = search(8, tree_root);
    if (found != NULL) {
        cout << "找到数字：" << found->value << endl;
    } else {
        cout << "未找到数字8" << endl;
    }

    return 0;
}

关键修复说明 #

1. 重构insert函数，支持直接传入数值和树根引用，自动创建节点，简化调用逻辑
2. 修复delete_node的空指针问题，处理了根节点删除的边界情况
3. 实现中序遍历打印函数，替代原未定义的PrintTree
4. 在main中完成了指定列表插入、元素删除、目标搜索的完整测试逻辑

内容的提问来源于stack exchange，提问作者fewdm