Skip to content

Problem 3.2: Pruning (100pts)

Problem

Complete the function prune that takes in a Tree t and a number n and prunes t mutatively. If t or any of its branches has more than n branches, the n branches with the smallest labels should be kept and any other branches should be pruned, or removed, from the tree.

You can assume that a node will not have two children with the same label.

完成函数 prune，它接受一个 Tree \(t\) 和一个数字 \(n\)，并以修改的方式修剪 \(t\)。 如果 \(t\) 或它的任何分支拥有的分支数量超过 \(n\) 个，则应该保留标签最小的 \(n\) 个分支，而所有其他分支都应该被修剪，或从树中移除。

你可以假设一个节点不会有两个标签相同的子节点。

def prune(t, n):
    """Prune the tree mutatively, keeping only the n branches
    of each node with the smallest label.

    >>> t1 = Tree(6)
    >>> prune(t1, 2)
    >>> t1
    Tree(6)
    >>> t2 = Tree(6, [Tree(3), Tree(4)])
    >>> prune(t2, 1)
    >>> t2
    Tree(6, [Tree(3)])
    >>> t3 = Tree(6, [Tree(1), Tree(3, [Tree(1), Tree(2), Tree(3)]), Tree(5, [Tree(3), Tree(4)])])
    >>> prune(t3, 2)
    >>> t3
    Tree(6, [Tree(1), Tree(3, [Tree(1), Tree(2)])])
    """
    "*** YOUR CODE HERE ***"

Hints

Hint: lst.pop(i) can remove the ith (start from 0) item in lst.

  • lst.pop(i) 可以移除列表 lst 中索引为 \(i\)（从 0 开始计数）的项。