RFpro.ru: Программирование на C / C++
Хостинг портала RFpro.ru: РАССЫЛКИ ПОРТАЛА RFPRO.RU
Лучшие эксперты по данной тематике
/ КОМПЬЮТЕРЫ И СОФТ / Программирование / C/C++
Консультация # 185916: Здравствуйте! Прошу помощи в следующем вопросе: Требуется написать несколько функций, связанных с двоичными деревьями, а именно: 1)Подсчет числа узлов двоичного дерева 2)Подсчет числа листьев двоичного дерева 3)Подсчет степени двоичного дерева 4)Подсчет степени вершины двоичного дерева И, если не сложно, прошу написать... Здравствуйте! Прошу помощи в следующем вопросе:
Дата отправки: 27.04.2012, 19:14 Консультирует Лысков Игорь Витальевич (Старший модератор): Здравствуйте, Барс Иван! Код : struct Node
{
int key;
Node *next;
Node *child;
};где Node.next - следующий элемент в текущем списке "братьев", Node.child - указатель на первый элемент списка потомков. Программа: Код : #include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <conio.h>
struct Node
{
int key; //ключ
Node *left; //левое поддерево
Node *right; //правое поддерево
};
void del(Node *node) //удаление дерева, начиная с корня
{
if (node != 0) //если не пустое
{
del(node->left) ; //удаляем левое поддерево
del(node->right) ; //правое
free(node); //сам узел
}
}
Node* insert( Node *node, int x ) //вставка узла в дерево
{
if (node==0) //узел пустой
{ //создаем
node = (Node *) malloc (sizeof(Node));
node->key = x ; //пишем ключ
node->left = node->right = 0 ; //и помечаем, что без потомков
} //узел есть
else if (x<=node->key) //новый ключ меньше или равно
node->left = insert (node->left, x); //вставляем в левое поддерево
else
node->right = insert (node->right, x); //иначе - в правое
return node ; //вернем корень
}
//подсчет всех узлов дерева, count - адрес переменной, в которой должен быть 0
void CalcAllNodes(Node *node, int *count)
{
if (node != NULL) //узел непустой?
{
(*count)++; //считаем себя
CalcAllNodes(node->left, count); //всех в левом поддереве
CalcAllNodes(node->right, count); //и в правом
}
}
//подсчет листьев (узлов без потомков)
void CalcLeafNodes(Node *node, int *count)
{
if (node == NULL) //узла нет - выходим
return;
if ((node->left == NULL) && (node->right == NULL)) //нет потомков - лист!
(*count)++; //считаем!!!
else
{ //иначе - считаем в левом поддереве и в правом
CalcLeafNodes(node->left, count);
CalcLeafNodes(node->right, count);
}
}
//подсчет степени дерева (максимальной длины цепочки потомков)
int CalcTreeLevel(Node *node)
{
if (node == NULL) //узла нет - выходим
return 0;
else //есть - считаем себя и максимальную из левого
return (1 + __max ( CalcTreeLevel(node->left), //и правого поддерева
CalcTreeLevel(node->right) ));
}
//подсчет степени узла (числа потомков)
//сначала ищем узел по ключу, затем в level пишем степень вершины, возвращаем true
//если узел не найден - возвращаем false
bool CalcNodeLevel(Node *node, int key, int *level)
{
if (node != NULL) //проверяем, есть и узел
{
if (node->key == key) //сравниваем ключ, и если равен, то
{ //возвращаем число потомков
*level = (node->left != NULL) + (node->right != NULL);
return true; //и true
} //ключ не равен, ищем дальше
if (CalcNodeLevel(node->left, key, level)) //в левом поддереве
return true; //если там найден, то выходим
if (CalcNodeLevel(node->right, key, level)) //и правом поддереве
return true; //если там найден, то выходим
}
return false; //ключ не найден
}
int main(void)
{
Node *root = NULL; //корень дерева
//зададим ключи для построения дерева
int d[15] = {10,5,15,1,8,3,6,9,12,2,18,13,21,11,4};
int count, level;
for (int i=0; i<15; i++) //построим дерево
root = insert(root, d[i]);
count = 0; //считаем все узлы
CalcAllNodes(root, &count);
printf ("Nodes count = %d\n", count);
count = 0; //листья
if (root) //сначала надо проверить на наличие корня
CalcLeafNodes(root, &count);
printf ("Leafs count = %d\n", count);
//степень дерева
printf ("Tree level = %d\n", CalcTreeLevel(root));
//найдем степень разных узлов
if (CalcNodeLevel(root, 9, &level)) //у которой 0 потомков
printf ("Node 9 level = %d\n", level);
else
printf("Node 9 not found\n");
if (CalcNodeLevel(root, 18, &level)) //1 потомок
printf ("Node 18 level = %d\n", level);
else
printf("Node 18 not found\n");
if (CalcNodeLevel(root, 12, &level)) //2 потомка
printf ("Node 12 level = %d\n", level);
else
printf("Node 12 not found\n");
if (CalcNodeLevel(root, 19, &level)) //нет узла
printf ("Node 19 level = %d\n", level);
else
printf("Node 19 not found\n");
del(root); //удалим дерево
_getch();
return 0;
}
Оценить выпуск | Задать вопрос экспертам
главная страница
|
стать участником
|
получить консультацию
© 2001-2012, Портал RFPRO.RU, Россия
Авторское право: ООО "Мастер-Эксперт Про" Калашников О.А. | Гладенюк А.Г. Хостинг: Версия системы: 2011.6.36 от 26.01.2012 |
| В избранное | ||
