Нахождение двух других обходов двоичного дерева, если дан только один обход
Я знаю, что вы можете реконструировать бинарное дерево, когда ему даны обходы по порядку и по предзаказу в виде строк, но возможно ли найти обходы по порядку и / или по предварительному порядку, когда только дан обход по порядку?
Решение
Нет, получение почтового заказа / предварительного заказа только из обхода заказа невозможно. Если бы это было так, было бы возможно восстановить двоичное дерево только с обходом по порядку, что невозможно, поскольку один обход по порядку может дать вам несколько возможных восстановленных двоичных деревьев.
Другие решения
Как выглядит ваш вклад и какова цель дерева?
Если у вас есть полностью упорядоченное выражение в порядке, то у вас есть уникальное дерево, и вы получаете предварительный и последующий порядок, создавая дерево, а затем создавая предварительные и последующие элементы из дерева.
Если ваше выражение не полностью заключено в скобки, это указывает на то, что нет никакой разницы между различными деревьями, которые соответствуют вашему порядку. Например, если это дерево, представляющее арифметические выражения, то x+y+zтакой же как (x+y)+z а также x+(y+z),
Это, однако, означает, что не имеет значения, какой пре- или почтовый заказ вы используете, а также ++xyzа также +x+yzподобные.
Теперь, если это не имеет значения, вам не нужно беспокоиться о нескольких возможных представлениях вашего заказа. Просто выберите одно из представлений, а затем вычислите предварительный и последующий порядок, индуцированный этим деревом.
detector