n-tree3.cpp

#include <cstdio>
#include <cctype>
using namespace std;
 
int N; // определяет арность дерева
 
struct Node
{
    int v; // значение в узле дерева
    int n; // кол-во узлов в поддереве с корнем в данном узле
    Node **cld; // массив потомков
    Node() : v( 0 ), n( 1 ), cld( new Node * [ N ] ) { for ( int i = 0; i < N; ++i ) cld[ i ] = 0; }
};
 
Node *root = 0; // корень дерева
Node *msub = 0; // корень поддерева, которое надо найти по заданию
 
int parseTreeR( Node *&r, char *&s ) // парсит дерево из скобочной последовательности; возвращает кол-во узлов в поддереве
{
    int n = 0; // здесь накапливаем узлы поддерева
    int m; // не знаю как объяснить, чтобы не запутать
 
    if ( isdigit( *s ) )
    {
        r = new Node(); // создаем очередной узел дерева
        n = 1; // и запоминаем, что в поддереве с корнем в этом узле есть 1 узел
        do { r->v = r->v * 10 + *s++ - '0'; } while ( isdigit( *s ) ); // парсим значение в узле
        for ( int i = 0; i < N; ++i ) // рекурсивно парсим всех потомков
            if ( *s == '(' && ( m = parseTreeR( r->cld[ i ], ++s ) ) >= 0 && *s == ')' )
                { ++s; n += m; }
        return r->n = n;
    }
    else if ( *s == ')' ) return n; // особый случай: пустой узел ( типа такого: () )
    else return -1; // если криво ввели скобочную последовательность, то надо об этом сообщить "наверх"
}
 
bool parseTree( char *s ) // обертка над парсилкой дерева parseTreeR
{
    int m;
    if ( *s == '(' )
    {
        m = parseTreeR( root, ++s );
        if ( m == -1 ) return false;
        if ( *s == ')' && *++s == 0 ) return true;
        else return false;
    }
    return false;
}
 
void showTreeR( Node *r, int sh ) // распечатка дерева
{
    if ( !r ) return;
    for ( int j = 0; j < sh; ++j ) putchar( ' ' );
    printf( "%d\n", r->v );
    for ( int i = 0; i < N; ++i )
        showTreeR( r->cld[ i ], sh + 5 );
}
 
void showTree() // обертка над печаталкой дерева
{
    printf( "\nTree:\n\n" );
    showTreeR( root, 0 );
    printf( "\n" );
}
 
bool findMaxSubR( Node *r, int *a, int n ) // ф-ция поиска максимального поддерева с заданными свойствами
{
    if ( !r ) return true;
    
    bool flag = true;
 
    for ( int i = 0; i < N; ++i )
        flag &= findMaxSubR( r->cld[ i ], a, n );
    for ( int j = 0; j < n; ++j )
        if ( a[ j ] == r->v )
            flag = false;
    if ( flag )
        if ( !msub || msub->n < r->n )
            msub = r;
    return flag;
}
 
void findMaxSub( int *a, int n ) // обертка над findMaxSubR + распечатка результатов
{
    findMaxSubR( root, a, n );
    printf( "\nMaxSubTree:\n" );
    showTreeR( msub, 0 );
    printf( "\n" );
}
 
int main()
{
    N = 3; // задаем арность дерева
//  char s[] = "(1)";
//  char s[] = "(1(2)(3)(4)))";
    char s[] = "(1(2(5(6)))(3(7(8)(2)))(4))"; // дерево в виде скобочной последовательности
 
    int a[] = { 1, 9, 4 }; // это "заданные вершины"
 
    if ( parseTree( s ) ) // если дерево удачно спарсилось из скобочной последовательности
    {
        showTree();
        findMaxSub( a, sizeof( a ) );
    }
    else
        printf( "Bad tree\n\n" );
 
    return 0;
}

/*  :):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):)
задание дерева с помощью скобочной последовательности (N = 3):
() - пустое дерево
(5) - дерево с одним узлом со значением 5
(5()()()) - то же что и выше, но в более развернутой форме (указано, что есть 3 пустых потомка)
(5(7)) - дерево с корнем 5 и одним потомком со значением 7
(5()(7)()) - то же что и выше
(5(7)(4)) - дерево с корнем 5 и 2-мя его потомками 7 и 4
(5(7)()(4)) - то же что и выше
(5(7(4))) - дерево с корнем 5, его сыном 7 и внуком 4
(5(7(4)())) - то же что и выше
(5()(7(4))) - то же что и выше
(5()(7(4))()) - то же что и выше
думаю примерно понятно как задается дерево с помощью скобочной последовательности: дерево должно быть окружено парой скобок, внутри скобок вначале задается значение корня, а затем перечисляются все поддеревья этого дерева (естественно каждое в отдельных скобках) (их должно быть не больше N). по мне так очень удобно задавать деревья (после небольшой практики конечно  )
обращаю внимание на то, что пустые пары скобок не обязательны, можно добавить а можно и опустить.
:):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):)
*/