我想实现一个 BST 并尝试使用 vector 作为输入

Question

我想用向量实现 BST class，但不知何故它不起作用。我只是想知道它不起作用的原因。

我能想到 BST 中的那个根的主要原因总是 NULL。

我想尝试在数据结构中使用 classes 的方法。

#include<iostream>
#include<vector>

using namespace std;

class Node{
    public:
    int data;
    Node* left ;
    Node* right ;

    Node(int val){
        data = val;
        left = NULL;
        right = NULL;
    }
};


class BST{
    public:
    Node* root = NULL;

    void insert(Node* r,int data){
        Node* new_node = new Node(data);
        if(r == NULL){
            r = new_node;
        }

        if(data < r->data){
            if(r->left == NULL){
                r->left = new_node;
            }
            else{
                insert(r->left,data);
            }
        }else if(data > r->data){
            if(r->right == NULL){
                r->right = new_node;
            }
            else{
                insert(r->right,data);
            }
        }else{
            return;
        }
        return;
    }

    BST(vector<int> bst_array){
        for(int i = 0; i<bst_array.size(); i++){
            insert(root,bst_array[i]);
        }
    }

    void print_t(Node* r){
        if(r == NULL){
            cout<<"NULL";
            return;
        }
            
        else{
            print_t(r->left);
            cout<<r->data<<" ";
            print_t(r->right); 
        }
    }
    
};


int main(){

    vector<int> v = {1,3,5,44,23,78,21};

    BST* tr = new BST(v);

    tr->print_t(tr->root);

    return 0;
}

我这边好像有逻辑错误，请帮我找出来。

提前致谢。

Answer 1

原因是 root 在初始化为 NULL 后从未被赋值。将 root 作为参数传递给 insert 方法永远不会改变 root 本身，因为传递的不是 root 的地址，而是它的值。

一些其他备注：

insert 总是在递归的每一步都从创建一个新节点开始。这是节点创建的浪费。最后你只需要一个新节点，所以只在确定它在树中的位置后才创建它。
不需要最后的 else，因为它所做的只是执行一个 return，如果没有那个 else 块
由于insert是BST的一个方法，可惜需要一个节点作为参数。你真的很想只做 insert(data) 让它来处理它。为此，我建议将您的 insert 方法移动到 Node class，其中 this 节点接管参数的角色。然后 BST class 可以获得包装 insert 方法，将作业转发给另一个 insert 方法。
而不是 NULL 使用 nullptr.

要解决主要问题，有很多可能的解决方案。但是在进行了上述更改之后，在 BST class.

上的简化 insert 方法中分配给 root 是相当容易的

这是它的工作原理：

class Node{
    public:
    int data;
    Node* left ;
    Node* right ;

    Node(int val){
        data = val;
        left = nullptr;
        right = nullptr;
    }

    void insert(int data) {
        if (data < this->data) {
            if (this->left == nullptr) {
                this->left = new Node(data);
            } else {
                this->left->insert(data);
            }
        } else if (data > this->data) {
            if (this->right == nullptr) {
                this->right = new Node(data);
            } else {
                this->right->insert(data);
            }
        }
    }
};

class BST {
    public:
    Node* root = nullptr;

    void insert(int data) {
        if (root == NULL) { // Assign to root
            root = new Node(data);
        } else { // Defer the task to the Node class
            root->insert(data);
        }
    }

    BST(vector<int> bst_array){
        for(int i = 0; i<bst_array.size(); i++){
            insert(bst_array[i]); // No node argument
        }
    }

    /* ...other methods ...*/
}

我想实现一个 BST 并尝试使用 vector 作为输入

I wanted to implement a BST and tried using vector for input

c++

tree

binary-tree

c++14