Поиск наибольшего элемента дерева - C#
Формулировка задачи:
Помогите, написать функцию, которая находит наибольший элемент дерева.
Разработаны универсальные классы, но задача не получается.
using System; namespace Tree { class tree<BT> where BT : struct, IComparable<BT> // использованы ограничения на тип BT: это тип значений, причем сравнимых { public class node { public BT inf; public node L, R; }; node root; // указатель на корень дерева private static node in_tree_r(node R, BT x) // рекурсивный метод добавления элемента в дерево { if (R != null) if (x.CompareTo(R.inf) < 0) // если x<R.inf R.L = in_tree_r(R.L, x); else R.R = in_tree_r(R.R, x); else { R = new node(); R.L = null; R.R = null; R.inf = x; } return R; } private static node out_tree(node R, BT x) // рекурсивный метод удаления элемента из дерева { node P, v; if (R == null) { Console.WriteLine("Дерево не содержит элемента со значением {0}", x); return R; } else if (x.CompareTo(R.inf) < 0) // если x<R.inf R.L = out_tree(R.L, x); else if (x.CompareTo(R.inf) > 0) // если x>R.inf R.R = out_tree(R.R, x); else { P = R; if (R.R == null) R = R.L; // случай 1 - у удаляемого узла не более одного поддерева else if (R.L == null) R = R.R; // случай 1 - у удаляемого узла не более одного поддерева else // случай 2 - у удаляемого узла два поддерева { v = R.L; if (v.R != null) { while (v.R.R != null) v = v.R; R.inf = v.R.inf; P = v.R; v.R = v.R.L; } else { R.inf = v.inf; P = v; R.L = R.L.L; } } // закончили случай 2 } // закончили удаление return R; } private static void print_tree(node R) // рекурсивный метод вывода элементов дерева { if (R != null) { print_tree(R.L); Console.Write("{0}; ", R.inf); print_tree(R.R); } } private static bool find_el(node R, BT x) // рекурсивный метод; возвращает true, если x есть в дереве и false в противном случае { if (R == null) return false; else if (x.CompareTo(R.inf) == 0) // если x==R.inf return true; else if (x.CompareTo(R.inf) < 0) // если x<R.inf return find_el(R.L, x); else return find_el(R.R, x); } public void in_t(BT x) { root = in_tree_r(root, x); } public void print() { print_tree(root); Console.WriteLine(); Console.WriteLine(); } public bool find(BT x) { return find_el(root, x); } public void out_t(BT x) { root = out_tree(root, x); } public void create_t() // создание дерева с заданным количеством элементов { BT x; root = null; Console.WriteLine("Сколько элементов в дереве? "); int n = Convert.ToInt32(Console.ReadLine()); for (int i = 1; i <= n; i++) { Console.Write("Очередной элемент? "); x = (BT)Convert.ChangeType(Console.ReadLine(), typeof(BT)); // конвертируем введенное значение к нужному типу in_t(x); } } private static void s7(node R, ref node p) // рекурсивный метод, решающий поставленную задачу { if (R != null) { while (R.R != null) { p = R.R; s7(R.R, ref p); } } } public int solution7(int n) { int k = 0; s7(root, n, 0, ref k); return k; } }; class Program { static void Main() { tree<int> T = new tree<int>(); T.create_t(); T.print(); Console.WriteLine("Количество узлов на уровне {0} равно {1}", 3, T.solution7(3)); Console.ReadKey(); } } }
Решение задачи: «Поиск наибольшего элемента дерева»
textual
Листинг программы
class tree<BT> where BT : struct, IComparable<BT> { .... public static IEnumerable<node> GetThisAndAllChilds(node n) { if(n != null) { yield return n; foreach (var child in GetThisAndAllChilds(n.L)) yield return child; foreach (var child in GetThisAndAllChilds(n.R)) yield return child; } } public node Max() { var max = root; foreach (var n in GetThisAndAllChilds(root)) if (n.inf.CompareTo(max.inf) > 0) max = n; return max; } }
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д