using System;

using System.Collections;

using System.Collections.Generic;

using System.Text;

​

public class Program

{

    public static void Main(string[] args)

    {

        var tree = new BinaryTree<int>(9);

        tree.Add(7);

        tree.Add(15);

        tree.Add(5);

        tree.Add(8);

        tree.Add(13);

        tree.Add(17);

        tree.Add(14);

        tree.Add(18);

        //tree = new BinaryTree<int>(9)

        //{

        //    left = new BinaryTree<int>(7)

        //    {

        //        left = new BinaryTree<int>(5),

        //        right = new BinaryTree<int>(8)

        //    },

        //    right = new BinaryTree<int>(15)

        //    {

        //        left = new BinaryTree<int>(13)

        //        {

        //            right = new BinaryTree<int>(14),

        //        },

        //        right = new BinaryTree<int>(17)

        //        {

        //            right = new BinaryTree<int>(18)

        //        }

        //    }

        //};

​

        Console.WriteLine("Обход в глубину");

        var result = new StringBuilder();

        foreach (var i in CLR_in_depth(tree))

        {

            result.Append(i.ToString() + " ");

        }

        Console.WriteLine(result + "\n");

        result.Clear();

​

        Console.WriteLine("Обход в ширину");

        foreach (var i in CLR_in_width(tree))

        {

            result.Append(i.ToString() + " ");

        }

        Console.WriteLine(result + "\n");

    }

​

    private static IEnumerable CLR_in_depth<T>(BinaryTree<T> tree) where T : IComparable

    {

        var stack = new Stack<BinaryTree<T>>();

        stack.Push(tree);

        while (stack.Count > 0)

        {

            var node = stack.Pop();

            if (node != null)

            {

                stack.Push(node.Right);

                stack.Push(node.Left);

                yield return node.Value;

            }

        }

    }

​

    private static IEnumerable CLR_in_width<T>(BinaryTree<T> tree) where T : IComparable

    {

        var stack = new Queue<BinaryTree<T>>();

        stack.Enqueue(tree);

        while (stack.Count > 0)

        {

            var node = stack.Dequeue();

            if (node != null)

            {

                stack.Enqueue(node.Left);

                stack.Enqueue(node.Right);

                yield return node.Value;

            }

        }

    }

}

​

public class BinaryTree<T> where T : IComparable

{

    public readonly T Value;

    public BinaryTree<T> Left {  get; private set; }

    public BinaryTree<T> Right { get; private set; }

​

    public void Add(T key)

    {

        BinaryTree<T> node = this;

        BinaryTree<T> buffer = null;

        while (node != null)

        {

            buffer = node;

            if (key.CompareTo(node.Value) < 0)

                node = node.Left;

            else node = node.Right;

        }

​

        if (key.CompareTo(buffer.Value) < 0)

            buffer.Left = new BinaryTree<T>(key);

        else

            buffer.Right = new BinaryTree<T>(key);

    }

​

    public BinaryTree(T value)

    {

        this.Value = value;

    }

​

    public BinaryTree() 

    { 

        Value = default(T); 

    }

}