Поиск наибольшего элемента дерева - 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;
        }
    }

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

6   голосов , оценка 3.5 из 5
Похожие ответы