在Python中使用类和字典来表示二叉树有什么区别？

Question

这个类代表树中的一个节点。我已经链接它的实例来生成一棵如下所示的树：

class Node:
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = None
        self.right = None

# Chaining the nodes to represent a tree
root = Node(1)
child1 = Node(2, Node(4), Node(5))
child2 = Node(3)
root.left = child1
root.right = child2

这也可以通过使用字典来表示为图形：

tree = {1: [2, 3], 2: [4, 5], 3: [], 4: [], 5: []}

我假设列表中的第一个元素是左节点，第二个元素是右节点。

然而，我遇到的所有博客和书籍都使用树类和图字典。我只是想知道其中的原因。

Answer 1

当您有一棵树时，您通常只想跟踪根节点（不需要随机访问节点）。当每个节点都有固定数量的子节点时，这种类型的数据结构很方便，例如：BST、段树、二叉堆、Trie 等。

当你有一个图时，你通常希望能够随机访问任何节点，而使用链表之类的结构是不可能的。所以你最好使用邻接表。