Работа с бинарным поисковым деревом - 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; } } } }
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д