所有元素在XML中排序，在c#中遍历后序

Question

我需要一个函数来返回c#中所有元素的preorder和postorder，它返回我所有元素的列表(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
.
.
.

我已经写了这个类，但它在大型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

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

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

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

从这里开始循环，只要有需要处理的迭代器。获取要处理的当前元素，如果它有子元素，则输出它的当前元素，将迭代器压回堆栈供后续处理，获取子元素的序列，将推入堆栈供后续处理。

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();
    }
}

这涵盖了我们的预排序算法，对于每个要处理的项，先生成它，然后处理所有子项。

下面是一个测试用例来演示它。它是一个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 order非常相似，但需要一些调整。基本上，我们想要做的是使用完全相同的算法，但是在处理完所有子条目后生成每个条目。首先要做的是复制粘贴相同的算法，并删除' yield '。现在，在我们的算法中，我们知道一个项的所有子项在哪里被处理了吗?

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

可悲的是，没有办法，给定一个IEnumerator，知道它是否有MoveNext调用它。我们可以创建一个新的类型来包装IEnumerator，并跟踪它是否已经启动。这实际上可能是一个好主意，但由于这只在这一个方法中使用，我欺骗了一点，只是使用Tuple<IEnumerator<T>, bool>来保存一个可能或可能没有开始的序列，将方法中IEnumerator<T>的所有使用替换为该元组，并根据我们是否知道我们已经向迭代器请求值设置布尔值。

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，…如果它们是以后序书写的:

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);