Как посчитать количество листьев в n-арном дереве

[Letcheg]

Как задать n-арное дерево и посчитать количество листьев на языке С++

[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;
}

[IceFlame]

Только в структуре должно быть:

Код: Выделить всё

struct CNode
{
     int nData; // some node data
     CNode** pChildren; // pointer to array of child nodes
};

[Romeo]

Зачем двумерный массив? Одной звёздочки вполне достаточно. Создание и удаление масива "детей" будет выглядеть следующим образом:

Код: Выделить всё

CNode node;

// children array creation
node.pChildren = new CNode [N];

// children array freeing
delete [] node.pChildren;

[IceFlame]

Ну тогда значит в массиве хранятся не указатели на детей, а они сами. Ну и соответственно

Код: Выделить всё

nLeafCount += GetLeafCount(&pNode->pChildren[i]);

[Romeo]

Замечание резонно. Я исправил исходный кусок кода. Если код не править, то второй вариант - это использовать две звезды в объявлении. У подхода с двумя звёздами есть плюсы и минусы.

Плюсы. Это позволит избежать ограничения, которые вводятся для классов, тип которых будет использоваться для создания массивов. Также при резайзинге массива можно будет просто перепресвоить элементы, не выделяя заново память и не копируя.

Минусы. При конструировании дерева для каждого элемента массива нужно будет вызывать отдельный new, а это серьёзный удар по performance приложения.

Ввиду того, что ограничения меня никогда не пугали, а ресайзинг в нашем случае не нужен (так как "детей" всегда фиксированное число в силу определения n-арного дерева), ввиду всего этого, а также потому, что я ярый сторонник оптимизации приложений "по скорости," я бы выбрал массив объектов, а не массив поинтеров на объекты, иными словами я бы выбрал одну звёздочку в определении. Как поступишь ты - выбирай сам.

[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();

}

Но он при многочисленных испытаниях выдает ошибку посмотрите опытным глазом можь чего увидите

[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;
}

Теперь контроль понимания. Напиши функцию, которая будет выводить деверо. Вложенность нод должно визуализироваться отступами. Чем более глубокая вложенность ноды - тем больше отступ. Ноды, имеющие разных родителей, но один и тот же уровень вложенности, должны иметь одинаковый отспут.