Реализация деревьев

#define _CRT_SECURE_N0_WARNINGS
 
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <conio.h>
 
//-------------------------------------------------------------------------
//структура для описания узла дерева
struct tree
{
    int data;
    struct tree *lchild, *mchild, *rchild;
};
 
 
//функции для вставки узлов в дерево.Данная функция принимает на вход три параметра: 
//указатель на вставляемый узел, значение вставляемого узла и направление вставки — влево, 
//в середину или вправо.
struct tree * my_insert(struct tree *p, int n, int dir) {
    struct tree *temp;
 
    temp = (struct tree *)malloc(sizeof(struct tree));
    temp->data = n;
    temp->lchild = temp->rchild = temp->mchild = NULL;
 
    if (p == NULL)
    {
        return temp;
    }
    else
    {
        if (dir == 0) // влево
        {
            p->lchild = temp;
            return temp;
        }
        else if (dir == 1) // посередине
        {
            p->mchild = temp;
            return temp;
        }
        else // вправо
        {
            p->rchild = temp;
            return temp;
        }
    }
}
 
 
//Симетричний обхід дерева
void inorder(struct tree *p) {
    if (p != NULL)
    {
        inorder(p->lchild);
        printf("%d ", p->data);
        inorder(p->mchild);
        inorder(p->rchild);
    }
}
//-------------------------------------------------------------------------
int main() {
 
 
    struct tree *root;
    struct tree *node_2, *node_3, *node_5;
    struct tree *node_8, *node_9, *node_6, *node_10, *node_4, *node_7;
 
    //создание дерева
    root = NULL;
    root = my_insert(root, 1, 0);
    node_2 = my_insert(root, 2, 0);
    node_3 = my_insert(root, 3, 1);
    node_4 = my_insert(root, 4, 2);
    node_5 = my_insert(node_3, 5, 0);
    node_8 = my_insert(node_5, 8, 0);
    node_9 = my_insert(node_5, 9, 2);
    node_6 = my_insert(node_3, 6, 2);
    node_10 = my_insert(node_6, 10, 1);
    node_7 = my_insert(node_4, 7, 1);
 
 
 
 
    //выполнение обхода дерева
    //printf("\n");
    inorder(root);
    printf("\n");
 
 
    _getch();
    return 0;
}

struct Node
{
    ...
    Node* parent;  // опционально
    Node* nextNeigh;  // указатель на следующего соседа, брата по родителю
};

struct Node
{
   ...
   Node* firstChild, secondChild,...;
};

void parseNode( Node* node ) 
{
   if( node == nullptr )
      return;
   // обработать информационные поля узла
   parseNode( node->firstChild );
   parseNode( node->secondChild );
   ...
}

struct Node
{
   // информационные поля
   Node* nextNeigh;
   Node* firstCHild;
};
 
void parseNodeDepth( Node* node )
{
   if( node == nullptr )
      return;
   // обработка информационных полей узла
   parseNodeDepth( firstChild );
   parseNodeDepth( nextNeigh );
}

void parseNodeWidth( Node* node )
{
   if( node == nullptr )
      return;
   // обработка информационных полей узла
   parseNodeWidth( nextNeigh );
   parseNodeWidth( firstChild );
}

struct Node
{
   // инф поля
   Node* leftChild, * rightChild;
};

Node* root;

struct Node
{
   // инф поля
   Node* firstChild;
   Node* nextNeigh;
};

Node* root;

#include <cstddef>
 
namespace trees
{
    // ====================================================
    // declarations
    // ====================================================
    template <typename T>
    struct Node
    {
        T data;
        Node* firstChild;
        Node* nextNeigh;
    };
 
    /// проход по дереву в ширину с предобработкой данных
    /// @param callback - адрес функции обратного вызова для поля данных каждого узла
    template <typename T>
    void traversePreWidth( Node<T>* node, void (*callback)( const T& ) );
 
    /// создание дерева от узла
    /// @param childNum - каким по счёту дочерним узлом данный приходится родительскому
    /// @param callback - адрес функции обратного вызова, возвращающей количество дочерних узлов
    /// которые следует добавить к данному, и возможно устанавливающей поле данных данного узла
    template <typename T>
    void generate( Node<T>* node, Node<T>* parent, size_t childNum,
                   size_t (*callback)( const Node<T>* parent, T& data, size_t childNum ) );
 
    /// создание дерева вместе с корнем
    /// @param callback - адрес функции обратного вызова, возвращающей количество дочерних узлов
    /// которые следует добавить к данному, и возможно устанавливающей поле данных данного узла
    template <typename T>
    Node<T>* generate( size_t (*callback)( const Node<T>* parent, T& data, size_t childNum ) );
 
    /// уничтожение дерева
    template <typename T>
    void dispose( Node<T>* node );
 
    // ====================================================
    // implementation
    // ====================================================
    template <typename T>
    void traversePreWidth( Node<T>* node, void (*callback)( const T& ) )
    {
        if( node == nullptr )
            return;
 
        callback( node->data );
 
        traversePreWidth( node->nextNeigh, callback );
        traversePreWidth( node->firstChild, callback );
    }
 
    template <typename T>
    Node<T>* generate( size_t (*callback)( const Node<T>* parent, T& data, size_t childNum ) )
    {
        Node<T>* root = new Node<T>;
        root->nextNeigh = nullptr;
        generate<T>( root, nullptr, 0, callback );
        return root;
    }
 
    template <typename T>
    void generate( Node<T>* node, Node<T>* parent, size_t childNum,
                   size_t (*callback)( const Node<T>* parent, T& data, size_t childNum ) )
    {
        if( node == nullptr )
            return;
        size_t n = callback( parent, node->data, childNum );
 
        Node<T>* child;
        if( n > 0 )
        {
            child = node->firstChild = new Node<T>;
            generate( child, node, 0, callback );
 
            for( size_t i = 1; i < n; i++ )
            {
                child = child->nextNeigh = new Node<T>;
                generate( child, node, i, callback );
            }
            child->nextNeigh = nullptr;
        }
        else
            node->firstChild = nullptr;
 
    }
 
    template <typename T>
    void dispose( Node<T>* node )
    {
        if( node->nextNeigh )
            dispose( node->nextNeigh );
        if( node->firstChild )
            dispose( node->firstChild );
        delete node;
    }
}

#include <cstdlib>
#include <ctime>
#include <iostream>
#include "trees.h"
 
void traverseCallback( const float& data );
 
/// @param data - поле данных узла, для которого вызван callback
/// @param childNum - каким по счёту дочерним узлом данный приходится родительскому
/// @return сколько дочерних узлов следует добавить к данному
size_t generateCallback( const trees::Node<float>* parent, float& data, size_t childNum );
 
int main()
{
    srand( time( 0 ) );
 
    trees::Node<float>* root = trees::generate<float>( &generateCallback );
    trees::traversePreWidth( root, &traverseCallback );
    trees::dispose( root );
}
 
void traverseCallback( const float& data )
{
    std::cout << data << " ";
}
 
/// @param data - поле данных узла, для которого вызван callback
/// @param childNum - каким по счёту дочерним узлом данный приходится родительскому
/// @return сколько дочерних узлов следует добавить к данному
size_t generateCallback( const trees::Node<float>* parent, float& data, size_t childNum )
{
    if( parent )
    {
        data = float( rand() ) / RAND_MAX * parent->data;
        return rand() % ( (int)parent->data / 2 + 1 );
    }
    else
    {
        data = float( rand() ) / RAND_MAX * 10;
        return rand() % 10;
    }
}