c#中所有元素顺序XML前序后序遍历

Question

我需要一个函数来 return C# 中所有元素的前序和后序，其中 return 是所有元素的（XElement、Preorder、Postorder）列表。我该怎么做？

例如，XML：

<?xml version='1.0' encoding='ISO-8859-1' ?>

<!--
  XML-Page generated by PENELOPE.
  Copyright (c) 1999 Araneus Group and University 'Roma Tre', Rome, ITALY
  All rights reserved.
-->
<SigmodRecord>
    <issue>
        <volume>11</volume>
        <number>1</number>
        <articles>
            <article>
                <title>Architecture of Future Data Base Systems</title>
                <authors>
                    <author position="00">Lawrence A. Rowe</author>
                    <author position="01">Michael Stonebraker</author>
                </authors>
                <initPage>30</initPage>
                <endPage>44</endPage>

            </article>
            <article>
                <title>Multisafe - A Data Security Architecture</title>
                <authors>
                    <author position="00">Robert P. Trueblood</author>
                    <author position="01">ii. Rex Hartson</author>
                </authors>
                <initPage>45</initPage>
                <endPage>63</endPage>
            </article>
        </articles>
    </issue>
    <issue>
        <volume>12</volume>
        <number>2</number>
        <articles>
            <article>
                <title>Comparison and Mapping of the Relational and CODASYL Data Models</title>
                <authors>
                    <author position="00">Gary H. Sockut</author>
                </authors>
                <initPage>55</initPage>
                <endPage>68</endPage>
            </article>
        </articles>
    </issue>
</SigmodRecord>

我需要这个答案：

Element = <SigmodRecord>,preorder = 1, postorder = 29
Element = <SigmodRecord/issue>,preorder = 2, postorder = 18
.
.
.

我已经写了这个 class 但它在大型 XML 文件中运行缓慢，因为对于每个元素，它都会处理所有节点！

class CTraversal
{
    private int preorderID = 0;
    private int postorderID = 0;

    public int PreOrderTraversal(XElement RootNode, XElement CurrentNode)
    {
        if (CurrentNode == RootNode)
        {
            return ++preorderID;
        }
        if (RootNode.DescendantNodes().Count() > 1)
        {
            foreach (var child in RootNode.Elements())
            {
                if (PreOrderTraversal(child, CurrentNode) != -1) return preorderID;
            }
        }
        return -1;
    }

    public int PostOrderTraversal(XElement RootNode, XElement CurrentNode)
    {
        if (RootNode.DescendantNodes().Count() > 1)
        {
            foreach (var child in RootNode.Elements())
            {
                if (PostOrderTraversal(child, CurrentNode) != -1) return postorderID;
            }
        }
        if (CurrentNode == RootNode)
        {
            return ++postorderID;
        }
        ++postorderID;
        return -1;
    }
}

Answer 1

所以处理 pre-order 树遍历是两者中比较容易的，所以我们将从这里开始。

该方法将接受一系列项目，以及一个接受项目并将其转换为项目序列的函数，这让我们可以得到任何给定节点的所有 children。

然后在我们的方法中，我们将有一个迭代器堆栈，将起始序列的迭代器压入堆栈以开始。

只要有任何迭代器要处理，我们就会从那里开始循环。我们获取要处理的当前项目，如果它有 children 我们放弃它的当前项目，将迭代器推回堆栈以供稍后处理，获取 children 的序列，推送他们入栈处理

public static IEnumerable<T> PreOrder<T>(
    IEnumerable<T> source,
    Func<T, IEnumerable<T>> childSelector)
{
    var stack = new Stack<IEnumerator<T>>();
    stack.Push(source.GetEnumerator());
    try
    {
        while (stack.Any())
        {
            var current = stack.Pop();
            if (current.MoveNext())
            {
                stack.Push(current);
                var children = childSelector(current.Current);
                stack.Push(children.GetEnumerator());
                yield return current.Current;
            }
            else
            {
                current.Dispose();
            }
        }
    }
    finally
    {
        foreach (var iterator in stack)
            iterator.Dispose();
    }
}

