二叉搜索树插入节点失败：根节点始终为nullptr的解决方法

原代码 #

节点结构体 #

struct node {
    int data{};
    node *right{nullptr};
    node *left{nullptr};
};

二叉树类定义 #

class BTree {
private:
    node *root;
    void insert(node *sr, int num);

public:
    BTree();
    void buildTree(int num);
};

insert 方法实现 #

void BTree::insert(node *sr, int num) {
    if (sr == nullptr) {
        sr = new node;
        sr->data = num;
    } else {
        if (num < sr->data)
            insert(sr->left, num);
        else
            insert(sr->right, num);
    }
}

main 函数 #

int main() {
    BTree tree;
    tree.buildTree(3);
    return 0;
}

问题根源 #

你写的 insert 函数用了传值方式传递指针，这意味着函数里的 sr 只是原指针的一个副本。当你在 sr == nullptr 时给 sr 分配新节点，修改的仅仅是这个副本，原指针（比如类里的 root，或者父节点的 left/right）根本不会被更新。

比如第一次调用 insert(root, 3) 时，root 原本是 nullptr，函数里的 sr 副本被赋值为新节点，但 root 本身还是保持 nullptr，自然看不到节点被添加。

修复方案 #

有两种简单有效的修复方式：

方式一：传递指针的引用 #

把 insert 函数的参数改成指针的引用，这样修改 sr 就会直接作用于原指针：

// 类内声明修改
void insert(node* &sr, int num);

// 方法实现修改
void BTree::insert(node* &sr, int num) {
    if (sr == nullptr) {
        sr = new node;
        sr->data = num;
    } else {
        if (num < sr->data)
            insert(sr->left, num);
        else
            insert(sr->right, num);
    }
}

同时别忘了补充类的构造函数和 buildTree 的实现（否则编译会报错）：

BTree::BTree() : root(nullptr) {}

void BTree::buildTree(int num) {
    insert(root, num);
}

方式二：让 insert 返回节点指针 #

让 insert 函数返回新的节点指针，在调用处手动更新原指针：

// 类内声明修改
node* insert(node *sr, int num);

// 方法实现修改
node* BTree::insert(node *sr, int num) {
    if (sr == nullptr) {
        sr = new node;
        sr->data = num;
        return sr;
    } else {
        if (num < sr->data)
            sr->left = insert(sr->left, num);
        else
            sr->right = insert(sr->right, num);
        return sr;
    }
}

// buildTree 实现
void BTree::buildTree(int num) {
    root = insert(root, num);
}

// 构造函数
BTree::BTree() : root(nullptr) {}

两种方式都能解决问题，第一种传递指针引用的写法更简洁直观，推荐优先使用。

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