c#——树的深度，广度优先遍历与迭代器(IEnumerableT)的结合使用 ...

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› Node.js›Node.js教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

树是开发工作中比较常见的一种数据结构,园子里有很多文章介绍了对它的遍历，此处我们结合c#的迭代器机制,创建两种树的遍历方法。

static IEnumerable<T> DepthFirstTravel<T>(T root,Func<T,IEnumerable<T>> getChildren)
        {

            if (getChildren == null)
            {
                throw new ArgumentNullException(nameof(getChildren));
            }

            var nodeStack = new Stack<T>();
            nodeStack.Push(root);
            while (nodeStack.Count != 0)
            {
                var node = nodeStack.Pop();
                foreach (var child in getChildren(node))
                {
                    nodeStack.Push(child);
                }

                yield return node;
            }
        }
        static IEnumerable<T> BreadthFirstTravel<T>(T root, Func<T, IEnumerable<T>> getChildren)
        {
            if (getChildren == null)
            {
                throw new ArgumentNullException(nameof(getChildren));
            }

            var nodeQueue = new Queue<T>();
            nodeQueue.Enqueue(root);
            while (nodeQueue.Count != 0)
            {
                T node = nodeQueue.Dequeue();
                foreach (var child in getChildren(node))
                {
                    nodeQueue.Enqueue(child);
                }

                yield return node;
            }
        }