Python 中樹的中序遍歷

Fariba Laiq 2023年1月30日 2022年7月18日
  1. 樹的中序遍歷
  2. Python 中的中序樹遍歷實現
Python 中樹的中序遍歷

樹是一種分層資料結構,由由邊連線的節點組成。遍歷樹意味著只訪問樹的每個節點一次。

我們出於不同目的遍歷樹,例如顯示節點、查詢最大和最小節點、搜尋、排序等。在本文中,我們將學習和實現 Python 中的 inorder 遍歷樹。

樹的中序遍歷

Inorder 遍歷是一種深度優先遍歷。假設我們有以下樹。

二叉樹

如果我們應用 inorder 遍歷,我們將對每個節點執行以下步驟。

  1. 首先,我們應該訪問左子樹的所有節點。
  2. 然後,我們訪問父節點。
  3. 然後,我們訪問右子樹中的所有節點。

我們將按照 4, 2, 5, 1, 6, 3, 7 的順序獲取節點。

Python 中的中序樹遍歷實現

有兩種方法可以在 Python 中實現 inorder 遍歷。遞迴和迭代方法。

遞迴方法

遞迴方法易於實現和理解。在下面的程式碼中,我們建立了一個類 Node 作為儲存樹的資料結構。

每個節點由一個值、它的左子節點和右子節點組成。inorder 遍歷將遞迴地為左右子樹工作。

對於每個節點,將通過訪問其左節點、父節點和右節點來執行 inorder 遍歷。

示例程式碼:

class Node:
    def __init__(self, value):
        self.left = None
        self.right = None
        self.val = value
def inorder(root):
    if root:
        inorder(root.left)
        print(str(root.val))
        inorder(root.right)
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
print("Inorder traversal of the Tree")
inorder(root)

輸出:

Inorder traversal of the Tree
4
2
5
1
6
3
7

迭代方法

在迭代方法中,我們必須維護一個 stack 來儲存我們稍後將訪問的節點。我們在下面的程式碼中建立了類 Node,就像以前一樣。

我們建立了一個空堆疊,並通過將其設為當前節點從根節點開始。如果當前節點存在,我們會將其壓入棧中,並轉到其左側節點。

否則,如果節點不存在,我們將從堆疊中彈出一個元素並列印它。當不存在左節點時,我們將通過使其成為當前節點來轉到右節點。

我們將迭代地重複相同的過程,直到堆疊和當前元素都為空。

示例程式碼:

from collections import deque
class Node:
    def __init__(self, value):
        self.left = None
        self.right = None
        self.val = value
def inorder(root):
    stack = deque()
    curr = root
    while stack or curr:
        if curr:
            stack.append(curr)
            curr = curr.left
        else:
            curr = stack.pop()
            print(curr.val)
            curr = curr.right
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
print("Inorder traversal of the Tree")
inorder(root)

輸出:

Inorder traversal of the Tree
4
2
5
1
6
3
7
Author: Fariba Laiq
Fariba Laiq avatar Fariba Laiq avatar

I am Fariba Laiq from Pakistan. An android app developer, technical content writer, and coding instructor. Writing has always been one of my passions. I love to learn, implement and convey my knowledge to others.

LinkedIn