在Python中遍历二叉树

Question

我快完成一个项目了，这个项目是让我们创建一个字典类，使用二叉树结构。不过，我在实现一个方法时遇到了麻烦，这个方法是用来打印出树中的所有元素。因为我对二叉树的经验不多，所以这让我有点困惑，不知道该怎么写代码。

我想弄明白的方法是一个叫做 keys 的方法，它会遍历整个树，并返回一个包含所有键的列表。有人告诉我，我应该创建一个私有的辅助函数，这个函数会递归地遍历树，并记录下所有的键。我想按照他说的去做，但我完全不知道该怎么编码。有没有人能帮我写这个代码？弄清楚这个问题对我来说几乎就能完成整个项目了。

这是我目前的代码。[Key:Value] 对是元组。我是根据书本上的例子写的这些代码，得到了你们看到的内容：

class DictWithTree:

    def __init__(self):
        self._element = None
        self._left = None
        self._right = None
        self._size = 0

    def isempty(self):
        if self._element == None:
            return True
        return False

    def __len__(self):
        return self._size

    def __contains__(self,key):
        path = self._tracePath(key)
        return path[-1]._size > 0

    def _tracePath(self,key): # taken from the textbook example and modified
        if len(self) == 0 or key == self._element[0]:
            return [self]   
        elif len(key) < len(self._element[0]):
            return [self] + self._left._tracePath(key)
        else:
            return [self] + self._right._tracePath(key)

    def __getitem__(self,key):
        if len(self) == 0:
            raise KeyError(key)   
        elif key == self._element[0]:
            return self._element[1]
        elif key < self._element[0]:
            return self._left[key]
        elif key > self._element[0]:
            return self._right[key]
        else:
            raise KeyError(key)

    def __setitem__(self,key,value):
        path = self._tracePath(key)
        endOfPath = path[-1]
        if endOfPath._element != None:       
            if endOfPath._element[0] == key: 
                endOfPath._element = key,value
        if endOfPath._size == 0: # a new element
            for location in path:
                location._size += 1
            endOfPath._element = key,value
            endOfPath._left = DictWithTree()
            endOfPath._right = DictWithTree()

    def clear(self):
        self._element = None
        self._left = None
        self._right = None
        self._size = 0

    def pop(self,key):
        value = self[key]
        self._remove(key)
        return value

    def popitem(self):     # returns the 'last' item in the dictionary,
        if self.isempty(): # (i.e. the largest key in the dictionary)
            return KeyError("There are no keys in the dictionary")
        elif self._right._element == None:
            return self._element
        else:   
            return self._right.popitem()                                   

    def _remove(self,key):
        path = self._tracePath(key)
        endOfPath = path[-1]
        if endOfPath._size > 0:
            for location in path:
                location._size -= 1
            if len(endOfPath._left) == 0:
                endOfPath._promoteChild(endOfPath._right)
            elif len(endOfPath._right) == 0:
                endOfPath._promoteChild(endOfPath._left)
            else:
                endOfPath._element = endOfPath._left.pop()

    def _promoteChild(self,child):
        self._element = child._element
        self._left = child._left
        self._right = child._right

Answer 1

在树的遍历中，通常人们会使用广度优先遍历（BFT）或深度优先遍历（DFT）。

在广度优先遍历中，你会用一个队列来记住你停在哪了；而在深度优先遍历中，你会用一个栈来记住你停在哪了。如果你了解队列和栈的基本特性，那么理解广度优先遍历和深度优先遍历就非常简单了。否则，你可以看看广度优先搜索和深度优先搜索的相关内容。顺便说一下，遍历树的代码通常不超过10行，这也说明了它们是多么简单。

Answer 2

你只需要创建一个辅助方法 visitAllSubnodes(node)，这个方法会对当前节点做一些事情，然后递归地调用自己去处理左边和右边的子节点。visitAllSubnodes(node) 可以做任何事情，比如在你的情况下可以是 print(node._element)，但你可以让这个函数变得非常灵活，比如：

def visitAllSubnodes(node, whatToDoAtEachNode):
    whatToDoAtEachNode(node)
    visitAllSubnodes(node._left, whatToDoAtEachNode)
    visitAllSubnodes(node._right, whatToDoAtEachNode)

def printAllElements(node):
    visitAllSubnodes(node, lambda x:print(x))

如果你想要返回一些东西，就需要用到高阶函数和闭包的概念。举个例子，你可以创建一个函数，这个函数里定义一个私有的累加器（就是一个你可以添加内容的列表），然后再创建另一个函数，让这个私有累加器归它所有，最后返回这个函数。

所以，比如说，每次遍历树的时候，你可以调用这个高阶函数，我们叫它 makeFunctionWhichKeepsTrackOfWhatHasBeenPassedIntoIt()，这个函数会返回一个可以记录传入内容的函数，还有那个累加器。我可以提供更多信息，但这正是问题的关键所在。=)

Answer 3

还有一种使用Python 3的 yield from 来进行递归中序树遍历的方法：

def traverse(tree):
    if tree.left is not None:
        yield from traverse(tree.left)

    yield tree.value

    if tree.right is not None:
        yield from traverse(tree.right)

print(list(traverse(tree_root)))

我觉得这种写法更容易读懂，概念上也更简单。希望对某些人有帮助。