using System;
using System.Linq;
using System.Text;
using Unit4.CollectionsLib;

namespace Lab08_02
{
    class Program
    {
        public static Random rnd = new Random();
        public static BinTreeNode<int> RandomSearchTree()
        {

            BinTreeNode<int> t = new BinTreeNode<int>(rnd.Next(1, 100));
            for (int i = 0; i < 2; i++)
            {
                AddTosearchTree(t, rnd.Next(1, 100));
            }
            return t;
        }

        public static void AddTosearchTree(BinTreeNode<int> t, int x)
        {
            if (t.GetRight() == t.GetLeft())
            {
                if (t.GetInfo() > x)
                    t.SetLeft(new BinTreeNode<int>(x));
                else
                    t.SetRight(new BinTreeNode<int>(x));
            }
            else
            {
                if (t.GetLeft() == null)
                {
                    if (t.GetInfo() >= x)
                        t.SetLeft(new BinTreeNode<int>(x));
                    else
                        AddTosearchTree(t.GetRight(), x);
                }
                else
                {
                    if (t.GetRight() == null)
                    {
                        if (t.GetInfo() < x)
                            t.SetRight(new BinTreeNode<int>(x));
                        else
                            AddTosearchTree(t.GetLeft(), x);
                    }
                    else
                        if (t.GetInfo() >= x)
                            AddTosearchTree(t.GetLeft(), x);
                        else
                            AddTosearchTree(t.GetRight(), x);

                }

            }
        }

        public static bool IfExist(int num, BinTreeNode<int> tr)
        {
            if (tr.GetRight() == tr.GetLeft())
                return false;
            if (num == tr.GetInfo())
                return true;
            if (tr.GetInfo() > num)
            {
                if (tr.GetLeft() == null)
                    return false;
                return IfExist(num, tr.GetLeft());
            }
            else if (tr.GetInfo() < num)
            {
                if (tr.GetRight() == null)
                    return false;
                return IfExist(num, tr.GetRight());
            }
            return false;
        }


        public static BinTreeNode<int> ArrayToSearchTree(int[] arr)
        {
            BinTreeNode<int> t = new BinTreeNode<int>(arr[0]);
            for (int i = 0; i < arr.Length; i++)
            {
                AddTosearchTree(t, arr[i]);
            }
            return t;
        }

        private static Queue<int> q = new Queue<int>();
        public static void PostOrder(BinTreeNode<int> t)
        {
            if (t != null)
            {
                PostOrder(t.GetLeft());
                PostOrder(t.GetRight());
                q.Insert(t.GetInfo());
            }
        }
        public static BinTreeNode<int> CombineSearchTrees(BinTreeNode<int> t1, BinTreeNode<int> t2)
        {
            PostOrder(t1);
            PostOrder(t2);
            if (!q.IsEmpty())
            {
                BinTreeNode<int> t = new BinTreeNode<int>(q.Remove());
                while (!q.IsEmpty())
                {
                    AddTosearchTree(t, q.Remove());
                }
                return t;
            }
            return new BinTreeNode<int>(0);
        }

        public static bool IsSearchTree(BinTreeNode<int> t)
        {
            if (t.GetLeft() == t.GetRight())
                return true;
            else
            {
                if (t.GetLeft() != null)
                {
                    if (t.GetLeft().GetInfo() > t.GetInfo())
                        return IsSearchTree(t.GetLeft());
                    return false;
                }
                if (t.GetRight() != null)
                {
                    if (t.GetRight().GetInfo() <= t.GetInfo())
                        return IsSearchTree(t.GetRight());
                    return false;
                }
                return IsSearchTree(t.GetLeft()) && IsSearchTree(t.GetRight());
            }
        }


        static void Main(string[] args)
        {
            BinTreeNode<int> t1 = RandomSearchTree();
            BinTreeNode<int> t2 = RandomSearchTree();
            BinTreeUtils.ShowTree(t1);
            BinTreeUtils.ShowTree(t2);
            BinTreeUtils.ShowTree(CombineSearchTrees(t1, t2));
        }
    }
}