Oct 22, 2014

Easy hierarchy traversal w/o recursion

    class Program
    {
        static void Main(string[] args)
        {
            Node n1 = new Node(null, "1. table");
            Node n2 = new Node(null, "2. chair");
            Node n11 = new Node(n1, "1.1. teapot");
            Node n12 = new Node(n1, "1.2. cup");
            Node n121 = new Node(n12, "1.2.1. tea");
            Node n21 = new Node(n2, "2.1. man");
 
            var topLevel = new Node[] { n1, n2 };
            var flat = Traverse(topLevel);
            foreach (var n in flat.OrderBy(n=>n.name))
            {
                Console.WriteLine(new string('\t', n.level) + n.name);
            }
            Console.ReadLine();
        }
 
        static IEnumerable<Node> Traverse(IEnumerable<Node> top)
        {
            Stack<Node> s = new Stack<Node>(top);
            while (s.Count > 0)
            {
                var next = s.Pop();
                yield return next;
                foreach (var n in next.nodes)
                {
                    s.Push(n);
                }
            }
        }
    }
 
    class Node
    {
        public int level;
        public List<Node> nodes = new List<Node>();
        public string name;
        public Node(Node parent, string name)
        {
            this.name = name;
            if (parent != null)
            {
                parent.nodes.Add(this);
                level = parent.level + 1;
            }
            else
            {
                level = 0;
            }
        }
    }


No comments:

Post a Comment