快树在任意树中行走

Question

我在尝试遍历使用anytree中的AnyNode构建的二叉树时偶然发现了一个问题。

首先，我需要说的是，每个节点都有一个与其关联的特定 id，因此根节点的 id=0，其子节点 id=1 和 id=2。那么 id=1 的孩子是 id=3 和 id=4 等等。我需要能够从上到下遍历树，检查每个节点是否满足条件，如果满足，则保存该节点并从遍历过程中删除其所有子节点。

我这样做的方法是使用

创建一个ID列表

list1=[node.id for node in LevelOrderIter(root)]
listfar=[]

然后

i=0
while i<len(list1):
 ....
 if condition is fulfilled for a node named e.g parent:
   list2=[node.id for node in LevelOrderIter(parent)]
   listfar.append(list2)
   list1=list(set(list1).difference(list2))
   list1.sort()
   i=i-1
  i=i+1

我使用node.id而不仅仅是node的原因是这样我可以在删除后进行排序，因为它不保留我的顺序。这里的主要问题是 LevelOrderIter 需要花费大量时间来运行我的树（因为树有 21 个级别）。另外，我没有使用 walk 模块，因为我需要对每个级别中的所有节点执行此操作，而不仅仅是从节点到叶子。

对于我的情况，遍历整棵树需要 1 分钟，并且我需要它最多下降到一秒的数量级。

anytree 中是否有一个模块可以快速生成与节点后代的 LevelOrderIter 相同的 node.ids 列表？如果没有，但有一个模块可以对整个节点（不仅仅是node.id）执行此操作，是否有一种方法可以在删除节点时保持 list1 元素的顺序？

Answer 1

如果我正确理解这个问题，你想按级别顺序遍历树。 如果一个节点满足特定条件，您希望存储该节点，但不再进一步遍历其任何后代。

似乎有一种更简单的方法可以在任何树中实现此目的。 签名是：

LevelOrderIter(node, filter_=None, stop=None, maxlevel=None)

stop

参数听起来非常接近您想要的。

因此，编写问题的一种方法如下：

list1 = list(LevelOrderIter(node, stop=lambda node: not node.is_root and condition(node.parent))

如果这还不够快，我们可能会变得有点棘手：

list1 = []
def stop_and_append(node):
    if condition(node):
        list1.append(node)
        return True
    else:
        return False

for _ in LevelOrderIter(node, stop=stop_and_append):
    pass  # Run for side-effect

但是对于二叉树来说，改进应该是微乎其微的，并且单行代码看起来更具可读性。

如果这还不够快，你可以尝试另一个树包，比如我的，但说实话，我不期望有太多加速，因为你的树只有 20 层深。

list1 = []
def keep_or_append(node, _):
    if condition(node):
        list1.append(node)
        return False
    else:
        return True

for _ in node.iter_tree(keep_or_append, order='level'):
    pass  # Run for side-effect

# or short version:

list1 = list(node.iter_tree(keep=lambda node, _: node.is_root or not condition(node.parent), order='level'))