data structure programming algorithm

how to draw binary trees whose preorder listing is abcdefgh and whose postorder listing is dcbgfhea.also,list the nodes of binary trees in inorde开发者_运维知识库r and level order ?

Tree:

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

inorder:

dcbagfeh

level order (i.e BFS):

abecfhdg

Here's a simple Python program that generates all possible inorder listings based on preorder and postorder listings.

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

And here's the output for your case:

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