如何用Python表示二叉树？

Question

目前我用以下方式来表示一个二叉树：

[None,2,[None,3,None]]

上面的树以数字2为根节点。None表示这个分支是空的。

我更想用列表来实现这个树。有没有更好的方法可以做到这一点（不想创建类）？

Answer 1

这是我的方法：用一个数组里面再放一个数组，索引为0的那个就是根节点。

[['Level A', 'A1', 'A2'], ['Level B', 'B1', 'B2'], ['Level C', 'C1', 'C2']]

如果使用类来处理这些简单的树结构，可能会让一个简单的应用变得复杂，特别是像上面那样的简单树。

Answer 2

如果你想表示一个完整的二叉树（也就是说，除了叶子节点以外，所有节点都有两个孩子），那么你可以用一个简单的列表来表示这个树。

这样你就可以很容易地找到一个节点的父亲和两个孩子，方法如下：

def leftChild(lst,i):
  try: 
    return lst[i*2]
  except IndexError:
    return None

def rightChild(lst,i):
  try: 
    return lst[i*2+1]
  except IndexError:
    return None

def father(lst,i):
  try:
    return lst[i/2]
  except IndexError:
    return None

Answer 3

可以用一个平坦的列表来表示二叉树，具体的内容可以在这里找到。这个方法的浪费程度取决于你树的形状。

我很好奇你为什么坚持不使用类。如果你把它放在一个类里面，你就可以定义一个简单明了的接口，并把实现的细节隐藏起来，让最终的用户不需要了解这些复杂的内容。