Работа с бинарным поисковым деревом - 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; }
}
}
}