C++ 二叉搜索树插入实现

Question

我正在尝试构建一个函数以插入到二叉搜索树中，但我很难弄清楚为什么它不起作用。我从根本上理解该函数应该如何工作，但是根据给我的模板，我似乎要避免创建 BST class 而是依赖节点 class 并构建所需的功能来解决这个问题。这是给定的模板：

#include <iostream>
#include <cstddef>

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

class Node {
    int value;
public:
    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;
    }
};

function insert(Node *insert_node, Node *tree_root){
    //Your code here
}

我遇到的问题是当我实现以下代码时，其中 getValue 是 Node 的一个简单 getter 方法：

int main(int argc, const char * argv[]) {
     Node* root = NULL;
     Node* a = new Node(2);
     insert(a, root);
}

void insert(Node *insert_node, Node *tree_root){
    if (tree_root == NULL)      
        tree_root = new Node(insert_node->getValue());

代码似乎可以编译并且运行没有错误，但是如果我运行在此之后再次检查 root，它 returns NULL。知道我在这里缺少什么吗？为什么不用等于 insert_node 的新节点替换 root?

我也意识到这似乎不是实现 BST 的最佳方式，但我正在尝试使用提供给我的模板。如有任何建议，我们将不胜感激。

Answer 1

正如 Joachim 所说，您的问题与按引用传递参数和按值传递参数之间的区别有关。

在您的代码 void insert(Node *insert_node, Node *tree_root) 中，您按值传递 Node* tree_root。在函数内部您更改此指针的本地副本，因此外部值不会更改。

要修复它，您应该将 Node* tree_root 传递给 reference。参数声明可以是Node*& tree_root（或Node** tree_root）。例如：

void insert(Node* insert_node, Node*& tree_root){
    if (tree_root == NULL)      
        tree_root = new Node(insert_node->getValue());

C++ 二叉搜索树插入实现

C++ Binary Search Tree Insert Implementation

c++

binary-tree