4

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

以这个列表为例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

这样做的问题是递归将是错误的。现在有比Lengthfor 循环中的节点更多的节点，因此并非所有项目都会被递归。同样，删除一个节点意味着在列表中向上移动的节点将被跳过。

如何递归由于我的递归处理而可能发生变化的树？是否一遍又一遍地重复我的列表，直到我确定唯一的方法没有进行任何更改，或者我是否错误地解决了问题？

4

2 回答 2

1

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

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

于 2015-08-13T19:05:26.457 回答
1

现在有比 for 循环中的长度更多的节点，因此并非所有项目都会被递归。

我不认为这是真的。您不是在评估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); 
    }
}

为什么我要传入 a 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

希望这个答案对您有所帮助。

于 2015-09-17T09:03:49.447 回答