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

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

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

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 ... дерево, которое удовлетворяет указанным выше ограничениям, не является уникальным.