首页 > 试题广场 >

算法题,给前序和中序,求出二叉树

[问答题]

算法题,给前序和中序,求出二叉树

def buildBTreeFromPreIn(preo, ino):
    if (preo == '' or ino == ''):
        return None
    pos = ino.find(preo[0])  # 在中序遍历中,找到根节点,从而可左右划分出左右子树
    if (pos < 0):
        return None
    # 前序: 父左右  中序: 左父右
    return BTree(preo[0], buildBTreeFromPreIn(preo[1:pos + 1], ino[0:pos]), # 迭代的找,前序的根节点,在中序中的位置,迭代重构出树
                 buildBTreeFromPreIn(preo[pos + 1:], ino[pos + 1:]))
                # (preo[1:pos + 1], ino[0:pos]) 左树
                # (preo[pos + 1:], ino[pos + 1:])) 右树 preo = 'abdecf'  ino = 'dbeafc'  po = 'debfca'  bt = buildBTreeFromPreIn(preo, ino)  print 'Build from preorder & inorder'  print 'The BTree is (* means no such a node):' 

编辑于 2019-07-18 23:06:43 回复(0)