No.7 Trees

CS61 A 计算机程序的结构与解释，无论你是对计算机科学充满好奇的新生，还是希望进一步提升编程技能的进阶者，CS61A都将为你提供一个广阔的学习平台，助你开启一段充满挑战与收获的旅程。

No.7 Trees

• 树结构的描述
• 实现树结构
  • 输入输出如图
  • 实现
    • 通常是 Tree 递归函数
      • 输入
        • label
          • 根节点
        • branches
          • 分支，是一个列表list，默认为空白
      • 输出
        • 树，一个内部多重嵌套的列表
      • list 函数
    • 列表拼接
• Tree processing
  • 斐波那契树
  • 计算叶子节点数
    • 叶子节点
      • 没有子节点的节点
    • • b in branches(t)实质上摘了一个[]，来使 b 变成一个list
    • 列表推导式
      • • 例子
  • 返回所有叶子节点的标签
  • 从另一个树创造树函数
    • 返回所有叶子节点的标签+1的树
      • 示例
    • 所有节点标签+1的树
      • 所有根节点都会+1，直至所有叶子节点+1
  • Print Tree
    • 拥有缩进结构的Print
  • Summing Paths
    • 沿路径加和树的label
  • counting trees
• 递归的类型
  • 操作返回值，在返回值处实现递归，此时每个 local frame 的 fact(n)的返回值并不相同，每次求得一个 fact(n-1)，递归得到最终值 如下图第一种做法
  • 不对返回值进行操作，改变每个 local frame 的 fact_times(n,k)的输入值，得到fact_times(n-1,n*k)这与fact_times(n,k)结果相同，再进行递归