用中序和前序遍历重建树的Python实现

Question

我需要写一个函数，从前序遍历和中序遍历构建一棵树，但我不太确定该在哪里放置创建节点的代码和递归调用，以便正确构建这棵树。

假设中序遍历和前序遍历都是整数列表，下面这个算法是否正确，用来根据遍历结果重建这棵树？

def build(preorder, inorder):
    root = preorder[0]
    left subtree = inorder[:root-1]
    right subtree = inorder[root+1:]

如果是这样的话，如何利用这个算法递归地构建一个堆（ArrayHeap）呢？我有一个类是用来构建节点的，然后我可以简单地用 heap.add(node) 来创建堆。

假设我用来创建节点的类叫“MakeNode”，它的构造方式如下（为了语法的目的）：

Class MakeNode():
    def __init__(self, character, left=None, right=None):

为了创建根节点，我需要像这样修改函数：

def build(preorder, inorder, heap):
    root = preorder[0]
    node = MakeNode(root) # Creating root node here
    heap.add(node) # Adding to heap
    left subtree = inorder[:root-1]
    right subtree = inorder[root+1:]

但是我应该如何使用递归来构建树的其余部分呢？
我可以通过这样做来结合左右的前序遍历，以便进行排序：

def build(preorder, inorder, heap):
    root = preorder[0]
    node = MakeNode(root)
    heap.add(node)
    left subtree = inorder[:root-1]
    # order of left subtree = preorder[1:1+left subtree]
    right subtree = inorder[root+1:]
    # order of right subtree = preorder[root+1:]

我其实不太知道如何将递归调用结合进来，或者在这样做时，左边或右边的参数应该具体放什么。

如果有人有建议，我会很感激的，如果我表达得不清楚也很抱歉。

Answer 1

def pre_order(node):
    print node #pre order ... print ourself first
    pre_order(node.left)
    pre_order(node.right)

def post_order(node):
    post_order(node.left)
    post_order(node.right)
    print node # post order print self last...

def in_order(node):
    in_order(node.left)
    print node  #in order ... between its children
    in_order(node.right)

    0
 1     2
3 4   5 6

0,1,3,4,2,5,6 #pre order
3,1,4,0,5,2,6 #in order

 1,4,2,5 # preorder
 1,4,5,2 # in-order

      0
   1      2
 3          6

4,5 # pre order
4,5 # in order

如果你有这些信息，你应该能重建这棵树。

假设我们有这样一棵树：

我们的遍历结果是：

从这个结果我们可以知道：

1. 零是我们的根节点。
2. 3是最左边最深的节点。
3. 6是最右边最深的节点。

0 ... 3 6

剩下的节点是：

从这个结果我们可以知道：

1. 1是零的子节点。
2. 1是下一层的最左边节点。
3. 2是下一层的最右边节点。

所以我们现在有：

留下的就是：

从这个结果我们可以知道4是1的子节点，因此5一定是2的子节点……

现在写一个函数来完成这些操作。

这篇文章可能会对你有帮助：

http://leetcode.com/2011/04/construct-binary-tree-from-inorder-and-preorder-postorder-traversal.html

Answer 2

来自 http://www.cse.hut.fi/en/research/SVG/TRAKLA2/tutorials/heap_tutorial/taulukkona.html，你可以这样做：

parent(i) = i/2
left(i) = 2i
right(i) = 2i+1

所以你可以定义一个类：

class ArrayHeapNode:
    def __init__(self, elements, index):
        self.elements = elements
        self.index = index

    def left(self):
        next = self.index * 2
        if next >= len(self.elements):
            return None
        return ArrayHeapNode(self.elements, next)

    def right(self):
        next = (self.index * 2) + 1
        if next >= len(self.elements):
            return None
        return ArrayHeapNode(self.elements, next)

    def value(self):
        return self.elements[self.index]

    def set_value(self, _value):
        self.elements[self.index] = _value

这样你就得到了一个类，它可以根据文章中的内容，作为一个数组表示的二叉堆的树。如果这个分支没有元素，就会返回None。

现在你可以创建树的遍历算法（https://en.wikipedia.org/wiki/Tree_traversal）：

def inorder_traversal(node, action):
    if not node: return
    inorder_traversal(node.left(), action)
    action(node.value())
    inorder_traversal(node.right(), action)

def preorder_traversal(node, action):
    if not node: return
    action(node.value())
    preorder_traversal(node.left(), action)
    preorder_traversal(node.right(), action)

这些算法同样适用于传统的二叉树节点：

class BinaryTreeNode:
    def __init__(self, value, left, right):
        self._value = value
        self._left = left
        self._right = right

    def left(self):
        return self._left

    def right(self):
        return self._right

    def value(self):
        return self._value

    def set_value(self, _value):
        self._value = _value

现在，你可以通过以下方式让遍历算法更灵活，更像Python的风格：

def inorder(node):
    if node:
        for item in inorder(node.left()):
            yield item
        yield node.value()
        for item in inorder(node.right()):
            yield item

这让你可以写出像这样的代码：

for item in inorder(tree):
    print item

然后你可以通过以下方式从节点中计算元素的数量：

n = sum(1 for e in inorder(root))

这样你就可以创建一个空数组，能够容纳n个元素，用于堆中的元素：

elements = [0 for x in range(n)]

或者结合起来：

elements = [0 for x in inorder(root)]
heap = ArrayHeapNode(elements, 0)

现在，你可以同时遍历这两棵树，使用：

for a, b in zip(inorder(root), inorder(heap)):
    b = a

这将把二叉树中的所有元素（root）分配到数组堆中的正确位置（heap），使用的是中序遍历。同样的操作也可以通过实现一个preorder函数来完成。

注意：我没有测试这段代码。

Answer 3

你需要做的是把先序列表的第一个元素（也就是树的根节点）添加到树里，然后把它从先序列表中移除。接着，像你之前做的那样，把中序列表分开，然后递归地处理左右两个分支。保持把先序列表的第一个元素加到前一个节点的左边，除非左子树是空的，这时候就需要把它加到右边。

下面是已经测试过的Python代码：

class Tree():
    def __init__(self, inorder, preorder):
        self.root = preorder[0]
        lt = inorder[:inorder.index(self.root)]
        rt = inorder[inorder.index(self.root) + 1:]
        self.build(self.root, lt, rt, preorder[1:])
    def build(self, last_node, left_subtree, right_subtree, preorder):
        left_preorder = [node for node in preorder if node in left_subtree] 
        right_preorder =  [node for node in preorder if node in right_subtree]
        if len(left_subtree) > 0:
            last_node.left = left_preorder[0]
            lt = left_subtree[:left_subtree.index(last_node.left)]
            rt = left_subtree[left_subtree.index(last_node.left) + 1:]
            self.build(last_node.left, lt, rt, left_preorder)
        if len(right_subtree) > 0:
            last_node.right = right_preorder[0]
            lt = right_subtree[:right_subtree.index(last_node.right)]
            rt = right_subtree[right_subtree.index(last_node.right) + 1:]
            self.build(last_node.right, lt, rt, right_preorder)