Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 13, средняя оценка - 4.69
Fynjy8
0 / 0 / 0
Регистрация: 11.05.2014
Сообщений: 9
#1

N-дерево - C++

11.05.2014, 02:48. Просмотров 2281. Ответов 8
Метки нет (Все метки)

Дано N-дерево. Найти поддерево не включающее ни одну из заданных вершин.

Вообще хотя бы "Дано N-дерево" - если вы кинете готовый код этой части, то поможете уже половине нашей группы
Серьезно, везде информация по бинарным деревьям, информации по N-деревьям нету почти никакой.

Как я понял N-дерево - это N-арное, оно же k-d дерево? Я правильно понимаю?

В общем, за любую конкретную информацию с примерами кода или готовыми исходниками - буду благодарен.
Заранее спасибо

Если про N-арное, оно же k-d дерево я правильно понял, то вот что нашел на вики:
(Оно не работает)
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
#include <stdlib.h>
#include <conio.h>
using namespace std;
 
 
const int N=10; // количество пространств ключей
 
struct Item { // структура элемента
  int key[N];  // массив ключей определяющих элемент
  char *info;  // информация элемента
};
 
struct Node { // структура узла дерева
  Item i;  // элемент
  Node *left; // левое поддерево
  Node *right; // правое поддерево
};
 
int main() { 
for (int i = 0; tree; i++) // i - это номер пространства
    if (tree->x[i] < tree->t)  // t - медиана
        tree = tree->left;     // переходим в левое поддерево
    else
        tree = tree->right;    // переходим в правое поддерево
 
return 0;
}
0
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.05.2014, 02:48
Здравствуйте! Я подобрал для вас темы с ответами на вопрос N-дерево (C++):

Бинарное дерево. Удалить из дерева часть вершин так, чтобы оставшееся дерево стало пирамидой - C++
Дано бинарное дерево. Удалить из дерева часть вершин так, чтобы оставшееся дерево стало пирамидой.

Дано дерево. Распечатать дерево по уровням - C++
Дано дерево. Распечатать дерево по уровням.

Исходное бинарное дерево превратить в бинарное дерево поиска, при этом сохранив его структуру - C++
Помогите, не могу понять!( Нужно исходное бинарное дерево превратить в бинарное дерево поиска, при этом сохранив его структуру. вот...

Напишите программу, которая бы читала дерево в формате (а) и затем печатала бы это дерево в формате (б). - C++
Представление дерева: а) Д (Б (А, Ф (В,)), Е (,З (Ж, И))) б) Д Б А Ф ...

Дерево дерево, странное дерево - C++
Нужна помощь в построении дерева. Задание таково: Вершина дерева содержит N целых значений и два указателя на потомков. Запись значений...

Дерево, бинарное дерево - C++
Читаю про дерево и не до конца понимаю, а точнее понимаю, но вопрос в том, правильно ли я понимаю, надеюсь вы мне подскажите. Вот есть...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
tegauss
30 / 24 / 24
Регистрация: 06.05.2014
Сообщений: 158
11.05.2014, 03:06 #2
Fynjy8, мне кажется, N-дерево, это дерево, у каждого узла которого есть N сыновей. Типа у узла бинарного дерева - два сына, а у узла N-дерева - N сыновей.

Тот код, что вы привели, скорее описывает именно бинарное дерево, т.к. я вижу там "левое" и "правое" поддеревья.

Думаю, так должен выглядеть узел:

C++
1
2
3
4
struct Node { // структура узла дерева
  int key; // идентификатор вершины
  Node *nodes[N]; // массив указателей на N сыновей узла
};
Если хотите, могу написать рекурсивную ф-ю обхода.. Ну там в принципе все понятно.
0
ya_noob
_
201 / 145 / 9
Регистрация: 08.10.2011
Сообщений: 432
11.05.2014, 10:46 #3
Цитата Сообщение от Fynjy8 Посмотреть сообщение
Как я понял N-дерево - это N-арное, оно же k-d дерево? Я правильно понимаю?
хитрый вопрос
1) N-арное дерево и k-d дерево совсем разные вещи.
2) является ли N-дерево N-арным деревом лучше уточнить у препода (мое мнение: да является, т.к. никогда не встречал такого понятия как N-дерево, хотя знаю, что есть B-деревья, R-деревья и т.д.)
0
Fynjy8
0 / 0 / 0
Регистрация: 11.05.2014
Сообщений: 9
11.05.2014, 12:13  [ТС] #4
tegauss, Было бы отлично

ya_noob, N-арное все-таки думаю, да. (думал, что k-d это оно же, но нет. Говорим об N-арном)

Добавлено через 5 минут
Что накопал:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <conio.h>
struct tree {
int k,n;
tree **son;
};
tree *root=NULL; 
tree *node;
void add(tree *);
void main()
{
node=new tree;
root=node;
printf("Enter the key of the root\n");
scanf("%d",&node->k);
add(node);
getch();
}
void add(tree *c)
{
int i;
printf("Enter the number of sons\n");
scanf("%d",&c->n);
if (c->n==0) 
{
c->son=NULL;
return;
}
c->son=new tree*[c->n];
for (i=0;i<c->n;i++)
{
c->son[i]=new tree;
printf("Enter the key of the node %d\n",i);
scanf("%d",&c->son[i]->k);
printf("\n%d",c->son[i]->k);
}
for (i=0;i<c->n;i++)
add(c->son[i]);
}
И еще:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include "stdafx.h"
#include "iostream"
#include "conio.h"
using namespace std;
 
struct CNode
{
   int number; // number of node
   int data; // some node data
   unsigned int nChildCount; // amount of chidren
   CNode* pChildren; // pointer to array of child nodes
};
 
int nn = 0;
int count = 0;
 
