algo04 树与二叉树 — exercise.py 练习指南

练习目标

通过四个任务掌握树的遍历、BST 操作、AVL 旋转和哈夫曼编码。

任务清单

任务1：迭代版后序遍历

技巧：后序（左-右-根）= 反序（根-右-左）。用一个栈先做根-右-左，然后反转。

标准后序: 4, 5, 2, 3, 1
根右左:   1, 3, 2, 5, 4
→ 反转即可!

任务2：BST 插入和查找

insert: 从根出发，根据比较结果左转或右转，直到找到空位。 search: 同样逻辑，找到匹配值或抵达 None。

任务3：AVL 旋转

右旋（LL）：y 是失衡节点，x = y.left，T3 = x.right。旋转后 x 成为新的根。

左旋（RR）：x 是失衡节点，y = x.right，T2 = y.left。旋转后 y 成为新的根。

任务4（Bonus）：哈夫曼编解码

编码：频率统计 → 优先队列合并 → DFS 生成编码表 → 逐字符编码。解码：反转编码表，从编码串头部开始匹配。

验证

bash

cd algo04_tree_binarytree/code
python exercise.py

预期全部通过，并展示哈夫曼编码的压缩效果。

完整代码

# -*- coding: utf-8 -*-
"""
===============================================================================
algo04_tree_binarytree/code/exercise.py — 树与二叉树练习
===============================================================================
练习目标：
  1. 实现二叉树的中序和后序遍历（迭代版）
  2. 实现 BST 的插入和查找操作
  3. 实现 AVL 树的右旋和左旋操作
  4. 实现哈夫曼编码的完整编码/解码

运行方式：python exercise.py
===============================================================================
"""


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


# ============================================================================
# 任务 1：迭代版后序遍历
# ============================================================================

def postorder_iterative(root):
    """后序遍历（迭代）—— 使用栈

    思路：使用两个栈，或者用一个栈 + 记录 last_visited
    技巧：后序遍历的逆序 = 根→右→左 的逆序
    """
    # TODO: 实现迭代版后序遍历
    if not root:
        return []
    result = []
    stack = [root]
    # 先做 根→右→左 的遍历，然后反转
    while stack:
        node = stack.pop()
        result.append(node.val)
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)
    # 反转得到 左→右→根
    return result[::-1]


# ============================================================================
# 任务 2：实现 BST 的插入和查找
# ============================================================================

class BST:
    def __init__(self):
        self.root = None

    # TODO: 实现 insert 方法（迭代版）
    def insert(self, val):
        if not self.root:
            self.root = TreeNode(val)
            return
        cur = self.root
        while True:
            if val < cur.val:
                if not cur.left:
                    cur.left = TreeNode(val)
                    return
                cur = cur.left
            else:
                if not cur.right:
                    cur.right = TreeNode(val)
                    return
                cur = cur.right

    # TODO: 实现 search 方法
    def search(self, val):
        cur = self.root
        while cur:
            if val == cur.val:
                return True
            elif val < cur.val:
                cur = cur.left
            else:
                cur = cur.right
        return False

    def inorder(self):
        result = []
        def dfs(node):
            if not node: return
            dfs(node.left)
            result.append(node.val)
            dfs(node.right)
        dfs(self.root)
        return result


# ============================================================================
# 任务 3（Bonus）：AVL 树的旋转
# ============================================================================

class AVLNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.height = 1


def get_height(node):
    return node.height if node else 0


def update_height(node):
    node.height = 1 + max(get_height(node.left), get_height(node.right))


# TODO: 实现右旋（LL 旋转）
def rotate_right(y):
    r"""
       y              x
      / \            / \
     x   T4   ->    z    y
    / \                / \
   z   T3            T3  T4
   图示：y 的平衡因子 = 2，x 的平衡因子 = 1（LL 情况）
   """
    # TODO: 你的代码
    x = y.left
    T3 = x.right
    x.right = y
    y.left = T3
    update_height(y)
    update_height(x)
    return x


# TODO: 实现左旋（RR 旋转）
def rotate_left(x):
    r"""
   x                y
  / \              / \
 T1  y     ->     x    z
    / \         / \
   T2  z       T1 T2
   图示：x 的平衡因子 = -2，y 的平衡因子 = -1（RR 情况）
   """
    # TODO: 你的代码
    y = x.right
    T2 = y.left
    y.left = x
    x.right = T2
    update_height(x)
    update_height(y)
    return y


