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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 21, средняя оценка - 4.81
kjahert
49 / 49 / 5
Регистрация: 08.04.2011
Сообщений: 124
#1

Дерево - C++

04.05.2011, 17:36. Просмотров 3118. Ответов 22
Метки нет (Все метки)

Условие:
Программа построения дерева, где узел(корень) - ФИО препода, а инф. поля (наверное левая\правая ветки) имеют записи: 1)должность(string[10]), 2)предметы что преподает. Написать процедуру печати построеного бинарного дерева(полная инфа про препода)

Кто нибудь знает как выполнить это задание, т.е. как в корень записать симв. строку, какие if 'ы и while'ы использовать, в какую часть дерева записывать записи?

В наличии имеються функции добавления первого введенного элемента в корень и ввода остальных узлов и вывода дерева print_tree ну и структура с *left, *right и
некоторым d что похоже есть num

Добавлено через 55 секунд
По структуре надо
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
#include <iostream.h>
 
struct node
{
 int d;
 node *left;
 node *right;
};
node * first(int d);
node * search_insert(node *root, int d);
void print_tree(node *root, int l);
 
void main()
{
    int n, i, what;
    cout<<"input n \n";
    cin>>n;
    cout<<"input first what \n";
    cin>>what;
    node *root = first(what);
    for (i = 1; i<n; i++)
    {
    cout<<"input what \n";
    cin>>what;
    search_insert(root, what);
    }
    print_tree(root, 0);
 
}
 
node * first(int d)
{
    node *pv = new node;
    pv->d    = d;
    pv->left = 0;
    pv->right = 0;
    return pv;
}
 
node * search_insert(node *root, int d)
{
    node *pv = root, *prev;
    int found = 0;
    while (pv && !found){
       prev = pv;
       if   (d == pv->d) found = 1;
       else if  (d <  pv->d)pv     = pv->left;
       else         pv     = pv->right;
    }
    if (found) return pv;
    node *pnew  = new node;
    pnew->d     = d;
    pnew->left  = 0;
    pnew->right = 0;
    if (d < prev->d)
       prev->left  = pnew;
    else
       prev->right = pnew;
    return pnew;
}
 
