Python 二叉樹

一、什麼是二叉樹

二叉樹是一種數據結構，它由節點組成，每個節點最多有兩個子節點。節點有一個稱為「根」的特殊節點，它是整個樹的起點。每個節點都有一個有向邊連接到其子節點。如果沒有子節點，則稱該節點為「葉子節點」。根據節點的排列方式，二叉樹可以分為以下幾種類型：

• 滿二叉樹：每個節點都有兩個子節點，除了葉子節點外
• 完全二叉樹：不一定每個節點都有兩個子節點，但是任何缺失子節點的節點都必須在右邊的子樹中

class Node:
    def __init__(self, val):
        self.left = None
        self.right = None
        self.val = val

二、二叉樹的遍歷

二叉樹的遍歷是指按照一定方法遍歷二叉樹節點的過程。常用的遍歷方法有前序遍歷、中序遍歷和後序遍歷。

• 前序遍歷：根節點->左子樹->右子樹
• 中序遍歷：左子樹->根節點->右子樹
• 後序遍歷：左子樹->右子樹->根節點

class BinaryTree:
    def __init__(self, val):
        self.left = None
        self.right = None
        self.val = val

    def preorderTraversal(self, root):
        res = []
        if root:
            res.append(root.val)
            res += self.preorderTraversal(root.left)
            res += self.preorderTraversal(root.right)
        return res

    def inorderTraversal(self, root):
        res = []
        if root:
            res += self.inorderTraversal(root.left)
            res.append(root.val)
            res += self.inorderTraversal(root.right)
        return res

    def postorderTraversal(self, root):
        res = []
        if root:
            res += self.postorderTraversal(root.left)
            res += self.postorderTraversal(root.right)
            res.append(root.val)
        return res

三、二叉樹的應用

1.表達式樹

表達式樹是一種二叉樹，其中每個葉節點都是一個操作數，而其他節點都是操作符。通過遍歷表達式樹，可以實現對表達式的計算。

class ExpressionTree:
    def __init__(self, val):
        self.left = None
        self.right = None
        self.val = val

    def evaluate(self):
        if self.val.isdigit():
            return int(self.val)
        else:
            left_val = self.left.evaluate()
            right_val = self.right.evaluate()
            if self.val == '+':
                return left_val + right_val
            elif self.val == '-':
                return left_val - right_val
            elif self.val == '*':
                return left_val * right_val
            else:
                return left_val / right_val

2.哈夫曼樹

哈夫曼樹是一種特殊的樹，其中有權重的葉子節點表示字元，並且具有最小的路徑權重和。哈夫曼樹經常用於編碼和解碼數據。

class HuffmanTree:
    def __init__(self, freq, left=None, right=None):
        self.freq = freq
        self.left = left
        self.right = right

    def __lt__(self, other):
        return self.freq  1:
            freq1, tree1 = heapq.heappop(heap)
            freq2, tree2 = heapq.heappop(heap)
            heapq.heappush(heap, (freq1 + freq2, HuffmanTree(freq1 + freq2, tree1, tree2)))
        return heap[0][1]

四、總結

Python 二叉樹是一種重要的數據結構，在計算機科學領域有廣泛的應用。我們可以用它來遍歷樹、求解表達式、以及構建哈夫曼樹等。掌握這些知識可以更好地理解和解決許多計算機科學問題。