用Python从给定数据生成二叉树

Question

我想知道如何将列表中的值读入二叉树中。 我有一个像这样的三角形：

         0
       1   2
     3   4   5
   6   7   8   9

我已经写了一个类似这样的节点类：

class Node { }

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

基本上我想做的是这样的：

node(0,node(1),node(2))

我想要创建一个递归函数，可以处理更大的三角形。能否告诉我应该怎么做？

编辑：很明显二叉树不是解决这个问题的方法。我想找出从顶部到底部的所有不同组合方式。例如 0,1,3,6 0,2,5,8 等等。

- johne

---

这不应该被标记为作业吗？ - Antony Hatchkins

你想制作的函数的列表输入和预期的树形输出是什么？ - ddaa

这看起来像是功能性代码。我会将其大写为Node，以便符合类命名的标准（现在它看起来像一个函数）。问题确切是什么？ - Roman

这个“三角形”是否实际上是一棵二叉树还不清楚，因为您没有显示任何边缘（节点之间的连接）。 7号节点的父节点是哪个？3？4？两个节点都是吗？ 如果两个都是，则这不是一棵树。 - Laurence Gonsalves

我怀疑递归不是这里的正确方法。据我所知，您需要以先进先出的方式处理节点（提示：使用队列）。这也不像是二叉树 - 节点可以有两个父节点。 - MAK

我实际上是在尝试解决一个难题。我的目标是找到从上到下的所有不同组合，比如0,1,3,6 0,2,4,8等。使用二进制列表可能不是做这件事的正确方法，但我想学习如何根据列表创建树形结构。 @劳伦斯，我不知道这一点，谢谢您。 - johne

Answer 1

这听起来像是一道作业题，所以我不会写代码，但是我可以给你一些提示：

1. 即使你的三角形被写成一个列表，比如 0 1 2 3 4 5 6 7 8 9，也可以完成这个任务。

2. 因为它看起来像是一个完全二叉树（假设你的三角形是错误的，第三行实际上应该是 3 4 5 6），你可以维护一个 parents 队列，其头部是下一个需要子节点的父节点。请注意，我特别不建议使用递归。

完全二叉树是指每个非叶节点恰好有两个子节点。如果这不是一个完全二叉树，那么就没有确定性的方法来解释这个问题（因为根据你的图片，节点1和2中的每个节点都可能有1或2个子节点）。

- danben

---

我是这个网站的新手，所以不知道是否禁止在ProjectEuler上寻求谜题帮助，如果是的话，我很抱歉。这个问题的解决方案可以在Pyeuler网站上找到，但我无法理解其中任何内容。三角形的结构让我觉得它可以使用树来解决，所以我想尝试一下我的理论，但最终失败了。 - johne

不，它并没有被禁止。但是你所描述的问题规范似乎有些奇怪。你有链接吗？或者最好能重新检查一下问题陈述并进行修订吗？ - danben

Answer 2

对于这样的列表：

a = 'aBCdef'

下面的程序生成以下结构：

- a -
- B C
B C -
- d e
d e f
e f -

代码（假定输入列表对应于“完整”三角形）：

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

    def __unicode__(self):
        return '%s %s %s' % (
                self.left.data if self.left or '-', 
                self.data, 
                self.right.data if self.right or '-')


nodelist = [Node(c) for c in a]

i,y = 0,1

while True:
    for x in range(y):
        nodelist[i].left = nodelist[i-1] if x!=0 else None
        nodelist[i].right = nodelist[i+1] if x!=y-1 else None
        i+=1
    if i<len(a):
        y+=1
    else:
        break

for n in nodelist:
    print unicode(n)

- Antony Hatchkins