Instantly share code, notes, and snippets.

Embed
What would you like to do?
#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). по мне так очень удобно задавать деревья (после небольшой практики конечно )
обращаю внимание на то, что пустые пары скобок не обязательны, можно добавить а можно и опустить.
:):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):):)
*/
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment