Python 中樹的中序遍歷
樹是一種分層資料結構，由由邊連線的節點組成。遍歷樹意味著只訪問樹的每個節點一次。
我們出於不同目的遍歷樹，例如顯示節點、查詢最大和最小節點、搜尋、排序等。在本文中，我們將學習和實現 Python 中的 inorder 遍歷樹。
樹的中序遍歷
Inorder 遍歷是一種深度優先遍歷。假設我們有以下樹。
如果我們應用 inorder 遍歷，我們將對每個節點執行以下步驟。
- 首先，我們應該訪問左子樹的所有節點。
- 然後，我們訪問父節點。
- 然後，我們訪問右子樹中的所有節點。
我們將按照 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
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