在 Python 中實現樹資料結構

1. 在 Python 中從頭開實現樹資料結構
2. 在 Python 中遍歷二叉樹
3. 使用 Python 庫實現樹

樹是資料結構之一。資料結構只是我們如何組織記憶體中的資料。樹是節點（也稱為頂點）和邊的組合。一棵樹可以有任意數量的節點和邊。一個節點是我們儲存資料的位置，一條邊是 2 節點之間的路徑。有多種型別的樹可用，例如二叉樹，三叉樹，二叉搜尋樹，AVL 樹等。

樹中節點的型別：

1. 父節點：具有一個或多個子節點的節點。
2. 子節點：具有父節點的節點。
3. 葉子節點：沒有任何子節點的節點。

在本文中，我們首先來看如何在不使用任何庫的情況下從頭開始實現樹，然後再看如何在 Python 庫的幫助下實現樹。

在 Python 中從頭開實現樹資料結構

要在 Python 中建立樹，我們首先必須建立一個表示單個節點的 Node 類。Node 類將包含 3 個變數；第一個是指向左側子節點的 left 變數，第二個變數是包含該節點值的 data 變數，而第二個變數是指向右側子節點的 right 變數。

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

讓我們初始化一棵樹。

root = Node(10)

root.left = Node(34)
root.right = Node(89)
root.left.left = Node(45)
root.left.right = Node(50)

這棵樹如下圖所示。

          10
        /    \
       34      89
     /    \ 
    45    50 

每當建立 Node 類的物件時，都會呼叫 __init__ 建構函式，並且該建構函式中的所有變數都將被初始化。root 包含樹的根節點，該節點的值為 10，以及 root.left 和 root.right，我們將使用其插入值 34 的左側子節點和右側的子節點。子節點到根節點，其值為 89。由於它是二叉樹，因此每個節點最多包含兩個節點。

最後，我們在樹中再插入兩個節點，即 45 和 50，作為節點 34 的子節點。你可以根據要建立的樹的型別在樹內插入任意數量的節點。

在 Python 中遍歷二叉樹

現在我們已經建立了一棵樹，所以讓我們遍歷該樹以列印樹元素。遍歷訪問樹中的每個節點。遍歷遍歷樹中的每個節點三次。我們遍歷樹的方式是從上到下，從左到右。

前序遍歷

在前序遍歷樹時，每當我們第一次看到該節點時，我們都會列印該節點，然後在左節點然後在右節點上執行遞迴。

def preorder(node):
    if node:
        print(node.data)
        preorder(node.left)
        preorder(node.right)

輸出：

10 
34 
45 
50 
89

中序遍歷

在執行中序遍歷時，我們首先在左側節點上執行遞迴，然後在第二次訪問同一節點時，列印該節點。然後，我們在右節點上執行遞迴。

def inorder(node):
    if node:
        inorder(node.left)
        print(node.data)
        inorder(node.right)

輸出：

45 
34 
50 
10 
89

後序遍歷

對於後序遍歷，我們在左節點和右節點上執行遞迴，然後當我們第三次訪問同一節點時，我們將列印該節點。

def postorder(node):
    if node:
        postorder(node.left)
        postorder(node.right)
        print(node.data)

輸出：

45
50
34
89
10

使用 Python 庫實現樹

如我們所見，從頭開始實現樹需要花費一些時間，並且需要大量程式碼。在 Python 中實現樹的更簡單方法是使用名為 anytree 的庫。anytree 庫使你無需編寫大量程式碼即可建立樹。

要使用 anytree 庫，我們首先必須在以下命令的幫助下進行安裝。

pip install anytree

在這裡，我們還將建立與先前建立的樹相同的樹。現在我們可以從 anytree 庫中匯入 Node 和 RenderTree。

from anytree import Node, RenderTree

root = Node(10)

level_1_child_1 = Node(34, parent=root)
level_1_child_2 = Node(89, parent=root)
level_2_child_1 = Node(45, parent=level_1_child_1)
level_2_child_2 = Node(50, parent=level_1_child_2)

for pre, fill, node in RenderTree(root):
    print("%s%s" % (pre, node.name))

# Tree Structure
#          10
#        /    \
#       34      89
#     /    \
#    45    50

輸出：

10
├── 34
│   └── 45
└── 89
    └── 50

在這裡，Node 將為我們建立一個帶有兩個引數的節點：第一個是節點的值，第二個是父節點的名稱（這是一個可選引數）。由於在我們的樹中，root 節點是唯一沒有任何父節點的節點，因此在建立 root 節點時，我們將僅傳遞第一個引數：節點的值，而不傳遞第二個引數。RenderTree 方法將幫助我們如輸出所示列印整個樹。