在 python 中放置变换树

Question

遍历树并就地修改它的最佳实践是什么？

这是我目前拥有的：

class N: # Node
    def __init__(self, name, *children):
        self.name = name
        self.children=children

    def __iter__(self):
        yield from ((yield from c) for c in self.children)
        yield self

    def __repr__(self):
        return self.name + '(' + ', '.join(str(c) for c in self.children) + ')'

t = N('parent', N('a', N('b')), N('c', N('d')), N('E', N('f'), N('g', N('h')), N('I', N('j'))), N('k', N('l')))

print(t)

for n in t:
    if n==None:
        continue
    print(n)
    if n.name == "E":
        print('How do I replace this node?')
        n = N('new', *n.children)  # obviously doesn't work

print(t)# now 'E' node should be 'new' node

当然我可以通过父节点改变一个节点，但是这样会使代码不那么优雅，因为我需要一个额外的循环：

for n in tree:
    for place, child in enumerate(n.children):
        if child.name=='E': # typo: was n.children
            n.children[place] = N('new', *child.children)

另外，有没有办法抽象出遍历顺序？我想对任何实现 __iter__:

for n in depth_first(tree): 或 for n in level_order(tree):

是否有一种通用的方法可以在节点更改后重新启动？

for n in level_order_redo(tree): pass #if node changed, automatically restart with modified node

应用程序是一个术语重写系统。

Answer 1

对于初学者（可能只是一个拼写错误）：在您建议的解决方案中，行 n.children[place] = N('new', *n.children) 应该是 n.children[place] = N('new', *child.children)。现在回答您的问题：

1。是与否

这在很大程度上取决于树的实现。虽然您可以向节点 class 添加更多内部结构（例如，对父节点和索引的引用）或实现某种方便的迭代器，例如

def pc_iter(self):  # df pre-order parent-child-index iterator
    agenda = [self]
    while agenda:
        n = agenda.pop()
        if n.children:
            for i, c in reversed(list(enumerate(n.children))):
                yield (n, c, i)   # important to yield before appending
                agenda.append(c)  # for changes during iteration
        else:
            yield (n, None, None)

这将允许您缩短就地替换循环

for n, child, i in t.pc_iter():
    if child and child.name == 'E':
        n.children[i] = N('new', *child.children)

我几乎不认为这个比您已有的解决方案更笨拙。

2。否（即使在您的情况下，是）

即使每棵树在其 __iter__() 中实现相同的订单类型（例如您的 post-order），这些订单中的 none（预购，在-order, post-order, level-order) 定义一个唯一的树。换句话说，对于任何节点序列 (len > 2)，存在多个可能的树（每个树的其他顺序不同），例如：

# trees
a[b, c, d]
a[b[c], d]
# have identical pre-order traversal:
(a, b, c, d)
# but different level-order traversal: 
(a, b, c, d) vs. (a, b, d, c)
# and different post-order traversal: 
(b, c, d, a) vs. (c, b, d, a)

当然，所有这些都是假设遍历只产生节点的有效负载（name 在你的情况下），而不是节点本身（正如你的 __iter__() 所做的那样任何类型的集合数据类型的异常行为）。在后一种情况下，返回的第一个（或最后一个 - 取决于顺序）节点是根节点，并包含构建其他遍历所需的所有信息。

3。不是真的（你为什么要）

如上所示，在迭代期间更改节点（我将其称为反模式）是唯一可能的，因为您实际上是在节点而不是有效负载上进行迭代。此外，您不是在迭代器到达该节点时替换该节点，而是在它位于该节点的父节点时替换该节点。

话虽这么说——假设你的level-order(tree)知道树的内部结构并且实际上产生节点而不是有效负载——该函数可以维护一个队列（通常在那里使用）parent-child-index 元组，在生成 parent 之后，检查 child 和 [=48= 是否相等]parent's index-th child，并清空队列以防发生变化。

4.

如果你想在迭代期间将节点 'E' 更改为 'new'，你为什么不这样做：

for n in tree:
    if n.name == 'E':
        n.name = 'new'

这将为您省去很多麻烦，并且从您调用节点构造函数的方式来看，您没有其他对 'E' 节点的引用，您可能会在此过程中无意中更改。

在 python 中放置变换树

In place transform tree in python

python

tree

1。是与否

2。否（即使在您的情况下，是）

3。不是真的（你为什么要）

4.