将树表示为 python 中的列表

Question

我正在学习 python，我很好奇人们如何选择在 python 中存储（二叉）树。

在python中将树的节点存储为列表是否有问题？类似于：

[0,1,2,3,4,5,6,7,8]

其中第0个位置默认为0，1为根，对于每个位置(i)，第2i和2i+1个位置为children。当没有 child 存在时，我们在该位置只有一个 'None'。

我读过一些 books/notes，它们使用列表的列表表示一棵树，或者比像这样的简单列表更复杂的东西，我想知道是否存在固有的错误我怎么看？

Answer 1

按照您的方式将二叉树存储为列表并没有错 - 这与使用 C 或 Java 等语言将其存储为平面数组的想法相同。访问给定节点的父节点非常快，查找子节点也非常高效。

我想很多示例和教程更喜欢使用 'really tree shaped'（列表或对象的列表）的表示形式 - 解释起来可能更直观一些。

Answer 2

你当然可以做到这一点。我将其定义为 class 派生自具有 get_children 方法的列表。然而，这是相当丑陋的，因为要么 A) 你必须在 O(n) 时间内预处理整个列表以将索引与值配对，要么 B) 你必须在 O(n log n ) 遍历树的时间。

class WeirdBinaryTreeA(list):
    def __init__(self, *args, **kwargs):
        super().__init__(*args, **kwargs)

    def get_children(value):
        """Calls list.index on value to derive the children"""
        idx = self.index(value)  # O(n) once, O(n log n) to traverse
        return self[idx * 2], self[idx * 2 + 1]


class WeirdBinaryTreeB(list):
    def __init__(self, *args, **kwargs):
        super().__init__(*args, **kwargs)
        self.__mapping = self.processtree()

    def processtree(self):
        for idx, val in enumerate(self):
            self.__mapping[val] = idx

    def get_children(value):
        """Queries the mapping on value to derive the children"""
        idx = self.__mapping[value]  # O(1) once, O(n) to traverse
        return self[idx * 2], self[idx * 2 + 1]

然而更大的问题是为什么你会这样做？是什么让它比列表的列表或字典的字典更好？当你拥有时会发生什么：

您的列表如下所示：

[0, 'A', None, 'B', None, None, None, 'C', None, None, None, None, None, None, None, 'D', ...]

而不是：

{"A": {"B": {"C": {"D": {"E": {"F": None}}}}}}

Answer 3

我在 C 代码中看到过这样的表示（您的平面 list/array），并且在 Python 中也可以接受这样的表示，但这取决于数据的性质你在处理在 C 代码中，此列表表示中的平衡树可以非常快速地访问（比导航一系列指针快得多），尽管由于所有其他开销，Python 中的性能优势可能不太明显。

对于合理平衡的密集树，这种平面列表方法是合理的。然而，正如 Adam Smith 评论的那样，这种类型的平面列表树对于不平衡的稀疏树来说会变得非常浪费。假设你有一个分支只有一个 children 向下一百层，而树的其余部分什么都没有。您将需要 2^100 + 2^99 + 2^98 + ... + 2^1 + 平面列表树中的 1 个位置。对于这种情况，您将耗尽大量内存来存储可以使用嵌套列表更有效地表示的内容。

所以本质上，平面列表树与嵌套列表树之间的选择类似于类 C 语言中平面数组树与基于指针的树之间的选择。

将树表示为 python 中的列表

representing a tree as a list in python

python

binary-tree