void print_tree(node *p, int level)
{
    if (p)
    {
    print_tree(p->left, level+1);
    for (int i = 0; i<level; i++)
    cout << "    ";
    cout <<  p->d << endl;
    print_tree(p->right, level + 1);
    }
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.05.2011, 17:36
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Дерево (C++):

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

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

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

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

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

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

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
pito211
186 / 173 / 8
Регистрация: 22.03.2010
Сообщений: 612
20.05.2011, 10:49 #16
Цитата Сообщение от taras atavin Посмотреть сообщение
Бинарное или двоичное дерево отличается тем, что каждый его узел имеет жёсткое ограничеение на количество своих потомков, а эти потомки называются левым и правым, чего нет в дереве общего вида. Поэтому двоичное дерево проще сделать с ноля, чем переделывать в него корягу общего вида.
от общего к частному легко перейти. В данном случае children[0] можно считать как левый, а children[1] как правый потомок и контролировать это в теле программы. Но учитывая наличие готового к работе класса Tree, тут просто грех не воспользоваться наследованием
taras atavin
Ушёл с форума.
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
20.05.2011, 10:56 #17
В данном случае частное проще, чем переход к частному.
fasked
Эксперт С++
4935 / 2515 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
20.05.2011, 11:53 #18
Цитата Сообщение от pito211 Посмотреть сообщение
т общего к частному легко перейти. В данном случае children[0] можно считать как левый, а children[1] как правый потомок и контролировать это в теле программы. Но учитывая наличие готового к работе класса Tree, тут просто грех не воспользоваться наследованием
Помимо того, что в бинарном дереве строгое количество потомков, есть еще и определенные алгоритмы вставки/удаления/поиска элементов. И что именно здесь наследовать? Название разве что...
pito211
186 / 173 / 8
Регистрация: 22.03.2010
Сообщений: 612
20.05.2011, 13:12 #19
да собственно почти все функции дерева пригодятся и в бинарном дереве.

C++
1
2
TreeItem<TYPE>* operator[](const Index &index); 
        /*Возвращает ссылку на i-ого сына, i = index*/
вместо него сделать две функции right и left, типа TreeItem<TYPE>* right {return this->operator[](0)}, TreeItem<TYPE>* left {return this->operator[](1)} то есть всё равно оператор индексирования пригодился
остальные все тоже не лишнии, за исключением add. Заместо неё addLeft и addRight можно написать. всяко проще дописать десять строк, чем писать с нуля класс к тому же узкопрофильный.

*******
алгоритмов поиска для бинарного дерева много - прямой обратный внутренний нафиг их в классе писать все, если пользователю будет нужен один из них. Пусть сам и напишет в теле программы какой ему надо.
fasked
Эксперт С++
4935 / 2515 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
20.05.2011, 14:12 #20
Цитата Сообщение от pito211 Посмотреть сообщение
да собственно почти все функции дерева пригодятся и в бинарном дереве.
Начнем с того, что в Вашем классе методов всего пять! Сейчас я объясню, почему же не подойдут оставшиеся четыре. Это не так уж и много. А заодно разберемся чем же так плох Ваш класс, Вы уж простите меня, но написан он через одно место, и Вы, кстати, сами в этом признались.

Метод add не подходит по, я надеюсь, всем понятным причинам. В бинарном дереве совершенно отличный, то есть другой, алгоритм вставки. Это объяснять, я думаю, не стоит.
Что принимает в качестве аргумента метод add? Я не верю своим глазам, но это индекс. Да-да, индекс. В комментарии написано, что метод должен добавить "сына" к "предку" с указанным индексом. Возникает вопрос: какого именно сына? Видимо никакого. Можно сказать, что этот метод резервирует место для последующей операции добавления или вставки, но никак не делает то, что следует из названия.

Идем дальше...
Метод size. Тут все просто, метод должен возвратить текущее количество элементов в дереве. Во всем дереве. Интересно, работает ли. Я не проверял, конечно, но закрадываются сомнения. Особенно с учетом того, что в самом TreeItem также лежит вектор. Я верю, что тут может быть хитрая схема индексации, но не доверяю.

Метод empty. Признаюсь, я был поражен. Кроме того, что Ваше дерево никогда не будет пустым, следовательно этот метод бесполезен, его реализация это тоже нечто. Да, работать будет. Но Вы в курсе зачем вообще существуют методы по имени empty? Совсем не только ради удобства, можно было бы всегда писать xxx.size() == 0, но нет, дело в другом. В структурах данных, основанных на списках (коим является и дерево) метод empty отрабатывает за O(1) операций, это элементарная операция. Метод size отрабатывает, как минимум, за линейное время O(n). Дело именно в скорости. У метода empty - фиксированное время работы, у метода size - нет.

Метод clear. Тоже странноватый. Судя по комментарию, опять же, должен удалить все кроме корня. М-м-м... И я опять в замешательстве. Реализация вроде как соответствует описанию. Правда есть утечка памяти.

Еще два интересных момента: конструктор и деструктор. В конструкторе создается (зачем?) корень. Я уже говорил, что дерево никогда не будет пустым, потому как корень у него создан изначально. В деструкторе вызывается метод clear - корень не удаляется. Опять потекла...

Operator[]... Имеет право на жизнь в бинарном дереве, но не в таком виде. Все дело в том, что к элементу дерева (даже иерархического, а тем более бинарного) нельзя обращаться по индексу. Ну вот нарисуйте дерево на бумажке... И какой индекс будет у каждого элемента? В бинарном дереве ясное дело к элементу обращаются по ключу. В n-арном дереве, наверное тоже по ключу, по ключу предка. Это же иерархия, верно? Значит элементы дерева должны быть упорядочены по определенному признаку.

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

В класс TreeItem лезть уже не будем. Там еще можно какими-то костылями привернуть его к бинарному дереве. Но и так уже понятно, что Ваш класс дерева не имеет права на жизнь., его надо переписывать.
Можно было бы поспорить с Вами, если бы он был написан хорошо, ну или хотя бы просто правильно. Если бы все его методы работали ожидаемо, не было бы утечек памяти и т.д.

Да и вообще использовать вектор в качестве структуры для хранения решение не однозначное.
Вы знаете почему списки пишут на основе узлов, то есть это так называемые node-based структуры. Почему их не пишут на основе массивов и векторов? Малейшее изменение может привести к "катастрофе", например, вставка в середину - не очень благодарное занятие для векторов. Это же надо сдвинуть очень много элементов в право, а в node-based структуре это просто переопределение адресной части двух элементов.

А так, проще написать новый класс с нуля, чем использовать Ваш.

Добавлено через 12 минут
Цитата Сообщение от pito211 Посмотреть сообщение
алгоритмов поиска для бинарного дерева много - прямой обратный внутренний нафиг их в классе писать все, если пользователю будет нужен один из них. Пусть сам и напишет в теле программы какой ему надо.
После этой Вашей фразы можно заканчивать разговор
Читайте книги, алгоритм поиска в бинарном дереве один! Реализовать его правда можно рекурсивно или не рекурсивно. Вот и вся разница... мдэ... а я то распинался...
pito211
186 / 173 / 8
Регистрация: 22.03.2010
Сообщений: 612
20.05.2011, 14:25 #21
Цитата Сообщение от fasked Посмотреть сообщение
Метод size. Тут все просто, метод должен возвратить текущее количество элементов в дереве. Во всем дереве. Интересно, работает ли. Я не проверял, конечно, но закрадываются сомнения. Особенно с учетом того, что в самом TreeItem также лежит вектор. Я верю, что тут может быть хитрая схема индексации, но не доверяю.
не работал бы, если Tree состоял бы из TreeItem, но так как он у меня он состоит из TreeItem* то никаких проблем с этим нет. Да и проверить это легко

насчёт add - класс изначально писался таким образом, что не содержал в себе ничего. А в связи с тем что человеку нужно было засовывать структуры вот я и прикрутил шаблон. В комментариях к setValue я написал, что её нету, кому надо тот и допишет. Поэтому нет ничего удивительного в том, что add добавляет по индексу пустой элемент.
fasked
Эксперт С++
4935 / 2515 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
20.05.2011, 14:32 #22
Цитата Сообщение от pito211 Посмотреть сообщение
кому надо тот и допишет
Если по Вашему это так просто, реализовать бинарное дерево, наследуя его n-арного, то покажите как это. Может быть тогда у Вас и получится что-то доказать, пока что это только пустые слова.
pito211
186 / 173 / 8
Регистрация: 22.03.2010
Сообщений: 612
20.05.2011, 14:37 #23
Цитата Сообщение от fasked Посмотреть сообщение
Метод size. Тут все просто, метод должен возвратить текущее количество элементов в дереве. Во всем дереве. Интересно, работает ли. Я не проверял, конечно, но закрадываются сомнения. Особенно с учетом того, что в самом TreeItem также лежит вектор. Я верю, что тут может быть хитрая схема индексации, но не доверяю.
не работал бы, если Tree состоял бы из TreeItem, но так как он у меня он состоит из TreeItem* то никаких проблем с этим нет. Да и проверить это легко

насчёт add - класс изначально писался таким образом, что не содержал в себе ничего. А в связи с тем что человеку нужно было засовывать структуры вот я и прикрутил шаблон. В комментариях к setValue я написал, что её нету, кому надо тот и допишет. Поэтому нет ничего удивительного в том, что add добавляет по индексу пустой элемент.

Добавлено через 32 секунды
и в моей библиотеке лежит такая версия size()

C++
1
2
3
4
size_type size() const
        {   // return length of sequence
        return (_Mysize);
        }
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.05.2011, 14:37
Привет! Вот еще темы с ответами:

Дерево - 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;...

N-дерево - C++
Дано N-дерево. Найти поддерево не включающее ни одну из заданных вершин. Вообще хотя бы &quot;Дано N-дерево&quot; - если вы кинете готовый код...


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

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

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