如何使用python将二叉树表示成数组？

Question

我想使用 Python 将二叉树转换为数组，但我不知道如何为树节点提供索引？

我已经使用公式 left_son=(2*p)+1; 和 right_son=(2*p)+2; 在java中但我被困在python中。是否有任何函数可以为 python 中的树节点提供索引？

Answer 1

您可以以完全相同的方式将 Python 中的二叉树表示为一维列表。

例如，如果您将 at 树表示为：

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 14, 15]

0是根
1&2是下一级&
的孩子是和12[3, 4][5, 6]

这对应于您的公式。对于索引处的给定节点i，该节点的子节点是(2*i)+1 (2*i)+2。这是对堆建模的常用方法。您可以在其 [heapq 库] 中阅读有关 Python 如何使用它的更多信息。（https://docs.python.org/3.0/library/heapq.html）

您可以使用它来深入遍历树，例如：

a =  [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 14, 15]

def childNodes(i):
     return (2*i)+1, (2*i)+2

def traversed(a, i=0, d = 0):
    if i >= len(a):
        return 
    l, r =  childNodes(i)
    traversed(a, r, d = d+1)
    print("   "*d + str(a[i]))
    traversed(a, l, d = d+1)

traversed(a)

这打印

         15
      6
         14
   2
         13
      5
         11
0
         10
      4
         9
   1
         8
      3
         7