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