void Zapolnenie(CNode* pNode)
{
   pNode->number = nn++;
   cout << "Vi v vershine " << pNode->number << "\nDannie uzla ";
   cin >> pNode->data;
 
   cout << "Skoka detey? ";
   unsigned int l; cin >> l;
   if (l > 0)
   {
      pNode->nChildCount = l;
      pNode->pChildren = new CNode[l];
      for (int qq = 0; qq < l; ++qq)
      {
         Zapolnenie(&pNode->pChildren[qq]);
      }
  
   }
   else
   {
      pNode->nChildCount = 0;
      pNode->pChildren = NULL;
      ++count;
   }
}
 
void Udalenie(CNode* pNode)
{
   if (pNode->nChildCount > 0)
   {
      for (int qq = 0; qq < pNode->nChildCount; ++qq)
      {
         Udalenie(&pNode->pChildren[qq]);
      }
      delete [] pNode->pChildren;
   }
}
 
int main()
{
   CNode node;
   Zapolnenie(&node);
 
   cout << "Kolichestvo list'ev: " << count;
   getch();
 
   Udalenie(&node);
 
   return 0;
}
Ни одно из них не скомпилировалось. Наверно из-за Visual Studio, ошибка везьде #include "stdafx.h"
P.S. Как видите, я полный "начинающий", поэтому не ругайте
0
ya_noob
_
201 / 145 / 9
Регистрация: 08.10.2011
Сообщений: 432
11.05.2014, 12:47 #5
Цитата Сообщение от Fynjy8 Посмотреть сообщение
ошибка везьде #include "stdafx.h"
ну и удали первую строку, всё должно заработать.
у меня они откомпилировались без ошибок, только main должен возвращать int, а не void в первой программе
0
Fynjy8
0 / 0 / 0
Регистрация: 11.05.2014
Сообщений: 9
11.05.2014, 14:11  [ТС] #6
ya_noob, пробовал естественно В первой ошибки scanf и getch, во второй count неоднозначный символ

Люблю Visual Studio

Добавлено через 1 час 10 минут
UPD: №2 все-таки запустил, пусть и с кучей предупреждений

По второй и основной части (Найти поддерево не включающее ни одну из заданных вершин) Нашел только это:

Берешь корень, его детей, относительно каждого из детей смотришь сколько у каждого из детей ненужных вершин. Если у какого-то ребенка этих вершин меньше, чем у этого ребенка его детей(ну то есть по отношению к первой вершине-внуков)-значит, будет такой внук у которого в след поколениях не будет ненужных вершин. Если такого ребенка нет-идешь по внукам и то же самое. Операций-не больше n^3(n-колво вершин)
0
ya_noob
_
201 / 145 / 9
Регистрация: 08.10.2011
Сообщений: 432
11.05.2014, 14:25 #7
Цитата Сообщение от Fynjy8 Посмотреть сообщение
пробовал естественно В первой ошибки scanf и getch, во второй count неоднозначный символ
Люблю Visual Studio
ну хз. я через голый компилятор gcc 1-ую прогу откомпилировал без предупреждений вообще, а 2-ую с 2-мя предами по поводу сравнений знаковых и беззнаковых типов.

Цитата Сообщение от Fynjy8 Посмотреть сообщение
Берешь корень, его детей, относительно каждого из детей смотришь сколько у каждого из детей ненужных вершин. Если у какого-то ребенка этих вершин меньше, чем у этого ребенка его детей(ну то есть по отношению к первой вершине-внуков)-значит, будет такой внук у которого в след поколениях не будет ненужных вершин. Если такого ребенка нет-идешь по внукам и то же самое. Операций-не больше n^3(n-колво вершин)
долго пытался понять смысл сего текста. тщетно.

как я понял, вам надо кроме дерева ввести в программу еще какие-то дополнительные данные ("заданные вершины"). так? просто меня сбило с толку это последнее высказывание по поводу детей, внуков и n^3.
0
Fynjy8
0 / 0 / 0
Регистрация: 11.05.2014
Сообщений: 9
11.05.2014, 14:44  [ТС] #8
Цитата Сообщение от ya_noob Посмотреть сообщение
долго пытался понять смысл сего текста. тщетно.
Вот и я также)
Это подсказка с форума на аналогичную задачу. Но звучит как цитата Кличко

Как я понял (может и не верно): мы вводим числа ("заданные вершины") и ищем такую ветку в которую ни одно из этих чисел не входит. (Какая-то идиотская задача получается, на мой взгляд)

Если всё так, то нужен обход дерева сверху вниз и сравнение каждой вершины с набором чисел.
0
ya_noob
_
201 / 145 / 9
Регистрация: 08.10.2011
Сообщений: 432
11.05.2014, 17:08 #9
Лучший ответ Сообщение было отмечено автором темы, экспертом или модератором как ответ
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#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). по мне так очень удобно задавать деревья (после небольшой практики конечно )
обращаю внимание на то, что пустые пары скобок не обязательны, можно добавить а можно и опустить.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.05.2014, 17:08
Привет! Вот еще темы с ответами:

Дерево - C++
Нужно НЕ рекурсивно распечатать двоичное дерево по слоям, собственно как это сделать?

дерево - C++
Сделал дерево, если его ветви создаются на стадии компиляции, то все работает нормально, но если их создает пользователь, то все ветви...

дерево - C++
// derevo_lr2.cpp : Defines the entry point for the console application. #include &quot;stdafx.h&quot; #include &quot;iostream&quot; using namespace std;...

Дерево... - C++
в общем есть дерево двоичного поиска, состоит из функций добавления, удаления, поиска, вывода, ф-ция, которая выводит размер дерева... К...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
11.05.2014, 17:08
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru