在 Python 中實現樹資料結構

Sahil Bhosale 2023年1月30日 2021年3月21日
  1. 在 Python 中從頭開實現樹資料結構
  2. 在 Python 中遍歷二叉樹
  3. 使用 Python 庫實現樹
在 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 方法將幫助我們如輸出所示列印整個樹。

Sahil Bhosale avatar Sahil Bhosale avatar

Sahil is a full-stack developer who loves to build software. He likes to share his knowledge by writing technical articles and helping clients by working with them as freelance software engineer and technical writer on Upwork.

LinkedIn

相關文章 - Python Data Structure