代码之家 › 专栏 › 技术社区 › Natalie Perret

迭代遍历BFS或DFS时,如何获取当前访问级别的信息?

visitor breadth-first-search depth-first-search .net c#

Natalie Perret · 技术社区 · 6 年前

我正在考虑创建自己的序列化程序,我需要一种简单的方法来为给定的.NET类型编写属性访问者,以便获取每个属性(包括嵌套属性)的属性。

似乎最简单的方法是从DFS或BFS的迭代版本开始遍历所有属性,所以我开始编写以下代码:

public static class Algorithms
{
    public static IEnumerable<TNode> DfsIterativeTraverse<TNode>(this TNode node, Func<TNode, IEnumerable<TNode>> childNodeSelectors) 
    {
        if (node == null)
        {
            yield break;
        }

        var stack = new Stack<TNode>();
        stack.Push(node);

        while (stack.Any()) 
        {
            var top = stack.Pop();
            foreach (var child in childNodeSelectors(top)) 
            {
                stack.Push(child);
            }
            yield return top;
        }
    }
    public static IEnumerable<TNode> BfsIterativeTraverse<TNode>(this TNode node, Func<TNode, IEnumerable<TNode>> childNodeSelectors) 
    {
        if (node == null)
        {
            yield break;
        }

        var queue = new Queue<TNode>();
        queue.Enqueue(node);

        while (queue.Any()) 
        {
            var front = queue.Dequeue();
            foreach (var child in childNodeSelectors(front))
            {
                queue.Enqueue(child);
            }
            yield return front;
        }
    }
}

然后将其应用于某些匿名类以获取不同的属性:

public static class Program
{
    public static void Main(params string[] args)
    {
        var stuff = new
        {
            A1 = new
            {
                B1 = new
                {
                    D1 = 42
                },
                C1 = new
                {
                    E1 = "Hello"
                }
            },
            A2 = new
            {
                B2 = new
                {
                    D2 = 42
                },
                C2 = new
                {
                    E2 = "Hello"
                }
            }
        };

        var properties = stuff.GetType().GetProperties();

        foreach (var property in properties)
        {
            var childProperties = property.DfsIterativeTraverse(x =>
            {
                if (x.PropertyType.IsPrimitive|| x.PropertyType == typeof(string))
                {
                    return Enumerable.Empty<PropertyInfo>();
                }

                return x.PropertyType.GetProperties();
            });

            var count = 0;
            foreach (var childProperty in childProperties)
            {
                Console.WriteLine($"{$"\t".Repeat(count)}{childProperty.Name}: {childProperty.PropertyType.Name}");
                count++;
            }
        }

        Console.ReadKey();
    }
}

public static class StringExtensions
{
    public static string Repeat(this string source, int count)
    {
        var stringBuilder = new StringBuilder(source.Length * count);
        for (var i = 0; i < count; i++)
        {
            stringBuilder.Append(source);
        }

        return stringBuilder.ToString();
    }
}

但这段代码返回:

A1: <>f__AnonymousType1`2
        C1: <>f__AnonymousType3`1
                E1: String
                        B1: <>f__AnonymousType2`1
                                D1: Int32
A2: <>f__AnonymousType4`2
        C2: <>f__AnonymousType6`1
                E2: String
                        B2: <>f__AnonymousType5`1
                                D2: Int32

我考虑过增加一个计数,这个计数会递增,但结果并不是那么简单。

1 回复 | 直到 6 年前

astef 6 年前

其实很简单。

interface ILevel
{
    int Level { get; set; }
}


public static IEnumerable<TNode> DfsIterativeTraverse<TNode>(this TNode node, Func<TNode, IEnumerable<TNode>> childNodeSelectors)
    where TNode : class, ILevel
{
    if (node == null)
    {
        yield break;
    }

    var currentLevel = 0;
    node.Level = 0;

    var stack = new Stack<TNode>();
    stack.Push(node);

    while (stack.Any())
    {
        var top = stack.Pop();
        foreach (var child in childNodeSelectors(top))
        {
            child.Level = top.Level + 1;
            stack.Push(child);
        }
        yield return top;
    }
}

代码并不完美,因为它修改了节点,但是如果在您的情况下需要,您可以用更安全的方式重构它。无论如何,问题应该解决,因为现在每个节点都应该有 Level 具有初始化值的属性。