Python實現遍歷樹形結構的方法

一、什麼是樹形結構

樹是一種抽象的數據結構，它是由n（n>=1）個有限節點組成一個具有層次關係的集合。其中，一個節點被稱作根節點，每個節點至多有一個父節點，但卻可以有多個子節點（允許為空）。

樹形結構非常適合用來表示具有層次關係的數據，比如文件系統的目錄結構，公司組織架構等。在實際應用中，經常需要對樹形結構進行遍歷、查找等操作。

Python中可以使用類來定義一個節點，並在節點類中定義各種方法，以實現樹形結構的操作。下面我們來看看如何實現樹的遍歷操作。

二、樹的遍歷方式

在對樹形結構進行操作時，遍歷是最基本的操作之一。遍歷樹就是按照一定的順序，依次訪問每個節點及其包含的所有子節點。常用的樹的遍歷方式有以下三種：

• 先序遍歷（前序遍歷）：先遍歷根節點，再遞歸遍歷左子樹和右子樹。
• 中序遍歷：先遞歸遍歷左子樹，再遍歷根節點，最後遞歸遍歷右子樹。
• 後序遍歷：先遞歸遍歷左子樹，再遞歸遍歷右子樹，最後遍歷根節點。

通過深度優先搜索演算法，可以實現樹的遍歷。接下來我們將給出Python代碼，實現深度優先搜索演算法，實現三種遍歷方式的操作。

三、先序、中序、後序遍歷的實現

# 定義一個節點類
class Node:
    def __init__(self, val=None, left=None, right=None):
        self.val = val  # 節點的值
        self.left = left  # 左子樹
        self.right = right  # 右子樹

# 先序遍歷
def preorder(root):
    if not root:
        return []
    res = []
    res.append(root.val)
    res += preorder(root.left)
    res += preorder(root.right)
    return res

# 中序遍歷
def inorder(root):
    if not root:
        return []
    res = []
    res += inorder(root.left)
    res.append(root.val)
    res += inorder(root.right)
    return res

# 後序遍歷
def postorder(root):
    if not root:
        return []
    res = []
    res += postorder(root.left)
    res += postorder(root.right)
    res.append(root.val)
    return res

# 測試代碼
root = Node(1, Node(2, Node(4), Node(5)), Node(3, Node(6), Node(7)))
print("先序遍歷：", preorder(root))  # [1, 2, 4, 5, 3, 6, 7]
print("中序遍歷：", inorder(root))   # [4, 2, 5, 1, 6, 3, 7]
print("後序遍歷：", postorder(root)) # [4, 5, 2, 6, 7, 3, 1]

四、層序遍歷的實現

層序遍歷（又稱廣度優先遍歷）是指在按照樹的層次依次遍歷樹中各節點的過程中，按照先遍歷當前層節點，再遍歷下一層節點的順序依次進行。

下面給出Python代碼實現：

# 層序遍歷
def levelorder(root):
    queue = [root]
    res = []
    if not root:
        return []
    while queue:
        level = []  # 保存當前層的節點值
        size = len(queue)  # 當前層的節點數
        for i in range(size):
            node = queue.pop(0)
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        res.append(level)
    return res

# 測試代碼
root = Node(1, Node(2, Node(4), Node(5)), Node(3, Node(6), Node(7)))
print("層序遍歷：", levelorder(root)) # [[1], [2, 3], [4, 5, 6, 7]]

五、對樹進行查找

樹的查找操作，常用的是深度優先搜索和廣度優先搜索演算法。在深度優先搜索演算法中，常用的是先序遍歷，因為先序遍歷先訪問根節點。廣度優先搜索中常用的是層序遍歷，因為層序遍歷是按層遍歷節點的，很容易找到需要的節點。

下面給出一個例子，使用深度優先搜索演算法，在樹中查找是否有某一個節點值為val。

# 深度優先搜索查找樹中是否有節點值為val
def dfs(root, val):
    if not root:
        return False
    if root.val == val:
        return True
    return dfs(root.left, val) or dfs(root.right, val)

# 測試代碼
root = Node(1, Node(2, Node(4), Node(5)), Node(3, Node(6), Node(7)))
print("查找節點5：", dfs(root, 5)) # True
print("查找節點8：", dfs(root, 8)) # False

六、總結

樹形結構在現實中應用非常廣泛，比如文件系統、公司架構、數據結構中的優先隊列等等。本文主要介紹了樹的遍歷方式，包括先序遍歷、中序遍歷、後序遍歷和層序遍歷，以及深度優先遍歷查找操作。通過Python代碼的實現，我們可以更好地理解樹的遍歷、查找等操作。