Работа с бинарным поисковым деревом - C#

Узнай цену своей работы

Формулировка задачи:

Имеется такая вот задачка: Условие Найти вершины, через которые проходит нечетное число путей максимальной длины, и удалить (правым удалением) ту из них, ключ которой наибольший. Если в дереве нет вершин, удовлетворяющих нужному свойству, то ничего удалять не требуется. Выполнить прямой (левый) обход полученного дерева. Замечание Если в дереве нет вершин, удовлетворяющих нужному свойству, то ничего из дерева удалять не надо. Входные данные tst.in содержит последовательность чисел — ключей дерева. Выходные данные tst.out содержит массив вершин, полученный прямым левым обходом итогового дерева. Пример tst.in 10 5 20 4 6 15 30 3 7 14 40 8 50 9 60 tst.out 10 5 4 3 6 7 8 9 20 15 14 30 40 50 Буду рад любой помощи в реализации задачки, особенно интересует реализация самого дерева и поиск количества путей проходящих через вершину. З.Ы. О_о Пошел гуглить...

Решение задачи: «Работа с бинарным поисковым деревом»

textual
Листинг программы
//поиск максимального пути
        static int max = 0;
        static void put()
        {
            for (int j = 0; j < L.Count; j++)
            {
                Item x = L[j];
                int xg = G[j]; //глубина
                for (int i = 0; i < L.Count; i++)
                {
                    Item y = L[i];
                    int yg = G[i]; //глубина
                    int p = 0;
                    while ((x != root && y != root) /*|| (x != y)*/)
                    {                      
                        if (x == y && x.lSon == null && x.rSon == null && y.lSon == null && y.rSon == null) { p = 0; break; }
                        if (x == y && y != root && x != root && x.lSon != null && x.rSon != null && y.lSon != null && y.rSon != null) { p = p - 1; break; }
                        if ((x != y) && (x.lSon == null || x.rSon == null))
                        {
                            while ((x.rSon == null) || (x.lSon == null))
                            {
                                x = x.father;
                                p = p + 1;
                                xg--;
                            }
                        }
                        if ((x != y) && (y.lSon == null || y.rSon == null))
                        {
                            while ((y.rSon == null) || (y.lSon == null))
                            {
                                y = y.father;
                                p = p + 1;
                                yg--;
                            }
                        }
                        if (y == root)
                        {
                            while (x != root)
                            {
                                x = x.father;
                                p++;
                                xg--;
                            }
                        }
                        if (x == root)
                        {
                            while (y != root)
                            {
                                y = y.father;
                                p++;
                                yg--;
                            }
                        }
 
                        if ((x != y) && (x.lSon != null) && (x.rSon != null) && (y.lSon != null) && (y.rSon != null) && (xg > yg))
                        {                            
                            { x = x.father; p = p + 1; xg--; }
                        }
 
                        if ((x != y) && (x.lSon != null) && (x.rSon != null) && (y.lSon != null) && (y.rSon != null) && (xg < yg))
                        {
                            { y = y.father; p = p + 1; yg--; }
                        }
                        if ((x != y) && (x.lSon != null) && (x.rSon != null) && (y.lSon != null) && (y.rSon != null) && (xg == yg))
                        {
                            { x = x.father; p = p + 1; xg--; }
                            { y = y.father; p = p + 1; yg--; }
                        }
 
                        if (x == y && x == root && y == root) { p = p - 1; break; }
                    }
                    Console.WriteLine("длинны " + p);
                    if (max < p) { max = p; }
                }
           }
        }

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

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