Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.76/17: Рейтинг темы: голосов - 17, средняя оценка - 4.76
Fynjy8
0 / 0 / 0
Регистрация: 11.05.2014
Сообщений: 9
1

N-дерево

11.05.2014, 02:48. Просмотров 3224. Ответов 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...

8
tegauss
30 / 24 / 27
Регистрация: 06.05.2014
Сообщений: 161
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
_
315 / 149 / 27
Регистрация: 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
_
315 / 149 / 27
Регистрация: 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
_
315 / 149 / 27
Регистрация: 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
_
315 / 149 / 27
Регистрация: 08.10.2011
Сообщений: 432
11.05.2014, 17:08 9
Лучший ответ Сообщение было отмечено Fynjy8 как решение

Решение

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). по мне так очень удобно задавать деревья (после небольшой практики конечно )
обращаю внимание на то, что пустые пары скобок не обязательны, можно добавить а можно и опустить.
1
11.05.2014, 17:08
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.05.2014, 17:08

Дерево, бинарное дерево
Читаю про дерево и не до конца понимаю, а точнее понимаю, но вопрос в том,...

Дерево
Здравствуйте! Есть вот такая задача: Условия: Определить структуру бинарного...

дерево
// derevo_lr2.cpp : Defines the entry point for the console application....


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

Или воспользуйтесь поиском по форуму:
9
Ответ Создать тему
Опции темы

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