Trees

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Library
{
    public class ForTree
    {
        public class Tree
            // Инициализация бинарного дерева
        {
            public char data;
            public Tree left,     //адрес левого поддерева
                        right;    //адрес правого поддерева
            public Tree()
            {
                data = '0';
                left = null;
                right = null;
            }
            public Tree(char d)
            {
                data = d;
                left = null;
                right = null;
            }
            public override string ToString()
            {
                return data + " ";
            }

        }

        static Tree MakeTree(char value)
            //Создание элемента типа Tree
        {
            Tree p = new Tree(value);
            return p;
        }

        static char GetValue()
            // Создание элемента типа char, ввод с клавиатуры
        {
            char info = CheckChar();
            return info;
        }

        static char GetValue(Random rnd)
            // Создание элемента типа char с помощью ДСЧ
        {
            char info = (char)rnd.Next(33, 122); //Явное преобразование типов
            return info;
        }

        static char CheckChar()
            // Проверка элемента для добавления в дерево (вручную)
        {
            Console.WriteLine("Введите элемент (тип char)");
            bool ok;
            char info;
            do
            {
                string buf = Console.ReadLine();
                ok = Char.TryParse(buf, out info);
                if (!ok)
                    Console.WriteLine("Символ char введен неверно. Повторите ввод.");
            } while (!ok);
            return info;
        }

        public static Tree IdealTree(int size)
            // Формирование идеально сбалансированного дерева
            // Заполнение с клавиатуры
        {
            if (size == 0) return null;
            int nl = size / 2;
            int nr = size - nl - 1;
            char number = GetValue();
            Tree r = MakeTree(number);
            r.left = IdealTree(nl);
            r.right = IdealTree(nr);
            return r;
        }

        public static Tree IdealTree(int size, Random rnd)
            // Формирование идеально сбалансированного дерева
            // Заполнение random
        {
            if (size == 0) return null;
            int nl = size / 2;
            int nr = size - nl - 1;
            char number = GetValue(rnd);
            Tree root = MakeTree(number);
            root.left = IdealTree(nl, rnd);
            root.right = IdealTree(nr, rnd);
            return root;
        }

        public static Tree FormTree()
            // Заполнение бинарного дерева с выбором
        {
            Console.WriteLine("Введите размер дерева");
            int size = Arrays.InputNatNumber();
            Tree idTree = null;
            Random rnd = new Random();
            bool ok = false;
            do
            {
                Console.ForegroundColor = ConsoleColor.White;
                Console.WriteLine("\nКак будем заполнять дерево?" +
                                  "\n1. Ввод с клавиатуры" +
                                  "\n2. Автозаполнение с помощью random");
                string MakeTree = Console.ReadLine();
                switch (MakeTree)
                {
                    case "1":
                        idTree = IdealTree(size);
                        ok = true;
                        break;
                    case "2":
                        idTree = IdealTree(size, rnd);
                        ok = true;
                        break;
                    default:
                        Console.ForegroundColor = ConsoleColor.Red;
                        Console.WriteLine("Неверный номер команды. Повторите ввод ");
                        break;
                }
            } while (!ok);
            Console.ResetColor();
            return idTree;
        }

        public static Tree Add(Tree root, char info)
            // Добавление элемента в дерево поиска
        {
            if (root == null || root.data == '0')
                return MakeTree(info);
            Tree tek = root;
            Tree anc = null;
            while (tek != null) //спускаемся "вниз" дерева
            {
                anc = tek;
                if (info == tek.data)
                {
                    Console.WriteLine("Элемент {0} уже существует в дереве", info);
                    return root;
                }
                else if (info > tek.data) //если элемент больше текущего
                    tek = tek.right; //идем вправо
                    else
                        tek = tek.left;  //идем влево
            }
            tek = MakeTree(info);
            if (tek.data > anc.data)
                anc.right = tek; //добавление в правую часть
            else
                anc.left = tek; //добавление в левую часть
            return root;
        }

        public static void BuildSearchTree(Tree idTree, ref Tree srch)
            //Построение дерева поиска
        {
            srch = Add(srch, idTree.data);
            if (idTree.left != null)
                BuildSearchTree(idTree.left, ref srch);
            if (idTree.right != null)
                BuildSearchTree(idTree.right, ref srch);
        }

        public static int CountElems(char value, Tree root)
            //Подсчет количества элементов с заданным ключом
        {
            int number = 0;
            if (value == root.data)
                number++;
            if (root.left != null)
                number += CountElems(value, root.left);
            if (root.right != null)
                number += CountElems(value, root.right);
            return number;
        }

        public static void WorkWithTree()
        {
            Tree idTree = FormTree();
            Console.WriteLine("Исходное дерево: ");
            ShowTree(idTree, 10);
            Console.WriteLine("Элемент для поиска ");
            char elem = CheckChar();
            int kolvo = CountElems(elem, idTree);
            if (kolvo == 0) Console.WriteLine("Элемента с заданным значением нет в дереве");
            else
                Console.WriteLine("Элемент {0} встречается {1} раз ", elem, kolvo);

            Tree SearchTree = new Tree();
            BuildSearchTree(idTree, ref SearchTree);
            idTree = SearchTree;
            Console.WriteLine("Перестроенное в дерево поиска: ");
            ShowTree(SearchTree, 10);
        }

        public static void ShowTree(Tree root, int l)
            // Печать дерева
        {
            if (root != null)
            {
                ShowTree(root.right, l + 3);     //переход к правому поддереву
                //формирование отступа
                for (int i = 0; i < l; i++) Console.Write(" ");
                Console.WriteLine(root.data);   //печать узла
                ShowTree(root.left, l + 3);     //переход к левому поддереву
            }
        }
    }
}