Реализация деревьев - C++ - Ответ 10426069

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