C++ 中的二叉搜索树实现

Question

#include <iostream>
using namespace std;

class Node{
    public:
        int data;
        Node* left_child;
        Node* right_child;
        Node(int x){
            data = x;
            left_child = NULL;
            right_child = NULL;
        }
};

class BST{
    public:
    //Initially root is null
    Node* root = NULL;

    void insert(Node* node, int data){
        if(node == NULL){
            node = new Node(data);
            return;
        }
        if(data < node->data){
            insert(node->left_child,data);
        }
        else if(data > node->data){
            insert(node->right_child,data);
        }

    }
    void just_insert(int data){
        insert(root,data);
    }
    void print(Node* node){
        if(node == NULL){
            return;
        }
        cout<<node->data<<" ";
        print(node->left_child);
        print(node->right_child);
    }
    void just_print(){
        print(root);
    }
};

int main() {
    //For fast IO
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n,x;
    cin>>n;
    BST bst = BST();
    for(int i=0; i<n; i++){
        cin>>x;
        bst.just_insert(x);
    }
    bst.just_print();
    return 0;
}

这种 BST 的实现有什么问题？我给出 8 个值作为输入： 8个 3个 5个 1个 6个 8个 7 2个 4个但是当我调用打印功能时。我没有得到任何输出。我错过了一些指针逻辑吗？ insert 函数递归地沿着树向下寻找插入值的位置打印功能也可以递归工作。

Answer 1

您永远不会在 BST class 中分配给 root，因为您在插入 class 中对节点的分配在插入函数之外是不可见的。您可以通过引用插入函数传递节点指针来解决此问题：

void insert(Node*& node, int data)

Answer 2

让我们看一下 insert 函数中的这些行：

if(node == NULL){
    node = new Node(data);
    return;
}

这里的问题是参数 node 通过值传递并且就像任何其他局部变量一样，并且像任何其他局部变量一样它将退出作用域一旦函数 returns，对变量的所有更改都将丢失。

你需要的是通过引用传递指针，喜欢

void insert(Node*& node, int data){ ... }
//               ^
// Note ampersand here

C++ 中的二叉搜索树实现

Binary Search Tree implementation in C++

c++

binary-search-tree