# ============================================================================
# 任务 4：哈夫曼编解码
# ============================================================================

import heapq


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

    def __lt__(self, other):
        return self.freq < other.freq


def huffman_encode(text):
    """哈夫曼编码：返回 (编码后的二进制串, 编码表)"""
    # 统计频率
    freq = {}
    for ch in text:
        freq[ch] = freq.get(ch, 0) + 1

    # 构建哈夫曼树
    # TODO: 你的代码 —— 使用优先队列合并节点
    heap = [HuffmanNode(ch, f) for ch, f in freq.items()]
    heapq.heapify(heap)
    while len(heap) > 1:
        left = heapq.heappop(heap)
        right = heapq.heappop(heap)
        merged = HuffmanNode(None, left.freq + right.freq)
        merged.left = left
        merged.right = right
        heapq.heappush(heap, merged)

    root = heap[0]

    # 生成编码表
    # TODO: 你的代码 —— DFS 遍历哈夫曼树生成 0/1 编码
    codes = {}
    def dfs(node, code):
        if not node: return
        if node.char is not None:
            codes[node.char] = code
            return
        dfs(node.left, code + '0')
        dfs(node.right, code + '1')
    dfs(root, '')

    # 编码
    encoded = ''.join(codes[ch] for ch in text)
    return encoded, codes


def huffman_decode(encoded, codes):
    """哈夫曼解码 —— 根据编码表还原原文"""
    # 反转编码表：code → char
    # TODO: 你的代码
    reverse_codes = {code: char for char, code in codes.items()}
    result = []
    current = ''
    for bit in encoded:
        current += bit
        if current in reverse_codes:
            result.append(reverse_codes[current])
            current = ''
    return ''.join(result)


# ============================================================================
# 主函数
# ============================================================================

def main():
    print('=' * 60)
    print('  树与二叉树 — 练习程序')
    print('=' * 60)

    # 测试任务 1
    print('\n--- 任务 1：迭代版后序遍历 ---')
    root = TreeNode(1)
    root.left = TreeNode(2); root.right = TreeNode(3)
    root.left.left = TreeNode(4); root.left.right = TreeNode(5)
    post = postorder_iterative(root)
    print(f'后序: {post}')
    assert post == [4, 5, 2, 3, 1]
    print('✅ 任务 1 通过！')

    # 测试任务 2
    print('\n--- 任务 2：BST ---')
    bst = BST()
    for v in [5, 3, 7, 2, 4, 6, 8]:
        bst.insert(v)
    print(f'BST 中序: {bst.inorder()}')
    assert bst.search(4) and bst.search(7) and not bst.search(99)
    print('✅ 任务 2 通过！')

    # 测试任务 3
    print('\n--- 任务 3：AVL 旋转 ---')
    # 构建 LL 情况
    y = AVLNode(30); y.left = AVLNode(20); y.left.left = AVLNode(10)
    y.height = 3; y.left.height = 2
    new_root = rotate_right(y)
    print(f'右旋后: root={new_root.val}, left={new_root.left.val}, right={new_root.right.val}')
    assert new_root.val == 20
    print('✅ 任务 3 通过！')

    # 测试任务 4
    print('\n--- 任务 4：哈夫曼编解码 ---')
    text = "ABRACADABRA"
    encoded, codes = huffman_encode(text)
    decoded = huffman_decode(encoded, codes)
    print(f'原文: {text}')
    print(f'编码表: {codes}')
    print(f'编码: {encoded} (长度: {len(encoded)} bits)')
    print(f'解码: {decoded}')
    assert decoded == text
    print(f'原始大小: {len(text) * 8} bits, 压缩后: {len(encoded)} bits, 压缩率: {len(encoded)/(len(text)*8)*100:.1f}%')
    print('✅ 任务 4 通过！')

    print('\n🎉 所有练习已完成！')


if __name__ == '__main__':
    main()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286

algo04 树与二叉树 — exercise.py 练习指南 ​

练习目标 ​

任务清单 ​

任务1：迭代版后序遍历 ​

任务2：BST 插入和查找 ​

任务3：AVL 旋转 ​

任务4（Bonus）：哈夫曼编解码 ​

验证 ​

完整代码 ​