Построить двоичное дерево поиска

Question

Как можно на основе таких входных данных построить двоичное дерево поиска?

в первой строке количество строк, в каждой строке 3 числа: 1-ое это значение узла дерева, 2-ое это номер строки в которой находится левый ребенок. 3-ее это номер строки правого ребенка. P.s. строки считаются с 1.

Я пытался считывать все в массив потом из него строить дерево.

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

void new_tree(int *arr, node *&tree) {
    if (tree == NULL) { // с такой проверкой рекурсия никогда не закончится и дерево построить не получиться, но на ум так и не приходит как определить конец массивf
        tree = new node;
        tree->data = *arr;
        tree->left = tree->right = NULL;
        if(*(arr + 1) != 0) new_tree(arr + 3*(*(arr + 1) - 1), tree->left);
        if (*(arr + 2) != 0) new_tree(arr + 3*(*(arr + 2) - 1), tree->right);
    }
}

int main(){
    
    node *tree = NULL;

    int n;
    in >> n;
    int size = n * 3;

    int *arr = new int[size];
    for (int i = 0; i < size; i++) in >> arr[i];

    new_tree(arr, tree);

    in.close();
    out.close();
    return 0;
}

Answer 1

Раз дерево ограниченное - что бы не строить сразу в одном массиве?

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

int main()
{
    int n;
    cin >> n;
    node * tree = new node[n];
    for(int i = 0; i < n; ++i)
    {
        cin >> tree[i].data;
        int ptr;
        cin >> ptr;
        if (ptr) tree[i].left = tree+ptr;
        cin >> ptr;
        if (ptr) tree[i].right = tree+ptr;
    }
}

Более того, указатели на потомков в этом случае могут быть просто индексами в массиве, а не указателями. Кто сказал, что указатель на потомка - это обязательно адрес? Это так обычно, но далеко не всегда...

БЛОГ НА HUSL

Построить двоичное дерево поиска

Ответы (1 шт):