python - 通过循环创建二叉树

Question

我想通过遍历循环来创建一个二叉树。我知道如何编写一个非常基本的二叉树。

class Tree(object):
    def __init__(self):
        self.left = None
        self.right = None
        self.data = None


root = Tree()
root.data = 75
root.left = Tree()
root.left.data = 95
root.right = Tree()
root.right.data = 64

root.left.left = Tree()
root.left.left.data = 32
root.left.right = Tree()
root.left.right.data = 93
root.left.left = Tree()
root.right.left.data = 32
root.left.right = Tree()
root.right.right.data = 93

print(root.data)

手写起来很乏味，如果我有一个数字列表:

list = [1,2,3,4,5,6,7]

然后将其放入一个循环中以按以下顺序创建二叉树:

   1 
 2   3
4 5 6 7

我该怎么写？因为我用它来计算所有路径的总和，你如何导航/迭代二叉树:

Answer 1

要从节点值列表构建完整的二叉树(不一定二叉搜索树)，我们假设列表中的值根据级别排序-顺序遍历。因此，您的问题列表

values = [1,2,3,4,5,6,7]

将代表一棵树:

   1 
 2   3
4 5 6 7

注意根值在位置0，它的左 child 在位置1*2-1=1，右 child 在 1*2=2等。一般来说，对于列表中索引为i的节点，其左子节点位于(i+1)*2-1，右 child 位于 (i+1)*2。

现在，我们只需要递归地构建树，逐个节点，在创建左子树和右子树的每一步中。

为了简单起见，我们假设 values 列表是全局的。

class Node(object):
    def __init__(self, data=None, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

def buildTree(i):
    if i < len(values):
        return Node(values[i], left=buildTree((i+1)*2-1), right=buildTree((i+1)*2))

values = [1,2,3,4,5,6,7]
tree = buildTree(0)

要打印出树，我们可以使用 preorder tree traversal :

def preorder(node):
    if node is None:
        return
    yield node.data
    for v in preorder(node.left):
        yield v
    for v in preorder(node.right):
        yield v

像这样:

>>> print list(preorder(tree))
[1, 2, 4, 5, 3, 6, 7]