在 Python 中實現樹資料結構

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

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

Python 中的樹

樹中節點的型別:

  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.leftroot.right,我們將使用其插入值 34 的左側子節點和右側的子節點。子節點到根節點,其值為 89。由於它是二叉樹,因此每個節點最多包含兩個節點。

最後,我們在樹中再插入兩個節點,即 4550,作為節點 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 庫中匯入 NodeRenderTree

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 方法將幫助我們如輸出所示列印整個樹。