在Python中从给定数据生成二叉树

Question

我想知道怎么把一个列表里的值读入一个二叉树里。

         0
       1   2
     3   4   5
   6   7   8   9

我写了一个节点类，像这样：

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 等等。

Answer 1

对于这样的列表：

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)

Answer 2

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

1. 即使你的三角形是用列表表示的，比如 0 1 2 3 4 5 6 7 8 9，也是可以做到的。

2. 因为看起来这是一个完整的二叉树（假设你的三角形有问题，第三行实际上应该是 3 4 5 6），你可以维护一个 parents 队列，队列的头部是下一个需要孩子的父节点。请注意，我特别不推荐使用递归。

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