Как я могу построить строгое двоичное дерево, если единственной предоставленной информацией является обход в обратном порядке?

Ранее я спрашивал, как получить предварительный порядок дерева, когда мне дается только обход после заказа. Однако теперь мне любопытно, как можно было бы построить строгое двоичное дерево (строгое двоичное дерево, означающее, что узел либо имеет двух дочерних элементов, либо не имеет дочерних элементов), если только задан обход по порядку. Некоторые примеры данных, с которыми я имею дело:

7 8 2 // 8,2 are dimensions stored in the node, likewise for other nodes)
6 4 8
3 1 5
A
B

Я знаю, как должно выглядеть дерево:

               B
            /     \
           7       A
                 /    \
                6      3

Но я не понимаю, как написать функцию, которая фактически построила бы это дерево (и сохранила бы информацию в узлах) из предоставленной информации (обход после заказа). Как я могу это сделать?


c tree binary-tree tree-traversal postorder
person fresh42juice    schedule 07.03.2020    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Создание полного двоичного дерева из обратного порядка похоже на создание синтаксического дерева из обратной польской нотации только с бинарные операторы. Ветви — это операторы, листья — это значения. (Вы должны уметь различать, что есть что. В вашем примере веточки — это буквы, а листья — числа.)

Вы можете обрабатывать данные по мере их поступления. Если это лист, создайте узел и поместите его в стек. Это ветвь, создайте узел, извлеките его правую и левую ветви из стека и поместите новый узел. Если полученные данные действительны, у вас должен быть один узел в стеке. Это корень вашего дерева.

Итак, в псевдо-коде C:

Node *head = NULL;

while (!stream_empty()) {
    int data = stream_get();

    if (is_leaf(data)) {
        if (nstack == MAX) fatal("Stack overflow!");

        stack_push(make_node(data));
    } else {
        if (stack_size < 2) fatal("Stack underflow!");

        Node *node = make_node(data);

        node->right = stack_pop();
        node->left = stack_pop();
        stack_push(node);
    }
}

if (nstack != 1) fatal("Ill-formed full binary tree!");

head = stack[0];

Переполнение стека происходит, когда размер дерева превышает размер стека. Опустошение стека или остаточные узлы в конце возникают, когда входные данные имеют неправильный формат.

Вот полный рабочий пример на ideone.

[Примечание: я полностью переписал свой ответ, потому что в ОП указаны новые требования. Я также основывал свой первоначальный ответ на ответе, который я дал на предыдущий вопрос ОП. Я думаю, что нынешний подход более элегантный. Что бы это ни означало, это. :)]

person M Oehm    schedule 07.03.2020
comment
Спасибо. Мне было интересно, есть ли способ сделать это, если вы не знаете количество узлов в файле. Или просто я должен их посчитать перед использованием этой функции? - person fresh42juice; 07.03.2020
comment
Вы можете использовать стек и обращаться с деревом как с синтаксическим деревом, а порядок следования как с обратной польской записью, где ветви — это бинарные операторы, а листья — значения. Вероятно, это даже более элегантный алгоритм, чем тот, который я дал. - person M Oehm; 07.03.2020
comment
(Но если это ваше требование, это должно быть частью вопроса.) - person M Oehm; 07.03.2020