using System;

using System.Collections.Generic;

​

public class Program

{

    public static void Main()

    {

        Node<string> root = new Node<string>("root");

            {

                Node<string> node0 = root.AddChild("node0");

                Node<string> node1 = root.AddChild("node1");

                Node<string> node2 = root.AddChild("node2");

                {

                    Node<string> node20 = node2.AddChild(null);

                    Node<string> node21 = node2.AddChild("node21");

                    {

                        Node<string> node210 = node21.AddChild("node210");

                        Node<string> node211 = node21.AddChild("node211");

                        {

                            Node<string> node2110 = node211.AddChild("node2110");

                            Node<string> node2111 = node211.AddChild("node2111");

                            Node<string> node2112 = node211.AddChild("node2112");

                        }

                    }

                }

                Node<string> node3 = root.AddChild("node3");

                {

                    Node<string> node30 = node3.AddChild("node30");

                }

            }

​

            Console.WriteLine("BFS");

            BFS(root);

            Console.WriteLine("DFS");

            DFS(root);

            Console.Read();

    }

    public class Node<T>

        {

            public T data;

            public List<Node<T>> child;

            public Node<T> parent { get; set; }

​

            public Node(T Data){

                data = Data;

                child = new List<Node<T>>();

            }

            public Node<T> AddChild(T data)

            {

                Node<T> child = new Node<T>(data) { parent = this };

                this.child.Add(child);

                return child;

            }

        }

​

        //Обход в ширину

        static public void BFS<T>(Node<T> start)

        {

            Queue<Node<T>> queue = new Queue<Node<T>>();

            queue.Enqueue(start);

            while (queue.Count != 0)

            {

                Node<T> temp = queue.Dequeue();

                Console.WriteLine(temp.data);

                foreach (Node<T> el in temp.child)

                {

                    queue.Enqueue(el);

                }

            }

        }

​

        //Оьход в глубину

        static public void DFS<T>(Node<T> start)

        {

            Stack<Node<T>> queue = new Stack<Node<T>>();

            queue.Push(start);

            while (queue.Count != 0)

            {

                Node<T> temp = queue.Pop();

                Console.WriteLine(temp.data);

                foreach (Node<T> el in temp.child)

                {

                    queue.Push(el);

                }

            }

        }

}