现代编程思想 树 Hongbo Zhang 1 数据结构：树 树 ⼆叉树 ⼆叉搜索树 ⼆叉平衡树 2 ⽣活中的树状图 ⽣活中有很多的数据的结构与⼀颗树相似 谱系图（⼜称，家族树） ⽂件结构 数学表达式 …… 3 树的逻辑结构 数据结构中，树是由有限个节点构成的具有层次关系的集合 节点是存储数据的结构，节点之间存在亲⼦关系：⽗节点和⼦节点 如果树不为空，则它拥有⼀个根节点：根节点没有⽗节点 任何节点不能是⾃⼰的后代节点：树中不能有环路 树的⼀条边指的是⼀对节点(u, v)，其中u是v的⽗节点或者v是u的⽗节点 4 树的逻辑结构 这不是⼀颗树 5 树的逻辑结构 计算机中的树根节点在上，⼦节点在⽗节点下⽅ 相关术语 节点的深度：根节点下到这个节点的路径的⻓度（边的数量） 根节点深度为0 节点的⾼度：节点下到叶节点的最⻓路径的⻓度 叶节点⾼度为0 树的⾼度：根节点的⾼度 只有⼀个节点的树⾼度为0 空树（没有节点的树）⾼度为-1 也有的定义将树的⾼度等同于最⼤层次，以根为第⼀层 6 树的存储结构 树的存储⽅式有多种（以⼆叉树为例，省略节点存储的数据） 节点与⼦节点关系的列表： [ (0, 1), (0, 2), (1, 3) ] 代数数据结构定义 1. Node(0, 2. Node(1, 3. Leaf(3), 4. Empty)

"(1+ 5) * 7 / 2" 转化为单词列表 LParen Value(1) Plus Value(5) Multiply Value(7) Divide Value(2) 转化为抽象语法树 Division(Multiply(Add(Value(1), Value(5)), Value(7)), Value(2)) 计算最终结果：21 语法分析 对输⼊⽂本进⾏分析并确定其语法结构 我们成功地分割了字符串 - 10123 - + - 523 103 ( 5 ) ) 但这不符合数学表达式的语法 13 语法分析 对单词流进⾏分析，判断是否符合语法 输⼊：单词流 输出：抽象语法树 1. expression = Value / "(" expression ")" 2. expression =/ expression "+" expression / expression List[Token])] { ... } 12. 13. // 返回函数代表的解析器 14. Parser(expression) 15. } 21 语法树之外：Tagless Final 计算表达式，除了⽣成为抽象语法树再解析，我们还可以有其他的选择 我们通过�⾏为�来进⾏抽象 1. trait Expr { 2. number(Int) -> Self 3. op_add(Self

哈希表与闭包 Hongbo Zhang 1 回顾 表 键值对的集合，其中键不重复 简单实现：⼆元组列表 添加时向队⾸添加 查询时从队⾸遍历 树实现：⼆叉平衡树 基于第五节课介绍的⼆叉平衡树，每个节点的数据为键值对 对树操作时⽐较第⼀个参数 2 哈希表 哈希函数/散列函数 Hash function 将任意⻓度的数据映射到某⼀固定⻓度的数据 在⽉兔的 Hash 接⼝中，数据被映射到整数范围内 value = a[ index ] // 查询 理想情况下，操作均为常数时间（⼆叉平衡树操作均为对数时间） 3 哈希冲突 根据抽屉原理/鸽巢原理/⽣⽇问题 不同数据的哈希可能相同 不同的哈希映射为数组索引时可能相同 解决哈希表的冲突 直接寻址（分离链接）：同⼀索引下⽤另⼀数据结构存储 列表 ⼆叉平衡搜索树等 开放寻址 线性探查：当发现冲突后，索引递增，直到查找空位放⼊ ⼆次探查（索引递增 . } 10. /// 直接寻址实现 11. fn Map::hash_bucket[K : Hash + Eq, V]() -> Map[K, V] { ... } 12. // 简易列表实现或树实现等等... 13. 14. fn init { 15. let map : Map[Int, Int] = Map::hash_bucket() // 仅需替换初始化函数，后续代码⽆需发⽣变化

主题 课程介绍与程序设计 接⼜：集合与表 ⾯向值编程 结构体 命令 函数 列表与递归 可变状态 与可变数据结构 列表 元组 嵌套模式 抽象堆栈结构机器 数据类型与树 可变队列 树与⼆分查找 迭代与尾递归 ⼆叉搜索树的插⼊与删除 闭包与对象 泛型与⾼阶函数 案例：句法分析器与程序解释器 ⾼阶函数： 与 案例：⾃动积分与⼩游戏 所有课程资料均在互联⽹上公开 课程论坛：taolun

现代编程思想 接⼝ Hongbo Zhang 1 回顾 第六课：定义平衡⼆叉树 我们定义⼀个更⼀般的⼆叉搜索树，允许存放任意类型的数据 1. enum Tree[T] { 2. Empty 3. Node(T, Tree[T], Tree[T]) 4. } 5. 6. // 我们需要⼀个⽐较函数来⽐较值的⼤⼩以了解顺序 7. // 负数表示⼩于，0表示等于，正数表示⼤于 8

f2) => f1 * f2.differentiate(val) + f1.differentiate(val) * f2 7. } 8. } 16 符号微分 利⽤符号微分，先构建抽象语法树，再转换为对应的微分，最后进⾏计算 1. fn example() -> Symbol { 2. Symbol::constant(5.0) * Symbol::var(0) * Symbol::var(0) fn init { 5. let input : Array[Double] = [10., 100.] 6. let func : Symbol = example() // 函数的抽象语法树 7. let diff_0_func : Symbol = func.differentiate(0) // 对x_0的偏微分 8. let _ = diff_0_func.compute(input)

0x10 if else end 0x04 (vec�instructions�) 0x05 (vec�instructions�) 0x0B 21 多层编译 字符串 -> 单词流 -> (抽象语法树) -> WASM IR -> 运⾏ 1. enum Expression { 2. Number(Int) 3. Plus(Expression, Expression) 4. Minus(Expression Multiply(Expression, Expression) 6. Divide(Expression, Expression) 7. } 22 多层编译 字符串 -> 单词流 -> (抽象语法树) -> WASM IR -> 编译/运⾏ 1. fn compile_expression(expression : Expression) -> List[Instruction] { 2.

cumulator) { Cons(f(value), cumulator) }, Nil) 3. } 思考题：如何⽤ fold_right 来实现 fold_left ？ 25 ⼆叉搜索树 我们定义⼀个更⼀般的⼆叉搜索树，允许存放任意类型的数据 1. // 我们利⽤泛型定义数据结构 2. enum Tree[T] { 3. Empty 4. Node(T, Tree[T], Tree[T])