0

我需要一个函数来返回 C# 中所有元素的前序和后序，它返回所有元素的 (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;
    }
}
4

1 回答 1

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，表明它们正在以正确的顺序进行处理。

发布顺序非常相似，但需要进行一些调整。基本上我们想要做的是拥有完全相同的算法，但在处理完所有子项后生成每个项目。首先要做的是复制粘贴相同的算法，然后删除 `yield. 现在，在我们的算法中，我们知道在哪里处理了一个项目的所有子项吗？

好吧，就在我们从堆栈中弹出一个迭代器之后，该Current迭代器的项目刚刚处理了它的所有项目。好吧，也就是说，除非我们根本还没有调用MoveNext那个迭代器，在这种情况下没有 current item。所以，如果有一个项目，我们应该让出它。

可悲的是，没有办法，给定一个IEnumerator, 知道它是否已经MoveNext调用它了。我们可以创建一个新类型来包装一个IEnumerator并跟踪它是否已经启动。这实际上可能是一个好主意，但是由于这仅在这一种方法中使用，所以我作弊了一点，只是使用 aTuple<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);
于 2015-05-21T17:43:47.977 回答