数据结构编程算法

Question

如何绘制前序列表为abcdefgh、后序列表为dcbgfhea的二叉树。另外，按中序和层序列出二叉树的节点？

Answer 1

树：

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

inorder：

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']