如何递归地遍历一个在遍历过程中不断变化的树

Question

我正在尝试遍历DOM树，使用HTML解析器替换和删除AngleSharp节点。这个问题不是这个库独有的，而是一个关于如何递归地修改树并确保我仍然遍历整个树的一般问题。

以这个列表myCollection为例，其中每个条目都是一个节点对象，可能有子节点。它也是一个实时集合:

-A
-B
-C
 --D
 --E
 --F
-G

我开始在递归函数中循环:

private void LoopRecursively(Node element) {
   //either do nothing, remove, or replace with children
   //e.g. element.Replace(element.ChildNodes);
   for (var x = 0; x < element.ChildNodes.Length; x++) {
      LoopRecursively(element.ChildNodes[x]);
   }
}

假设我们决定用C节点的子节点替换它，那么列表变成:

-A
-B
-D
-E
-F
-G

这样做的问题是递归会出错。现在for循环中的节点比Length要多，所以不是所有的项都要递归。类似地，删除一个节点将意味着在列表中向上移动的节点将被跳过。

我如何递归一个可能由于我的递归处理而改变的树?是否一遍又一遍地递归我的列表，直到我确定没有进行任何更改，还是我处理问题的方法不正确?

Answer 1

安全方法:使用递归函数创建一个全新的树，而不是更改旧树，然后用新树替换旧树。

不太安全的方法:让looprecursive函数返回一个整数，表示添加或删除的节点数，然后用这个新数字更新循环变量。(更新循环索引和循环条件中的变量)

Answer 2

现在for循环中的节点数已经超过了Length，所以不是所有的项都将被递归。

我不认为这是真的。您不是一次评估element.ChildNodes.Length，而是在每次迭代中评估。因此，如果列表是活动的，长度将随着您的更改而更改。

让我们假设树的简单实现如下:

class Node
{
    readonly List<Node> children;
    readonly String name;
    public Node(String name)
    {
        this.children = new List<Node>();
        this.name = name;
    }
    public Node AddChild(Node node)
    {
        children.Add(node);
        return this;
    }
    public Node InsertChild(int index, Node node)
    {
        children.Insert(index, node);
        return this;
    }
    public Int32 Length
    {
        get { return children.Count; }
    }
    public Node this[Int32 index]
    {
        get { return children[index]; }
    }
    public Int32 IndexOf(Node node)
    {
        return children.IndexOf(node);
    }
    public Node RemoveChild(Node node)
    {
        children.Remove(node);
        return this;
    }
    public IEnumerable<Node> Children
    {
        get { return children.AsEnumerable(); }
    }
    public override String ToString()
    {
        var content = new String[1 + children.Count];
        content[0] = name;
        for (int i = 0; i < children.Count; )
        {
            var childs = children[i].ToString().Split(new [] { Environment.NewLine }, StringSplitOptions.RemoveEmptyEntries);
            content[++i] = "+ " + String.Join(Environment.NewLine + "  ", childs);
        }
        return String.Join(Environment.NewLine, content);
    }
}

给定的Node包含子(但没有父)和简单的方法来添加，删除，插入，…,孩子们。

让我们看看如何用这种Node:

构造一个好的例子

var root = new Node("Root");
root.AddChild(new Node("a")).
     AddChild(new Node("b")).
     AddChild(new Node("c").
        AddChild(new Node("d").
            AddChild(new Node("e")).
            AddChild(new Node("f"))).
        AddChild(new Node("g")).
        AddChild(new Node("h"))).
    AddChild(new Node("i"));

调用root.ToString()的输出如下所示:

Root
+ a
+ b
+ c
  + d
    + e
    + f
  + g
  + h
+ i

我猜你想把树压平?正如已经说过的，以不可变的方式做它可能是一个好主意。有多种方法可以做到这一点，但考虑到上面的API，我们最终可以得到以下解决方案:

void Flatten(Node element, List<Node> nodes)
{
    var before = nodes.Count;
    foreach (var node in element.Children)
    {
        Flatten(node, nodes);
    }
    if (nodes.Count == before)
    {
        nodes.Add(element); 
    }
}

为什么我传递一个List<Node> ?我们可以在每次调用中创建一个列表，然后将其与调用者的列表合并，然而，上面的版本更有效率一些。此外，我们正在使用Count属性来确定是否有任何孩子被看到。我们也可以使用Any()扩展方法，但这又是一些不必要的开销。我们只需检查给定节点是否为叶节点。如果是，则将其添加到所提供的列表中。

如果你真的想改变原始树，那么你还有一些其他的选择。下面的代码接受一个元素，递归遍历它的子元素。叶子保持不变，有父节点的子节点将把它们的后代附加到父节点。

void Flatten(Node element, Node parent = null)
{
    for (var i = 0; i < element.Length; i++)
    {
        Flatten(element[i], element);
    }
    if (parent != null && element.Length > 0)
    {
        var children = element.Children.ToArray();
        var index = parent.IndexOf(element);
        parent.RemoveChild(element);
        foreach (var child in children)
        {
            element.RemoveChild(child);
            parent.InsertChild(index++, child);
        }
    }
}

第一次迭代不会改变element.Length的值。因此我们也可以安全地求一次值，就是这样。然而，潜在的第二次迭代将做到这一点。这就是为什么我们首先获得element.Children.ToArray()的副本。还有另一种不需要复制的方法，它涉及一个反向for循环(从Length到-1)。

让我们看看调用Flatten(root)后树的序列化是怎样的。

Root
+ a
+ b
+ e
+ f
+ g
+ h
+ i