C++: произвольное дерево из чисел с ограниченным количеством потомков узла

Ниже приведён листинг простого примера на работу с произвольным деревом чисел (см. поле info структуры). Так как узлы сравниваются между собой по значениям info, все они предполагаются разными. В реальном приложении можно оценивать это info как идентификатор записи, добавив в структуру любые произвольные данные.

По условию задачи, максимальное количество потомков ограничиваем константным значением COUNT. Заметим, что в реальных приложениях память всё равно лучше выделять некоторыми "порциями", как, собственно, и делают стандартные контейнеры STL. Каждый раз "перевыделять" оперативку функциями вроде realloc чревато "дырками" в памяти приложения, а всё время делать delete и new при добавлении нового элемента в контейнер слишком не экономично.

В принципе, подобный листинг есть и вот здесь, только с malloc и "опасной" realloc. Также здесь дерево выводится в консоль в "древовидной" форме и есть метод для удаления поддерева.

Код проверен в Visual Studio 2010 Express, где благополучно сработал.

/* Простой пример на произвольное дерево из чисел info, 
максимальное количество потомков ограничено */
#include <cstdio>
#include <cstdlib>

const int COUNT = 10; //макс. количество потомков
struct tree { //произвольное дерево
 int info; //информационное поле
 tree **childs; //указатель на массив потомков
 int count; //количество потомков - для удобства
};

void error (int n) { //Сообщения об ошибках и выход
 switch (n) {
 case 0: printf("\nNormal stutdown"); break;
 case 1: printf("\nNo memory!"); break;
 case 2: printf("\nToo many child items!"); break;
 default: printf("\nUnknown error!"); break;
 }
 fflush(stdin);  getchar(); exit(n);
}

tree *init (tree *p, int info) { //Инициализация узла
 p->info = info; p->childs = nullptr; p->count = 0; return p;
}

void print1 (tree *p) { //Вывод одного узла
 printf ("Item %d (%d childs)\n",p->info,p->count);
}

void print (tree *p, int tab=0) { //Вывод всего дерева (поддерева) с узла p
 print1 (p);
 for (int i = 0; i < p->count; i++) {
  for (int k=0; k<=tab; k++) printf ("\t");
  print (p->childs[i],++tab);
  --tab;
 }
}

tree *search (tree *t, int info) { //Поиск в дереве t узла со значением info
 if (t->info == info) return t;
 else if (t->count>0) {
  for (int i = 0; i < t->count; i++) {
   tree *p = search(t->childs[i], info); //рекурсия!
   if (p != nullptr) return p;
  }
  return nullptr;
 }
 else return nullptr;
}

tree *search_parent (tree *t, tree *p) { //Поиск в дереве t родителя для узла p
 if (t->count>0) {
  for (int i=0; i<t->count; i++) {
   if (t->childs[i]->info==p->info) return t;
   else {
    tree *s=search_parent (t->childs[i],p);
    if (s != nullptr) return s;
   }
  }
  return nullptr;
 }
 else return nullptr;
}

tree *add (tree *ptr, int parentinfo, int info) { 
 //Добавление потомка со значением info родителю с parentinfo
 tree *p = search (ptr, parentinfo); //ищем в дереве родителя
 if (p) {
  if (p->count == 0) {
   p->childs = new tree * [COUNT];
   if (p->childs == nullptr) error(1);
   p->childs[0] = new tree;
   if (p->childs[0] == nullptr) error(1);
   p->count = 1;
  }
  else if (p->count < COUNT-1) {
   p->childs[p->count] = new tree;
   if (p->childs[p->count] == nullptr) error(1);
   p->count++;
  }
  else error (2);
  return init(p->childs[p->count - 1], info);
 }
 return nullptr;
}

void remove (tree *t, tree *p) { //Удаление из дерева t узла p и его потомков
 tree *item = search(t, p->info);
 if (item) {
  tree *parent = search_parent (t, item);
  if (parent) { //Есть родитель - "сжать" массив его потомков
   for (int i=0; i<parent->count; i++) if (parent->childs[i]->info==item->info) {
    for (int k=i; k<parent->count-1; k++) parent->childs[k]=parent->childs[k+1];
    parent->count--;
   }
  }
  if (item->count>0) {
   for (int i = item->count-1; i>-1; i--) {
    remove (t,item->childs[i]);
   }
   item->count = 0;
  }
  delete item;
 }
}

int main(void) {
 tree head; //один узел есть сразу
 init(&head,1);
 tree *ptr = &head;
 
 add(ptr, 1, 2); //узел "2" - потомок "1"
 add(ptr, 1, 3);
 add(ptr, 1, 4);
 tree *ptr2=add(ptr, 2, 5); 
  //сохраним указатель на узел "5" для последующего удаления этого поддерева
 add(ptr, 2, 6);
 add(ptr, 5, 7);
 add(ptr, 7, 8);
 add(ptr, 6, 9);
 
 printf("\nSearch test: ");
 tree *s = search(ptr,5);
 if (s) print1(s); else printf("Not found");
 
 printf("\nAll items:\n");
 print(ptr);

 remove (ptr,ptr2);
 printf("\nAll items after deleting:\n");
 print(ptr);

 error(0);
}

Вот что вывело это приложение:

Search test: Item 5 (1 childs)

All items:
Item 1 (3 childs)
        Item 2 (2 childs)
                Item 5 (1 childs)
                        Item 7 (1 childs)
                                Item 8 (0 childs)
                Item 6 (1 childs)
                        Item 9 (0 childs)
        Item 3 (0 childs)
        Item 4 (0 childs)

All items after deleting:
Item 1 (3 childs)
        Item 2 (1 childs)
                Item 6 (1 childs)
                        Item 9 (0 childs)
        Item 3 (0 childs)
        Item 4 (0 childs)

Normal stutdown

08.02.2017, 11:50 [5817 просмотров]