#include <stdio.h> //Библиотека функций ввода и вывода
#include <stdlib.h> //Библиотека стандартных функций
#include <string.h> //Библиотека функций обработки строк
int Put(int); //Помещение значения в дерево
void Find(int **,int*); //Поиск ветви наибольшей длины
void Destroy(void); //Удаление всего дерева
/* --------------- Главная функция main ---------------- */
int main(int argc, char *argv[])
{
while(1){//Цикл ввода значений
char str[50]; //Буфер ввода
gets(str); //Ввод строки
if(strlen(str)==0) break;//Если строка пустая - выход
int val = atoi(str); //Преобразование к числу
if(val==0) continue; //Если не число, то продолжение
if(Put(val)){//Помещение в дерево, и если
puts("Мало памяти!"); //поместить не удалось, то
break; //вывод сообщения и выход
}
}
//Указатель на список значений вершин само длинной ветви
int *list = NULL, num = 0; //и их количество
Find(&list,&num); //Поиск самой длинной ветви дерева
Destroy(); //Удаление дерева
//Вывод значений вершин самой длинной ветви дерева
for(int i=0;i<num;i++) printf("%d\n",list[i]);
free(list); //Удаление списка вершин
return 0; //Выход
}
/* ------ Описание структуры и указателя на дерево ----- */
typedef struct _Element{
int value;
struct _Element *left, *right, *parent;
} Element;
Element *root = NULL;
/* --------- Функция добавления вершины в дерево ---------
Параметры: curr - указатель на вершину, к которой добавлять
новую вершину
value - значение новой вершины
Возвращаемое значение: 0 - успешное завершение
1 - ошибка выделения памяти
------------------------------------------------------- */
int Add(Element *curr, int value)
{
if(!curr){//Если указатель нулевой, то создание корня
//Выделение памяти под элемент
root = (Element *)malloc(sizeof(Element));
if(!root) return 1; //Если память не выделилась - выход
root->parent = NULL;//Инициализация связи с родителем
//Инициализация связи с потомками
root->left = root->right = NULL;
root->value = value; //Запись значения
}else{ //Иначе: не корневой элемент
//Если значение больше значения текущего элемента
if(curr->value < value){
//Если присутствует дочерний элемент слева, то
//вызов функции добавления к дочернему элементу
if(curr->left) return Add(curr->left,value);
}else{ //иначе: если меньше или равно
//Если присутствует дочерний элемент справа, то
//вызов функции добавления к дочернему элементу
if(curr->right) return Add(curr->right,value);
}
//Выделение памяти под новый элемент
Element *tmp = (Element*)malloc(sizeof(Element));
if(!tmp) return 1; //Если память не выделилась - выход
//Инициализация связей с дочерними элементами
tmp->right = tmp->left = NULL;
//Установка связи с родительским элементом
tmp->parent = curr;
tmp->value = value; //Запись значения
//Если значение нового элемента больше, чем значение
//текущего элемента, то добавление в левую ветвь.
//В противном случае - в правую
if(curr->value < value) curr->left = tmp;
else curr->right = tmp;
}
return 0; //Успешное завершение
}
/* --- Функция поиска ветви максимальной длины в дереве ---
Параметры: curr - указатель на текущую вершину
n - номер вершины от корня (1 - корень)
list - указатель на список, содержащий значения
вершин найденной ранее ветви (по ссылке)
num - количесвтво вершин в списке (по ссылке)
Возвращаемое значение: нет
------------------------------------------------------- */
void Step(Element *curr, int n, int **list, int *num)
{
if(!curr) return; //Если указатель нулевой, то выход
//Если это конечная вершина дерева (нет потомков)
if((!curr->left)&&(!curr->right)){
//Если номер текущей вершины меньше номера найденной
//ранее конечной вершины, то выход, так как эта ветвь
if(*num >= n) return; //не максимальной длины
//Если найдена новая ветвь максимальной длины, то
//удаление старого списка и создание нового
*num = n;
*list = (int *)realloc(*list,n*sizeof(int));
Element *tmp = curr;
for(int i=n-1;i>=0;i--){//Заполнение нового списка
(*list)[i] = tmp->value;
tmp = tmp->parent;
}
}else{
//Иначе: если это не конечная вершина, то рекурсия
Step(curr->left, n+1,list,num); //для левой ветви
Step(curr->right,n+1,list,num); //для правой ветви
}
}
/* ---------- Функция удаления вершины из дерева ----------
Параметры: curr - указатель на удаляемую вершину
Возвращаемое значение: нет
-------------------------------------------------------- */
void Del(Element *curr)
{
if(!curr) return; //Если нулевой указатель, то выход
//Удаление левой ветви, если она есть
if(curr->left) Del(curr->left);
//Удаление правой ветви, если она есть
if(curr->right) Del(curr->right);
free(curr); //Удаление элемента
}
/* ---------- Функция помещения значения в дерева ---------
Параметры: value - помещаемое значение
Возвращаемое значение: 0 - успешное завершение
1 - ошибка выделения памяти
-------------------------------------------------------- */
int Put(int value)
{
//Помещение нового элемента, начиная с корня дерева
return Add(root,value);
}
/* ------- Функция поиска ветви максимальной длины --------
Параметры: list - указатель на список (по ссылке)
num - количество элементов в списке (по ссылке)
Возвращаемое значение: нет
-------------------------------------------------------- */
void Find(int **list, int *num)
{
*list = NULL; //Инициализация указателя
*num = 0; //Инициализация количества
Step(root,1,list,num); //Вызов функции поиска с корня
}
/* ------------ Функция удаления всего дерева -------------
Параметры: нет
Возвращаемое значение: нет
-------------------------------------------------------- */
void Destroy(void)
{
Del(root); //Удаление корневого элемента
root = NULL; //Инициализация указателя на корень
}
