Найти максимальный элемент в бинарном дереве - C (СИ)
Формулировка задачи:
тип информационного поля int*, найти маскимальный элемент в дереве. (помогите, пожалуйста, нужен конкретный пример, чтобы разобраться)
Решение задачи: «Найти максимальный элемент в бинарном дереве»
textual
Листинг программы
#include <iostream.h>
struct Node
{
int Val;
Node *Left;
Node *Right;
};
void delTree(Node *root)
{
if ((root->Left == NULL) && (root->Right == NULL))
delete root;
else
if (root->Left == NULL)
{
delete root->Left;
delete root;
}
else
if (root->Right == NULL)
{
delete root->Right;
delete root;
}
else
{
delete root->Right;
delete root->Left;
delete root;
}
}
int min (int a, int b)
{
return ((a > b) ? b : a);
}
int minVal(Node *root)
{
if ((root->Left == NULL) && (root->Right == NULL))
return root->Val;
else
if (root->Left == NULL)
return min(root->Val,minVal(root->Right));
else
if (root->Right == NULL)
return min(root->Val,minVal(root->Left));
else
return min(root->Val,min(minVal(root->Left),minVal(root->Right)));
}
int main(int argc, char* argv[])
{
Node *Root,*Curr,*Next;
Root = new Node;
Root->Left =NULL;
Root->Right =NULL;
Root->Val=123;
Curr = new Node;
Curr->Left =NULL;
Curr->Right =NULL;
Curr->Val=56;
Root->Left=Curr;
Curr = new Node;
Curr->Left =NULL;
Curr->Right =NULL;
Curr->Val=66;
Root->Right=Curr;
Next = new Node;
Next->Left =NULL;
Next->Right =NULL;
Next->Val=16;
Curr->Right=Next;
cout << minVal(Root) << endl;
delTree(Root);
return 0;
}
Объяснение кода листинга программы
- Структура бинарного дерева реализована в виде динамического массива, элементы которого являются указателями на узлы.
- Рекурсивная функция для удаления дерева. Если узел пуст, то его следует удалить. Если узел не пуст, то нужно рекурсивно вызвать функцию для обоих поддеревьев и затем удалить узел.
- Рекурсивная функция для поиска минимального значения в дереве. Если узел пуст, то возвращается его значение. Если узел не пуст, то рекурсивно вызывается функция для обоих поддеревьев и затем возвращается минимальное значение.
- Создается дерево из 4 узлов.
- Рекурсивно вызывается функция для поиска минимального значения в дереве и выводится результат.
- Рекурсивная функция для удаления дерева вызывается для корня дерева.
- Все узлы освобождаются с помощью оператора delete.
- Возвращается 0, что означает успешное завершение программы.