алгоритм программирования структуры данных

Question

как нарисовать бинарные деревья, чей список предварительного порядка равен abcdefgh, а чей список порядка: dcbgfhea.also, перечислить узлы двоичных деревьев в порядке следования и в порядке уровней?

Answer 1

Дерево:

            a
           /  \
          b    e
         /    / \
        c    f   h
       /    / 
      d    g

Симметричный:

dcbagfeh

порядок уровней (т. Е. BFS):

abecfhdg

Answer 2

Вот простая программа на Python, которая генерирует все возможные списки заказов на основе списков заказов и заказов.

from itertools import product

def inorders(pre, pos):
  if not pre: return [""]
  ret = []
  if pre[0] == pos[-1]:
    for left_size in range(len(pre)):
      left = inorders(pre[1:left_size+1], pos[:left_size])
      right = inorders(pre[left_size+1:], pos[left_size:-1])
      for l, r in product(left, right):
        ret.append(l + pre[0] + r)
  return ret

И вывод для вашего случая:

>>> inorders("abcdefgh", "dcbgfhea")
['bcdafgeh', 'bcdagfeh', 'bdcafgeh', 'bdcagfeh', 'cdbafgeh', 'cdbagfeh', 'dcbafgeh', 'dcbagfeh']