Python怎么實現二叉樹的遍歷

Python怎么實現二叉樹的遍歷

二叉樹是一種常見的數據結構，廣泛應用于算法和數據處理中。二叉樹的遍歷是指按照某種順序訪問樹中的所有節點。常見的遍歷方式包括前序遍歷、中序遍歷、后序遍歷和層次遍歷。本文將介紹如何使用Python實現這些遍歷方式。

1. 二叉樹的定義

首先，我們需要定義一個二叉樹的節點類。每個節點包含一個值以及指向左子樹和右子樹的指針。

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

2. 前序遍歷

前序遍歷的順序是：根節點 -> 左子樹 -> 右子樹。我們可以使用遞歸或棧來實現前序遍歷。

遞歸實現

def preorder_traversal(root):
    if root is None:
        return []
    return [root.value] + preorder_traversal(root.left) + preorder_traversal(root.right)

棧實現

def preorder_traversal_stack(root):
    if root is None:
        return []
    stack, result = [root], []
    while stack:
        node = stack.pop()
        result.append(node.value)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    return result

3. 中序遍歷

中序遍歷的順序是：左子樹 -> 根節點 -> 右子樹。同樣可以使用遞歸或棧來實現。

遞歸實現

def inorder_traversal(root):
    if root is None:
        return []
    return inorder_traversal(root.left) + [root.value] + inorder_traversal(root.right)

棧實現

def inorder_traversal_stack(root):
    stack, result = [], []
    current = root
    while current or stack:
        while current:
            stack.append(current)
            current = current.left
        current = stack.pop()
        result.append(current.value)
        current = current.right
    return result

4. 后序遍歷

后序遍歷的順序是：左子樹 -> 右子樹 -> 根節點。遞歸和棧的實現方式如下。

遞歸實現

def postorder_traversal(root):
    if root is None:
        return []
    return postorder_traversal(root.left) + postorder_traversal(root.right) + [root.value]

棧實現

def postorder_traversal_stack(root):
    if root is None:
        return []
    stack, result = [root], []
    while stack:
        node = stack.pop()
        result.append(node.value)
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)
    return result[::-1]

5. 層次遍歷

層次遍歷是按照樹的層次從上到下、從左到右依次訪問節點。通常使用隊列來實現。

from collections import deque

def level_order_traversal(root):
    if root is None:
        return []
    queue, result = deque([root]), []
    while queue:
        node = queue.popleft()
        result.append(node.value)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    return result

6. 總結

本文介紹了如何使用Python實現二叉樹的四種常見遍歷方式：前序遍歷、中序遍歷、后序遍歷和層次遍歷。每種遍歷方式都有遞歸和迭代兩種實現方法，開發者可以根據具體需求選擇合適的方式。掌握這些遍歷方法對于理解和應用二叉樹結構至關重要。