使用Inorder Traversal打印二进制树

Question

我想使用Inorder Traversal打印一个二进制树，我有这些函数，我想知道如何编写一个函数来使用它们打印二进制树。非常感谢任何帮助。

def inorder(self):
if not self.is_empty():
for p in self._subtree_inorder(self.root()):
yield p
def _subtree_inorder(self, p):
if self.left(p) is not None:
for other in self._subtree_inorder(self.left(p)):
yield other
yield p
if self.right(p) is not None:
for other in self._subtree_inorder(self.right(p)):
yield other
def positions(self):
return self.inorder()

Answer 1

这里是Python中的两种可能的解决方案，给定以下二进制搜索树。

20
/  
10    30
/  
35    40

37

递归遍历

每当node为空时，递归就会结束。首先为左子树调用inorder_rec()，然后打印当前节点的值，然后为右子树打印。

使用生成器遍历

该方法或多或少是相同的(毫不奇怪，因为算法是相同的)。我们首先需要yield来自左子树的所有结果，然后我们产生当前节点的值，最后但并非最不重要的是，我们产生来自右子树的键。

全部在一起

class Node:
def __init__(self, key):
self.left = None
self.right = None
self.key = key

class Bst:
def __init__(self):
self.root = None
def insert(self, key):
self.root = self.insert_rec(self.root, key)
def insert_rec(self, node, key):
if node is None:
return Node(key)
if key == node.key:
print(f"Key {key} already present! Ignoring value!")
return node
if key <= node.key:
node.left = self.insert_rec(node.left, key)
else:
node.right = self.insert_rec(node.right, key)
return node
def inorder(self):
self.inorder_rec(self.root)
def inorder_rec(self, node):
# end of recursion if current node is None
if node is None:
return
# indorder means: left subtree, then own value, then right subtree
self.inorder_rec(node.left)
print(node.key)
self.inorder_rec(node.right)
def inorder_with_generator(self):
# yield from inorder_genreator()
yield from self.inorder_generator(self.root)
def inorder_generator(self, node):
# nothing to yield if node is None
if node is not None:
for node_data in self.inorder_generator(node.left):
yield node_data
yield node.key
for node_data in self.inorder_generator(node.right):
yield node_data

tree = Bst()
tree.insert(20)
tree.insert(10)
tree.insert(30)
tree.insert(40)
tree.insert(35)
tree.insert(37)
tree.inorder()
print(list(tree.inorder_with_generator()))

预期输出：

10
20
30
35
37
40
[10, 20, 30, 35, 37, 40]

为了避免每次都必须提供root节点作为参数，我添加了两个函数，它们总是在根节点开始遍历，而不需要提供任何参数。