如何在python中表示二叉树？

Question

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

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

上面那棵树的根是2。None表示分支为空。在

我宁愿在列表中实现这一点。 有没有更好的方法来做到这一点（不用创建类）？在

Answer 1

可以使用平面列表表示二叉树，如here。这种方法的浪费程度取决于你的树的形状。在

我很好奇你为什么坚持不上课。如果要将其包装在一个类中，则可以定义一个干净的API，并对最终用户隐藏实现的细节。在

Answer 2

我的方法是： 数组数组，其中索引为0的项是根项：

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

类可以使一个简单的应用程序变得不必要的复杂，特别是当您处理上面所示的简单树时。在

Answer 3

如果你想表示一个完整的二叉树（即所有节点都有两个子节点，除了叶子），那么你可以使用一个表示树的平面列表。在

可以很容易地确定节点的父节点和两个子节点：

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