遍历Python中的二叉树

Question

我几乎完成了一个项目，该项目使我们创建了一个使用二叉树结构的字典类。然而，我坚持如何实现一个方法，打印出树中的所有元素，我只是没有太多的二叉树经验，所以它如何编码它相当混乱。

我想弄明白的方法是一个键方法，它将遍历整个树并返回所有键的列表。我认识的人暗示我应该创建一个递归遍历树并跟踪所有键的私有助手函数。我想创建他正在谈论的内容，但我没有现成的想法来编写代码。任何人都可以帮我编码吗？搞清楚这一点对我来说几乎完成了。

这是我的代码到目前为止。 [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

所有你需要做的就是创建一个helper方法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 2

这应该这样做

def allKeys(d): 
    toVisit = [] 
    toVisit.append(d) 
    while (len(toVisit)>0): 
     x = toVisit.pop() 
     if x._element: 
      yield x._element[0] 
     if x._left: 
      toVisit.append(x._left) 
     if x._right: 
      toVisit.append(x._right) 

对于中序遍历，你需要一个递归水溶液和如在树的遍历维基百科给出entry。

Answer 3

对于树遍历，通常人们进行宽度优先遍历（BFT）或深度优先遍历（DFT）。

在BFT中，您使用一个队列记住您离开的位置，在DFT中使用堆栈记住您离开的位置。如果你知道队列和堆栈的性质，那么理解BFT和DFT只是小菜一碟，否则请阅读Breadth-first search和Depth-first search，顺便说一下，遍历树的代码通常不超过10行，证明他们多么容易。

Answer 4

有使用递归有序树遍历另一种解决方案的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))) 

我认为这是更具可读性和概念上简单。我希望这会对某人有帮助。