notebook

深色模式

WARNING

🧪 Beta公测版本提示：教程主体已完成，正在优化细节，欢迎大家提Issue反馈问题或建议。

algo04 树与二叉树 — demo.py 代码详解 ​

Download demo.py

运行方式 ​

bash
cd docs/algorithms/basics/tree/code
python demo.py

代码结构 ​

类/函数功能关键算法
preorder/inorder/postorder_recursive递归遍历DFS
inorder_iterative迭代中序遍历栈模拟递归
morris_inorderO(1) 空间中序遍历利用空指针建回链
BST二叉搜索树插入/查找/删除
AVLTree自平衡 BSTLL/RR/LR/RL 旋转
build_huffman_tree + generate_huffman_codes哈夫曼编码贪心 + 优先队列

第1步：Morris 遍历的核心技巧 ​

python
if not pre.right:
    pre.right = cur      # 建立"回链"
    cur = cur.left
else:
    pre.right = None     # 断开"回链"，访问 cur
    result.append(cur.val)
    cur = cur.right

直觉：利用叶子节点空闲的 right 指针，指向中序后继，从而在不使用栈的情况下实现回溯。

第2步：BST 删除的三种情况 ​

情况 1（叶节点）:  直接删除，父节点的引用设为 None
情况 2（一个子节点）: 用子节点替代当前节点
情况 3（两个子节点）: 用后继（右子树的最小值）替换值，然后删除后继

第3步：AVL 树的四种旋转 ​

旋转平衡因子模式操作
LLnode.bf=2, left.bf=1右旋一次
RRnode.bf=-2, right.bf=-1左旋一次
LRnode.bf=2, left.bf=-1先左旋左子，再右旋
RLnode.bf=-2, right.bf=1先右旋右子，再左旋

第4步：哈夫曼树的贪心证明（直觉） ​

哈夫曼算法的高明之处在于它每次取最小的两个频率合并。为什么这是最优的？

交换论证：假设最优树中频率最小的两个字符不是兄弟，我们可以将它们与最深层的两个兄弟交换（因为最深层的频率一定不大于最优树中任何节点的频率），交换后的树总代价不增加。因此，最小频率的两个字符一定在最优树的最深层且互为兄弟——这正是哈夫曼算法做的。

关键概念速查表 ​

遍历顺序递归迭代应用
先序根-左-右O(n), O(h)空间栈序列化、前缀表达式
中序左-根-右O(n), O(h)空间栈/MorrisBST 有序输出
后序左-右-根O(n), O(h)空间双栈计算子树大小、后缀表达式
层序逐层从左到右-队列 O(n), O(w)空间BFS、最短路径

源码位置 ​

clone 后打开（相对仓库根目录）：

docs/algorithms/basics/tree/code/demo.py