通过循环创建二叉树

Question

通过循环创建二叉树

3

我希望可以通过循环来创建二叉树。我知道如何编写一个非常基本的二叉树。

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

我应该如何编写代码？由于我正在使用它来计算所有路径的总和，因此如何在二叉树中导航/迭代：

- user5676791

节点5属于节点2还是3，或者两个都属于？ - juanpa.arrivillaga

1

与此相关。虽然不完全重复，但是该帖子的作者想要自动化创建树的过程。 - Christian Dean

你需要跟踪当前树的高度。 - cs95

@juanpa.arrivillaga 抱歉，我不明白什么是节点。我对二叉树非常陌生。 - user5676791

1

@PoChenLiu 节点 = 树中的一个数字。 - cs95

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- randomir · Accepted Answer

从节点值的列表构建一棵完整的二叉树（不一定是二叉搜索树），假设该列表中的值按级遍历顺序排序。因此，从您的问题生成的列表为：

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

将代表一棵树：

   1 
 2   3
4 5 6 7

请注意，根值位于位置0，其左子节点位于位置1*2-1=1，右子节点位于1*2=2等。一般来说，对于列表中索引为i的节点，其左子节点位于位置(i+1)*2-1，右子节点位于(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)

要打印树形结构，我们可以使用前序遍历：

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]