post 在 Python 中排序一般树遍历

Question

是否可以使用Python以post次序的方式遍历一般树（即具有多个children的树）。本质上，我想从树的左下角向上遍历像下面这样的树，并将每个节点 .size 与其 parents .size 比较哪个最大，如果 child 更大，我将节点 .max_size 更改为 child 的 .size。根将始终存储树中最大的值。

我的问题：有没有办法以 post 顺序遍历一般树（对于本例：E, F, B, C, D, A）？如果可以的话，应该怎样做？

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

Answer 2

你可以递归:

def updateNodeSize(node):
    if 'children' not in node:
        if 'size' in node:
            return node['size']
        return 0

    maxSize = 0
    for child in node['children']:
        maxSize = max(maxSize, updateNodeSize(child))
    node['size'] = maxSize
    return maxSize


updateNodeSize(root)

post 在 Python 中排序一般树遍历

post order general tree traversal in Python

python

tree

nodes

postorder