使用類和字典來表示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。

因此，總結一下，使用類和字典來表示二叉樹有什麼區別？不同之處在於代碼的可讀性，可用性，可維護性和結構。希望我的建議？最後，在字典上使用類是正確的選擇。