python - 在 python 中就地转换树

Question

1. 遍历树并就地修改它的最佳做法是什么？

这是我目前所拥有的:

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)

1. 还有，有没有办法抽象出遍历顺序？ 我想对任何实现 __iter__ 的树做这样的事情:

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

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

   对于 level_order_redo(tree) 中的 n:通过 #如果节点改变，自动重启修改节点

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

Answer 1

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

1。是与否

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

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__() 中实现相同的订单类型(例如您的情况下的后序)，这些订单(前序、中序、后序)都不是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 和parent 的相等性> index-th child ，并在发生变化时清除队列。

4.

如果您想在迭代期间将节点“E”更改为"new"，为什么不这样做:

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

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