Skip to content

Problem 2: Trees (600pts)

Recall that the tree abstract data types mentioned in class, can be recursively defined using a root node and (sub)trees.

Tree ADT has one constructor:

  • tree(label, branches=[]): Creates a tree with the given label and branches.

We also have the following default selectors in order to get the information for each tree:

  • label(tree): returns the tree's label.
  • branches(tree): returns the tree's branches.
  • is_leaf(object): returns the if a tree is a leaf.

回想一下，课上提到的树（tree）抽象数据类型（ADT）可以递归地定义为一个根节点和若干个（子）树。

树 ADT 有一个构造函数：

  • tree(label, branches=[])：创建一个带有给定标签（label）和分支（branches）的树。

我们还有以下默认的选择函数，用于获取每棵树的信息：

  • label(tree)：返回该 tree 的标签。
  • branches(tree)：返回该 tree 的分支（即子树列表）。
  • is_leaf(object)：如果一个 tree 是一个叶子节点，则返回 True。