Как я могу построить строгое двоичное дерево, когда единственная информация - это прохождение после заказа? - PullRequest
Новая
       74

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

0 голосов
/ 07 марта 2020

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

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

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

1 Ответ

1 голос
/ 07 марта 2020

Создание полного двоичного дерева из почтового заказа аналогично созданию синтаксического дерева из Reverse Poli sh Обозначение только с двоичными операторами. Ветви - это операторы, листья - значения. (Вы должны быть в состоянии сказать, что есть что. В вашем примере, ветви - это буквы, листья - это цифры.)

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

Итак, в псевдо-i sh 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 .

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

...