C ++, как создать и нарисовать двоичное дерево, а затем пройти его в предзаказ

Question

C ++, как создать и нарисовать двоичное дерево, а затем пройти его в предзаказ

Как создать двоичное дерево и нарисовать его, используя стратегию обхода предварительного заказа? Корень будет первым входящим числом.

У меня есть набор чисел: 48 32 51 54 31 24 39, 48 будет корнем. Как дочерние узлы помещаются в двоичное дерево при обходе предварительного заказа?

0

binary-tree c++tree-traversal

Решение

Другие решения

Допустим, у вас есть следующее двоичное дерево:

        A
/    \
B        C
/ \      / \
D   E    F   G
/ \
H   I

Предварительный заказ проходит УЗЕЛ, ВЛЕВО, ВПРАВО.

Таким образом, предзаказ этого двоичного дерева будет: A B D E H I C F G

Для более подробной информации о том, как реализовать это в C ++: https://stackoverflow.com/a/17658699/445131

2

Источник

Accepted Answer

Представьте себе следующую подзадачу. У вас есть набор чисел:

N A1...AX B1...BY

Ты знаешь что N является корнем соответствующего дерева. Все, что вам нужно знать, это то, какие числа образуют левое поддерево. Очевидно, что остальные числа образуют правильное поддерево.

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

Следовательно, левое поддерево — это последовательность чисел, которые меньше (или, возможно, равны) N, Остальные числа находятся в правом поддереве.

Рекурсивно решить для

A1...AX

а также

B1...BY

Например, учитывая:

10 1 5 2 9 3 1 6 4 11 15 12 19 20

Ты получаешь:

корень: 10
левое поддерево: 1 5 2 9 3 1 6 4
правое поддерево: 11 15 12 19 20

2