Как построить недвоичное дерево, основанное на предположении и оформлении порядка или послепорядка?

Question

Два упражнения для моих структур данных и класса звука Алгоритмов как этого

Постройте дерево, обход является: 1, 2, 5, 3, 6, 10, 7, 11, 12, 4 , 8, 9 и обход инвертора составляет 5, 2, 1, 10, 6, 3, 11, 7, 12, 8, 4, 9.

Построить дерево, обход которого по порядку: 5, 2, 10, 6, 11, 12, 7, 3, 8, 9, 4, 1 и обход инвертора составляет 5, 2, 1, 10, 6, 3, 11, 7, 12, 8, 4, 9.

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

Answer 1

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

Во-первых, подумайте о том, как обход обхода проходит по дереву. Если вы нарисуете дерево так, чтобы левый левый слева (визуально), а остальные дети справа (визуально), то обход ордера свободно перемещается слева направо. Вы можете столкнуться с проблемой, когда она не совсем оставлена ​​вправо (из-за некоторого совпадения между дочерним элементом одного узла и родителем или что-то в этом роде), но вы всегда можете растянуть дерево, чтобы оно было четко «слева направо». Поэтому я воспользоваться этим путем начиная мое дерево с заказовМой обходом:

5 2 1 10 6 3 11 7 12 8 4 9 

Тогда идея мы перемещаем узлы вверх и вниз в соответствии с обходом. Эта часть трудно определить. В основном вы перемещаете узлы вверх, если они посещаются «раньше» и перемещают их вниз, если они посещаются позже. Так, например, 1 находится слева от 2 и 5 в обходе предзаказов, поэтому я поднял его вверх в том смысле, что я сделал 2 и 5 предков (но не обязательно детей) 1. Так что-то вроде

1 
5 2 10 6 3 11 7 12 8 4 9 

Тогда вы увидите 2, который идет до 5, так что я поднял 2:

1 
    2 
5  10 6 3 11 7 12 8 4 9 

Затем вы видите 3 идет до 6 и 10 в обходе, чтобы мы могли «поднять» его.

1 
    2  3 
5  10 6 11 7 12 8 4 9 

И так далее. Обратите внимание, что 3 в конечном итоге может быть дочерним из 2 или 1 ... дерево, которое удовлетворяет вышеуказанным ограничениям, не является уникальным.