使用类和字典来表示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等。

当您有图形时，通常希望能够访问任何节点随机使用像结构这样的链表是不可能的。所以你最好使用邻接表。

Answer 2

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

就语义而言，这并没有太大的区别。主要区别在于每种方法的可用性。

正如您所看到的，字典和对象都可以用来表示二叉树。但是，使用对象为二叉树提供了更加方便和可读的界面。

为什么？我们来看一个例子。假设你有二叉树：

 1 
    /\ 
    2 3 
//\ 
5 7 9 

好吧。现在我们假设我们想要访问树根的正确节点。有了字典，那会是这个样子：

tree[1][1] 

与对象是：

tree.right 

好了，现在让我们说，我们要得到正确的节点，右节点的二叉树的根。换句话说，9。再次，这是怎么会看使用字典：

tree[tree[1][1]][1] 

随着对象将是：

tree.right.right 

你开始明白我的意思？当然，使用字典对于有多个节点的小二叉树看起来可以，但是树越大越需要去，使用字典方法的丑陋和更难以理解。

当您想要开始在二叉树中插入和删除等操作时，字典方法变得更糟。做这样的操作需要你有一个定义良好的根节点。这是繁琐的使用字典，因为它没有一套为了模拟 - 使用对象不同的层次结构：

# insertion 

def insert(key, root, tree): 
    if root is None: 
     return Node(key) 
    elif key < root: 
     tree[root][0] = insert(key, tree[root][0], tree) 
    else: 
     tree[root][1] = insert(key, tree[root][1], tree) 
    return root 

# deletion 

def min_value(node, tree): 
    current = node 
    while tree[current][0] is not None: 
     current = tree[current][0] 
    return current 


def delete(root, key, tree): 
    if root is None: 
     return root 
    if key < root: 
     tree[root][0] = delete(tree[root][0], key, tree) 
    elif key < root: 
     tree[root][1] = delete(tree[root][1], key, tree) 
    else: 
     if tree[root][0] is None: 
      temp = tree[root][1] 
      return temp 
     elif tree[root][1] is None: 
      temp = tree[root][0] 
      return temp 
     temp = min_value(tree[root][1], tree) 
     tree[root] = tree[temp] 
     tree[temp] = tree.pop(root) 
     tree[root][1] = delete(tree[root][1], temp) 
    return root 

上述方法的可读性会更清洁的使用命名的属性，如left，right和key。

因此，总结一下，使用类和字典来表示二叉树有什么区别？不同之处在于代码的可读性，可用性，可维护性和结构。希望我的建议？最后，在字典上使用类是正确的选择。