Страница 1 из 1
Как посчитать количество листьев в n-арном дереве
Добавлено: 09 мар 2010, 17:21
Letcheg
Как задать n-арное дерево и посчитать количество листьев на языке С++
Re: Как посчитать количество листьев в n-арном дереве
Добавлено: 09 мар 2010, 18:35
Romeo
Можно так:
Код: Выделить всё
struct CNode
{
int nData; // some node data
CNode* pChildren; // pointer to array of child nodes
};
Если учесть, что в таком представлении нода будет являться листом, если у неё pChilder == NULL, то напрашивается простой алгоритм для вычисления количества листьев.
Код: Выделить всё
int GetLeafCount(CNode* pNode)
{
int nLeafCount = 0;
if (pNode->pChildren)
{
for (int i = 0; i < N; ++i)
{
nLeafCount += GetLeafCount(&pNode->pChildren[i]);
}
}
else
{
++nLeafCount;
}
return nLeafCount;
}
Re: Как посчитать количество листьев в n-арном дереве
Добавлено: 09 мар 2010, 18:50
IceFlame
Только в структуре должно быть:
Код: Выделить всё
struct CNode
{
int nData; // some node data
CNode** pChildren; // pointer to array of child nodes
};
Re: Как посчитать количество листьев в n-арном дереве
Добавлено: 09 мар 2010, 19:16
Romeo
Зачем двумерный массив? Одной звёздочки вполне достаточно. Создание и удаление масива "детей" будет выглядеть следующим образом:
Код: Выделить всё
CNode node;
// children array creation
node.pChildren = new CNode [N];
// children array freeing
delete [] node.pChildren;
Re: Как посчитать количество листьев в n-арном дереве
Добавлено: 09 мар 2010, 20:46
IceFlame
Ну тогда значит в массиве хранятся не указатели на детей, а они сами. Ну и соответственно
Код: Выделить всё
nLeafCount += GetLeafCount(&pNode->pChildren[i]);
Re: Как посчитать количество листьев в n-арном дереве
Добавлено: 09 мар 2010, 23:45
Romeo
Замечание резонно. Я исправил исходный кусок кода. Если код не править, то второй вариант - это использовать две звезды в объявлении. У подхода с двумя звёздами есть плюсы и минусы.
Плюсы. Это позволит избежать ограничения, которые вводятся для классов, тип которых будет использоваться для создания массивов. Также при резайзинге массива можно будет просто перепресвоить элементы, не выделяя заново память и не копируя.
Минусы. При конструировании дерева для каждого элемента массива нужно будет вызывать отдельный new, а это серьёзный удар по performance приложения.
Ввиду того, что ограничения меня никогда не пугали, а ресайзинг в нашем случае не нужен (так как "детей" всегда фиксированное число в силу определения n-арного дерева), ввиду всего этого, а также потому, что я ярый сторонник оптимизации приложений "по скорости," я бы выбрал массив объектов, а не массив поинтеров на объекты, иными словами я бы выбрал одну звёздочку в определении. Как поступишь ты - выбирай сам.
Re: Как посчитать количество листьев в n-арном дереве
Добавлено: 10 мар 2010, 21:03
Letcheg
На основе вашей подсказки родился следующий код:
Код: Выделить всё
// Derevo.cpp: определяет точку входа для консольного приложения.
//
#include "stdafx.h"
#include "iostream"
#include "conio.h"
using namespace std;
struct CNode {
int number;
char deti;
int data; // some node data
CNode* pChildren; // pointer to array of child nodes
};
int N,i;
int nn = 0;
int count = 0;
int Zapolnenie(CNode* pNode)
{
pNode->number = nn++;
cout << "Vi v vershine " << pNode->number << "\nDannie uzla ";
cin >> pNode->data;
if(pNode->deti == 1) {
cout << "Skoka detey? ";
int l; cin >> l;
if(l > 0) {
pNode->pChildren = new CNode[l];
pNode->deti = 2;
for(int qq = 0; qq < l; qq++) {(pNode->pChildren[qq]).deti = 1; }
Zapolnenie(&pNode->pChildren[0]);
}
if(l == 0) count++;
}
if(pNode->deti == 2) { for (int i = 1; i < N; i++)
if(&pNode->pChildren[i])
{Zapolnenie(&pNode->pChildren[i]); }
}
return(0);
}
int main() {
cout << "Vvedite N> "; cin >> N;
int j;
CNode* perv=new CNode[1];
perv->deti = 1;
Zapolnenie(perv);
cout << count;
getch();
}
Но он при многочисленных испытаниях выдает ошибку посмотрите опытным глазом можь чего увидите
Re: Как посчитать количество листьев в n-арном дереве
Добавлено: 11 мар 2010, 10:47
Romeo
Много чего неправильного. Зачем поле deti, я к примеру вообще не понял. Самая главная ошибка - рекурсивный вызов функции Zapolnenie сделан только для первого элемента массива детей. Нужно сделать на самом деле для всех. Ещё я не нашёл код, который очищает память, выделенную под дерево. Он должен быть обязательно:
Код: Выделить всё
// Derevo.cpp: определяет точку входа для консольного приложения.
//
#include "stdafx.h"
#include "iostream"
#include "conio.h"
using namespace std;
struct CNode
{
int number; // number of node
int data; // some node data
unsigned int nChildCount; // amount of chidren
CNode* pChildren; // pointer to array of child nodes
};
int nn = 0;
int count = 0;
void Zapolnenie(CNode* pNode)
{
pNode->number = nn++;
cout << "Vi v vershine " << pNode->number << "\nDannie uzla ";
cin >> pNode->data;
cout << "Skoka detey? ";
unsigned int l; cin >> l;
if (l > 0)
{
pNode->nChildCount = l;
pNode->pChildren = new CNode[l];
for (int qq = 0; qq < l; ++qq)
{
Zapolnenie(&pNode->pChildren[qq]);
}
}
else
{
pNode->nChildCount = 0;
pNode->pChildren = NULL;
++count;
}
}
void Udalenie(CNode* pNode)
{
if (pNode->nChildCount > 0)
{
for (int qq = 0; qq < pNode->nChildCount; ++qq)
{
Udalenie(&pNode->pChildren[qq]);
}
delete [] pNode->pChildren;
}
}
int main()
{
CNode node;
Zapolnenie(&node);
cout << "Kolichestvo list'ev: " << count;
getch();
Udalenie(&node);
return 0;
}
Теперь контроль понимания. Напиши функцию, которая будет выводить деверо. Вложенность нод должно визуализироваться отступами. Чем более глубокая вложенность ноды - тем больше отступ. Ноды, имеющие разных родителей, но один и тот же уровень вложенности, должны иметь одинаковый отспут.