Вставка в двоичное дерево (geeksforgeeks) рекурсивно - PullRequest
Новая
       41

Вставка в двоичное дерево (geeksforgeeks) рекурсивно

1 голос
/ 12 апреля 2020

Я пытаюсь реализовать функцию вставки, используемую на geeksforgeeks.com, но сталкиваюсь с некоторыми проблемами, пытаясь включить ее в мой текущий код.

У меня есть вектор с данными, которые мне нужно поместить в двоичное дерево. Я использую эту функцию для передачи чисел в функцию вставки: 

void populateTree(vector<string> dataVec) {
    for (int i = 0; i < dataVec.size(); i++) {
        insert(stoi(dataVec[i]), root);
    }
}

Это функция вставки: 

node* insert(int x, node* node) {

    if (node == nullptr)
        return newNode(x);
    if (x < node->data)
        node->left = insert(x, node->left);
    else
        node->right = insert(x, node->right);

    return root;
}

Новая функция узла: 

node* newNode(int num) {

node* temp = new node;
temp->data = num;
temp->left = temp->right = nullptr;
temp->level = 1;
return temp;

}

Root - это закрытый член в классе, который инициализируется значением nullptr. Я не уверен, как я должен go сделать первый узел, который приходит из вектора, как root, а затем продолжать рекурсивно вставлять вещи, начиная с него. Спасибо!

1 Ответ

1 голос
/ 12 апреля 2020

Ваша проблема связана с использованием указателя.

Вместо использования node* insert(int x, node* node) вы должны использовать node* insert(int x, node** node) или node* insert(int x, node*& node) и соответственно принять ваш код.

Ниже приведено исправленный пример кода. См. Здесь в исполнении : 

#include <iostream>
#include <vector>
using namespace std;

struct Node
{
    int val;
    Node* left;
    Node* right;

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


class Tree
{
    Node* root;

    Tree()
    {
        root = nullptr;
    }

    public:

    static void insert(int x, Node*& node)
    {
        if (node == nullptr)
        {
            node = new Node(x);
        }
        else
        {
            if (x < node->val)
                insert(x, node->left);
            else
                insert(x, node->right);
        }
    }

    static Tree* populateTree(vector<string> dataVec)
    {
        Tree* t= new Tree();
        for (int i = 0; i < dataVec.size(); i++)
        {
            insert(stoi(dataVec[i]), t->root);
        }
        return t;
    }

    static void printTree(Node* node, string s)
    {
        if(node == nullptr) return;
        cout<<s<< "+"<<node->val <<endl;
        s += "----";
        printTree(node->left,s);
        printTree(node->right, s);
    }

    static void printTree(Tree* t)
    {
        if(t)
        {
            printTree(t->root, "");
        }
    }
};

int main() {
    Tree* t = Tree::populateTree({"70", "2", "7", "20", "41", "28", "20", "51", "91"});
    Tree::printTree(t);
    return 0;
}
...