python - Python中的后序通用树遍历

Question

是否可以使用 Python 以后序方式遍历一般树（即具有多个子节点的树）。本质上，我想从树的左下角向上遍历一棵树，并将每个节点.size与其父节点进行比较.size，以确定哪个节点最大，如果孩子更大，我将节点更改.max_size为孩子的.size. 根将始终具有存储在其中的树中最大的值。

我的问题：有没有办法按后序遍历一般树（对于这个例子：）E, F, B, C, D, A？如果是这样，这样做的方法是什么？

标签： pythontreenodespostorder

Answer 1

不知道为什么你需要大小的东西。你可以这样做：

In [254]: class Node:
     ...:     def __init__(self, val: str):
     ...:         self.val = val
     ...:         self.children = []
     ...:

In [255]: A = Node('A')
In [256]: B = Node('B')
In [257]: C = Node('C')
In [258]: D = Node('D')
In [259]: E = Node('E')
In [260]: F = Node('F')
In [261]: A.children = [B,C,D]
In [262]: B.children = [E,F]
In [263]: root = A
# General post order but iterating over the children instead of doing left/right
In [264]: def post_order(root: Node):
     ...:     if root is not None:
     ...:         for child in root.children:
     ...:             post_order(child)
     ...:         print(root.val)
     ...:

In [265]: post_order(A)
E
F
B
C
D
A