这涵盖了我们的 pre-order 算法，对于每个要处理的项目，产生它，然后处理所有 child 个项目。

这里有一个测试用例来演示它。这是一个 XML 文档，其中每个节点都有一个值，表示它应该从预序遍历中产生的顺序：

string preOrderExample =
@"<node value='1'>
  <node value='2'>
    <node value='3'/>
    <node value='4'/>
    <node value='5'/>
  </node>
  <node value='6'>
    <node value='7'>
      <node value='8'/>
      <node value='9'>
        <node value='10'/>
      </node>
    </node>
    <node value='11'/>
  </node>
</node>";

var preOrderDoc = XDocument.Parse(preOrderExample);
var query = PreOrder(new[] { preOrderDoc.Root }, node => node.Elements());
foreach (var node in query)
    Console.WriteLine(node.Attribute("value").Value);

这将打印出 1, 2, 3, ..., 11，表明它们正在以正确的顺序处理。

Post 顺序非常相似，但需要稍微调整一下。基本上我们想要做的是使用完全相同的算法，但在处理所有 children 之后生成每个项目。首先要做的是 copy-paste 相同的算法，只是删除 `yield。现在，在我们的算法中，我们知道在哪里处理了一个项目的所有 children 吗？

嗯，就在我们从堆栈中弹出一个迭代器之后，该迭代器的 Current 项刚刚处理了它的所有项。嗯，也就是说，除非我们还没有在该迭代器上调用 MoveNext，在这种情况下 没有当前项 。所以，如果有物品，我们应该让出它。

遗憾的是，给定一个 IEnumerator，没有办法知道它是否已经被 MoveNext 调用过。我们可以创建一个新类型来包装 IEnumerator 并跟踪它是否已启动。这实际上可能是个好主意，但由于仅在这一种方法中使用，我作弊了一点，只是使用 Tuple<IEnumerator<T>, bool> 来保存可能已启动或未启动的序列，替换了 [ 的所有用法=20=] 在带有该元组的方法中，并根据我们是否知道我们已经向该迭代器询问了一个值来设置布尔值。

public static IEnumerable<T> PostOrder<T>(
    IEnumerable<T> source,
    Func<T, IEnumerable<T>> childSelector)
{
    var stack = new Stack<Tuple<IEnumerator<T>, bool>>();
    stack.Push(Tuple.Create(source.GetEnumerator(), false));
    try
    {
        while (stack.Any())
        {
            var current = stack.Pop();
            if (current.Item2)
                yield return current.Item1.Current;
            if (current.Item1.MoveNext())
            {
                stack.Push(Tuple.Create(current.Item1, true));
                var children = childSelector(current.Item1.Current);
                stack.Push(Tuple.Create(children.GetEnumerator(), false));
            }
            else
            {
                current.Item1.Dispose();
            }
        }
    }
    finally
    {
        foreach (var iterator in stack)
            iterator.Item1.Dispose();
    }
}

最后我们有一个测试用例，它对节点的值进行了排序，这样它们将打印出 1、2、3，...如果它们是按 post 顺序编写的：

string postOrderExample =
@"<node value='11'>
  <node value='4'>
    <node value='1'/>
    <node value='2'/>
    <node value='3'/>
  </node>
  <node value='10'>
    <node value='8'>
      <node value='5'/>
      <node value='7'>
        <node value='6'/>
      </node>
    </node>
    <node value='9'/>
  </node>
</node>";

var postOrderDoc = XDocument.Parse(postOrderExample);
query = PostOrder(new[] { postOrderDoc.Root }, node => node.Elements());
foreach (var node in query)
    Console.WriteLine(node.Attribute("value").Value);

c#中所有元素顺序XML前序后序遍历

All elements order in XML preorder and postorder traversal in c#

c#

xml

preorder

postorder