这道题目比较有代表性，recursive function是解题的关键
Question 6
Write a function has_path that takes in a tree t and a string word. It returns True if there is a path that starts from the root where the entries along the path spell out the word, and False otherwise. (This data structure is called a trie, and it has a lot of cool applications, such as autocomplete). You may assume that every node’s label is exactly one character.

def has_path(t, word):"""Return whether there is a path in a tree where the entries along the pathspell out a particular word.>>> greetings = tree('h', [tree('i'),...                        tree('e', [tree('l', [tree('l', [tree('o')])]),...                                   tree('y')])])>>> print_tree(greetings)hielloy>>> has_path(greetings, 'h')True>>> has_path(greetings, 'i')False>>> has_path(greetings, 'hi')True>>> has_path(greetings, 'hello')True>>> has_path(greetings, 'hey')True>>> has_path(greetings, 'bye')False>>> has_path(greetings, 'hint')False"""assert len(word) > 0, 'no path for empty word.'if label(t) == word:return Trueelse:nb = [has_path(b, word) for b in branches(t)]return label(t) + sum(nb) == word

Tree Data Abstraction Implementation:

def tree(label, branches=[]):"""Construct a tree with the given label value and a list of branches."""return [label] + list(branches)def label(tree):"""Return the label value of a tree."""return tree[0]def branches(tree):"""Return the list of branches of the given tree."""return tree[1:]def is_leaf(tree):"""Returns True if the given tree's list of branches is empty, and Falseotherwise."""return not branches(tree)