# 了解 BST 遍历的打印输出

2023-08-22 10:47:40

## 1 回答

TA贡献1712条经验 获得超3个赞

from collections import namedtuple

class Tree:

def __init__(self, root):

self.root = root

def inorder(self):

def traverse(node):

if node:

yield from traverse(node.left)

yield node

yield from traverse(node.right)

return traverse(self.root)

if __name__ == "__main__":

Node = namedtuple("Node", "data left right")

"""

9

/ \

4   17

/ \

3   6

"""

tree = Tree(

Node(

9,

Node(

4,

Node(3, None, None),

Node(6, None, None),

),

Node(17, None, None)

)

)

for node in tree.inorder():

print(node.data, end=" ") # => 3 4 6 9 17

from collections import namedtuple

class Tree:

def __init__(self, root):

self.root = root

def inorder(self):

def traverse(node, depth=0):

if node:

yield from traverse(node.left, depth + 1)

yield node, depth

yield from traverse(node.right, depth + 1)

return traverse(self.root)

if __name__ == "__main__":

Node = namedtuple("Node", "data left right")

"""

9

/ \

4   17

/ \

3   6

"""

tree = Tree(

Node(

9,

Node(

4,

Node(3, None, None),

Node(6, None, None),

),

Node(17, None, None)

)

)

for node, depth in tree.inorder():

print(" " * (depth * 2) + str(node.data))

3

4

6

9

17

from collections import namedtuple

class Tree:

def __init__(self, root):

self.root = root

def print_traversals_pedagogical(self):

preorder = []

inorder = []

postorder = []

def traverse(node, depth=0):

if node:

preorder.append(node.data)

print("    " * depth + f"entering {node.data}")

traverse(node.left, depth + 1)

inorder.append(node.data)

print("    " * depth + f"visiting {node.data}")

traverse(node.right, depth + 1)

postorder.append(node.data)

print("    " * depth + f"exiting {node.data}")

traverse(self.root)

print("\npreorder ", preorder)

print("inorder  ", inorder)

print("postorder", postorder)

if __name__ == "__main__":

Node = namedtuple("Node", "data left right")

"""

9

/ \

4   17

/ \

3   6

"""

tree = Tree(

Node(

9,

Node(

4,

Node(3, None, None),

Node(6, None, None),

),

Node(17, None, None)

)

)

tree.print_traversals_pedagogical()

entering 9

entering 4

entering 3

visiting 3

exiting 3

visiting 4

entering 6

visiting 6

exiting 6

exiting 4

visiting 9

entering 17

visiting 17

exiting 17

exiting 9

preorder  [9, 4, 3, 6, 17]

inorder   [3, 4, 6, 9, 17]

postorder [3, 6, 4, 17, 9]

• `restart`做同样的事情，`b4 app`所以你应该忽略它以避免混淆。这`if node is not None: print("b4 app", node.data)`始终是正确的——我们保证调用者`node`不会是 None。

• `b4 app`-> `entering`（或将新调用推入堆栈）。

• `aft app`-> `visiting`（按顺序）。再次`if node is not None:`保证是真实的并且应该被删除。父调用会检查这一点，即使他们没有这样做，程序也会在上面使用 的行上崩溃`node.data`

• `inside right`令人困惑——这是一个有序打印，但仅适用于具有右子节点的节点。我不确定这会增加什么价值，所以我会忽略它。

`if`如果跳过该语句（上次`io`调用该函数时），递归将如何继续？

visiting 3  # this is your `aft app 3 True [0]`

exiting 3   # you don't have this print for leaving the node

visiting 4      # this is your `aft app 4 False #[2]`

• 1 回答
• 0 关注
• 3859 浏览

0/150