L14 Trees

• 实现树的抽象

  • def tree(label,branches=[]):
    • for branch in branches:
      • assert is_tree(branch)
    • return [label]+list(branches)
  • def label(tree):
    • return tree[0]
  • def branches(tree):
    • return tree[1:]
  • def is_tree(tree):
    • if type(tree) != list or len(tree)<1:
      • return False
    • for branch in branches(tree):
      • if not is_tree(branch):
      • return False
    • return True
  • def is_leaf(tree):
    • return not branches(tree)

• 对树的处理

  • 斐波那契树的递归构建
  • 数叶子数量
  • 得到所有叶子的list
    • 利用sum的特性 --- sum([[1],[2,3],[4]],[]) == [1,2,3,4]
    • def leaves(tree):
      • if is_leaf(tree):
        • return [label(tree)]
      • else:
        • return sum([leaves(b) for b in branches(tree)],[])
  • 由旧树得到新树
    • def increment_leaves(t):
      • if is_leaf(t):
        • return tree(label(t)+1)
      • else:
        • bs = [increment_leaves(b) for b in branches(t)]
        • return tree(label(t),bs)
  • 打印树
    • def print_tree(t,indent=0):
      • print(' '*indent+str(label(t)))
      • for b in branches(t):
        • print_tree(b,indent+1)
  • 沿路径求和并打印总和
    • def print_sums(t,so_far):
      • so_far = so_far+label(t)
      • if is_leaf(t):
        • print(so_far)
      • else:
        • for b in branches(t):
          • print_sums(b,so_far)
  • 数符合条件的路径个数
    • def count_paths(t,total):
      • if label(t) == total
        • found = 1
      • else:
        • found=0
      • return found + sum([count_paths(b,total-label(t)) for b in branches(t)])

---

评论