红魔咖啡馆

头发越掉越多，头发越掉越少

0%

【CS61A】CS61A——Trees

发表于 更新于 分类于
本文字数： 2.5k 阅读时长 ≈ 5 分钟

Trees

描述树形结构的术语

递归描述 - 一课树有一个根节点和一系列分支节点 - 每个分支也是一棵树，也有根节点与分支节点 - 没有分支节点的树被称为叶子节点

亲戚描述

  • 树的每个位置被称为节点
  • 每个节点可以表示任何值
  • 一个节点可以称为另一个节点的父节点/子节点 trees

实现树形结构的抽象

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
def tree(label, branches=[]):
    for branch in branches:
        assert is_tree(branch), "branches must be trees" # 确保构造的是一棵树
    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)


if __name__ == "__main__":
    t = tree(1, [tree(5, [tree(7)]), tree(6)])
    print(t)
    print(label(t))
    print(branches(t))
    print(label(branches(t)[0]))
[1, [5, [7]], [6]]
1
[[5, [7]], [6]]
5

Tree Processing

处理叶子节点

使用递归，将会在每个分支节点进行递归调用，最后合并

1
2
3
4
5
6
7
8
9
10
def count_leaves(t):
    """Count the leaves of tree T"""
    if is_leaf(t):
        return 1
    else:
        return sum([count_leaves(b) for b in branches(t)])

if __name__ == "__main__":
    t = tree(1, [tree(5, [tree(7)]), tree(6)])
    print(count_leaves(t))
2

返回叶子节点的值

实现leaves函数，返回树的叶子节点的值的列表

1
2
3
4
5
6
7
8
9
10
def leaves(tree):
    """return a list containing the leaf labels of tree"""
    if is_leaf(tree):
        return [label(tree)]
    else:
        return sum([leaves(b) for b in branches(tree)], [])

if __name__ == "__main__":
    t = tree(1, [tree(5, [tree(7)]), tree(6)])
    print(leaves(t))
[7, 6]

根据树创建树

使用递归根据另一棵树创建一颗新树 如让叶子节点值+1的树 或让所有节点都+1的树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def increment_leaves(t):
    """return a tree like t but with leaf labels incremented"""
    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 increment(t):
    """return a tree like t but with all labels incremented"""
    return tree(label(t)+1, [increment(b) for b in branches(t)])

if __name__ == "__main__":
    t = tree(1, [tree(5, [tree(7)]), tree(6)])
    print(leaves(t))
    print(increment_leaves(t))
    print(increment(t))
[7, 6]
[1, [5, [8]], [7]]
[2, [6, [8]], [7]]

例：print_tree

按节点在树中的深度缩进打印一颗树

1
2
3
4
5
6
7
8
def print_tree(t, indent = 0):
    print(' '*indent + str(label(t)))
    for b in branches(t):
        print_tree(b, indent+1)

if __name__ == "__main__":
    t = tree(1, [tree(5, [tree(7)]), tree(6)])
    print(print_tree(t))
1
 5
  7
 6
None

例： 求从根节点沿路径到叶子节点求和并打印

1
2
3
4
5
6
7
8
9
10
11
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)

if __name__ == "__main__":
    t = tree(1, [tree(5, [tree(7)]), tree(6)])
    print(print_sums(t, 0))
13
7
None