Первый листинг реализует дерево, каждый узел которого может иметь произвольное число потомков. Соответственно, при описании структуры с типом tree достаточно указать конструкцию tree **childs;, которая будет служить указателем на текущий список узлов-потомков. Для простоты в нашем дереве всего одно информационное поле int info;, но в этом плане программу нетрудно расширить. Реализованы добавление, поиск, печать узлов.

#include <stdio.h>
#include <stdlib.h>
#include <alloc.h>
typedef struct tree {
 int info;
 tree **childs;
 unsigned count;
};
int const size1=sizeof(tree);

void error (int c) {
 printf ("\nError: ");
 switch (c) {
  case 1:  printf(" no memory"); break;
  default: printf(" unknown");   break;
 }
 exit (c);
}
tree *init (tree *p,int info) {
 p->info=info;
 p->count=0;
 p->childs=NULL;
 return p;
}
void print1 (tree *p) {
 printf ("\nnode %6d: %2d child(s)",
  p->info,p->count);
}
void printnode (tree *p) {
 print1 (p);
 for (int i=0; i<p->count; i++) 
  print1 (p->childs[i]);
}
tree *searchnode (tree *t, int info) {
 if (t->info == info) return t;
 else if (t->count>0) {
  for (int i=0; i<t->count; i++) {
   tree *p=searchnode (t->childs[i],info);
   if (p!=NULL) return p;
  }
  return NULL;
 }
 else return NULL;
}
tree *addnode (tree *ptr, int parentinfo, 
 int info) {
 tree *p=searchnode (ptr,parentinfo);
 if (p!=NULL) {
  if (p->childs==NULL) {
   p->childs = (tree **)malloc
    (sizeof(tree *));
   if (p->childs==NULL) error (1);
   p->childs[0]=(tree *)malloc(size1);
   if (p->childs[0]==NULL) error (1);
   (p->count)=1;
  }
  else {
   p->childs = (tree **)
   realloc(p->childs,sizeof(tree *)
    *(p->count+1));
   if (p->childs==NULL) error (1);
   p->childs[p->count]=(tree *)
    malloc(size1);
   if (p->childs[p->count]==NULL) 
    error (1);
   (p->count)++;
  }
  return init (p->childs[p->count-1],info);
 }
 return NULL;
}

void main () {
 tree head,temp,*ptr;
 ptr=&head;
 init(ptr,1);
 addnode (ptr,1,2);
 addnode (ptr,1,3);
 addnode (ptr,2,4);
 tree *s=searchnode (ptr,2);
 printf ("\n With node after search:");
 if (s!=NULL) printnode (s);
 else printf ("\nNULL");
 printf ("\n With root:");
 printnode (ptr);
 getchar ();
}

Во втором примере дерево - бинарное, то есть, у каждого узла лишь два потомка - левая и правая подветви, описанные указателями btree *left,*right;. Это дает возможности удобного рекурсивного поиска и обхода.

#include <stdio.h>
#include <iostream.h>
#include <string.h>
#include <alloc.h>

typedef struct btree {
 int val;
 btree *left,*right;
};

//----- Рекурсивный поиск в двоичном дереве---------------
// Возвращается указатель на найденную вершину
btree *Search(btree *p, int v) {
 if (p==NULL) return(NULL);                    // Ветка пустая
 if (p->val == v) return(p);                   // Вершина найдена
 if (p->val > v)                               // Сравнение с текущим
  return(Search(p->left,v));                   // Левое поддерево
 else
  return(Search(p->right,v));                  // Правое поддерево
}

//----- Включение значения в двоичное дерево--------------
// функция возвращает указатель на созданную вершину,
// либо на существующее поддерево
btree *Insert(btree *pp, btree *v) {
 if (pp == NULL) {           // Найдена свободная ветка
                             // Создать вершину дерева
  btree *q = new btree;      // и вернуть указатель
  q->val = v->val;
  q->left = q->right = NULL;
  return q;
 }
 if (pp->val == v->val) return pp;
 if (pp->val > v->val)                           // Перейти в левое или
  pp->left=Insert(pp->left,v);                   // правое поддерево
 else
  pp->right=Insert(pp->right,v);
 return pp;
}

// Рекурсивный обход двоичного дерева с выводом
// значений вершин в порядке возрастания
void Scan(btree *p) {
 if (p==NULL) return;
 Scan(p->left);
 cout << p->val << endl;
 Scan(p->right);
}


// Рекурсивный обход двоичного дерева с нумерацией вершин
// снизу-вверх слева-направо, n - текущий номер вершины
int Scan2 (btree * p, int n) {
 if (p==NULL) return n;
 Scan2 (p->left,n);
 n++;
 cout << n << ") " << p->val << endl;
 n=Scan2(p->right,n) ;
 return n;
}


// Рекурсивный обход двоичного дерева с последовательной
// нумерацией вершин в возвратом указателя на вершину с заданным номером
// Глобальный счетчик вершин передается через указатель
btree *ScanNum(btree *p, int *n) {
 btree *q;
 if (p==NULL) return NULL;
 q=ScanNum(p->left,n);
 if (q!=NULL) return q;
 if ((*n)-- ==0) return p;
 return ScanNum(p->right,n);
}

int main (void) {
 int v=1;
 btree *root=NULL;
 int depth=1;
 // ввод узлов 
 while (1) {
  printf ("\n введите узел дерева или 0 для выхода:");
  fflush (stdin);
  scanf ("%d",&v);
  if (!v) break;
  btree node;
  node.val=v;
  root=Insert (root,&node);
 }
 // поиск значения
 printf ("\n введите узел для поиска:");
 fflush (stdin);
 scanf ("%d",&v);
 btree *found=Search (root,v);
 if (found) printf ("\n found %d\n",found->val);
 else printf ("\n not found %d\n",v);
 // нумерация вершин
 printf ("\nScan:\n");
 Scan (root);
 printf ("\n введите начальный номер вершины:");
 fflush (stdin);
 scanf ("%d",&v);
 // поиск по номеру вершины
 printf ("\nScan2:\n");
 Scan2 (root,v);
 printf ("\nScan&Num:\n");
 found=ScanNum (root,&v);
 if (found) printf ("\n found %d\n",found->val);
 else printf ("\n not found %d\n",v);
 fflush (stdin);
 getchar ();
}

 В этом архиве (лаб. 7, весь архив около 5 Мб) - реализации всех основных динамических структур данных на Си: односвязный и двусвязный списки, стек, очередь

гостевая; E-mail