49 / 49 / 14
Регистрация: 08.04.2011
Сообщений: 124
|
||||||
1 | ||||||
Дерево04.05.2011, 17:36. Показов 8498. Ответов 22
Метки нет (Все метки)
Условие:
Программа построения дерева, где узел(корень) - ФИО препода, а инф. поля (наверное левая\правая ветки) имеют записи: 1)должность(string[10]), 2)предметы что преподает. Написать процедуру печати построеного бинарного дерева(полная инфа про препода) Кто нибудь знает как выполнить это задание, т.е. как в корень записать симв. строку, какие if 'ы и while'ы использовать, в какую часть дерева записывать записи? В наличии имеються функции добавления первого введенного элемента в корень и ввода остальных узлов и вывода дерева print_tree ну и структура с *left, *right и некоторым d что похоже есть num Добавлено через 55 секунд По структуре надо
0
|
04.05.2011, 17:36 | |
Ответы с готовыми решениями:
22
Бинарное дерево. Удалить из дерева часть вершин так, чтобы оставшееся дерево стало пирамидой Дано дерево. Распечатать дерево по уровням Исходное бинарное дерево превратить в бинарное дерево поиска, при этом сохранив его структуру Напишите программу, которая бы читала дерево в формате (а) и затем печатала бы это дерево в формате (б). |
49 / 49 / 14
Регистрация: 08.04.2011
Сообщений: 124
|
|
04.05.2011, 17:59 [ТС] | 3 |
Ну я понял так:
корень:ФИО в левую ветку идет: должность в правую: предметы(дисциплины), причем их несколько , должность одна ФИО наверное разные Добавлено через 59 секунд должность одна ФИО несколько предметы несколько
0
|
49 / 49 / 14
Регистрация: 08.04.2011
Сообщений: 124
|
|
04.05.2011, 18:10 [ТС] | 5 |
ХИХИ!
Дословное условие: Розробити програму побудови двійкового дерева, вузол якого містить в якості ключа прізвище та ім'я по батькові викладача, а в якості інформаційного поля запис: посада(string[10]); дисципліни, які викладає(масив з рядкових змінних); Написати процедуру друку побудованого двійкового дерева (повна інформація про викладача) Russian version: Разработать программу построения двоичного дерева, узел которого содержит в качестве ключа фамилию и имя отчество преподавателя, а в качестве информационного поля запись: должность(string[10]); дисциплины, которые выкладывает(массив из строчных переменных); Написать процедуру печати построенного двоичного дерева (полная информация о преподавателе) Может и вправду бред?
0
|
187 / 174 / 18
Регистрация: 22.03.2010
Сообщений: 612
|
|||||||||||
04.05.2011, 18:48 | 7 | ||||||||||
писал когда то давно, может пригодится
только в привате вектор лежит. Некоторым этом может не понравится, можно легко переделать чтобы была только ссылка на корень и выпилить оператор[], вот тогда будет полноценное дерево
1
|
49 / 49 / 14
Регистрация: 08.04.2011
Сообщений: 124
|
|
04.05.2011, 19:49 [ТС] | 8 |
fasked, Это и есть ответ?(от pito211) или есть по примеру моей структуры?
0
|
05.05.2011, 00:50 | 9 | ||||||||||||||||||||
kjahert, конкретно по примеру Вашей структуры нет, но есть более-менее похожий вариант. Получайте
teacher.h
В коде программы много отладочной информации, в первую очередь для контроля памяти - чтобы утечек не было. Перед каждым вызов malloc/calloc и перед каждым вызовом free. По номерам указателей можно видеть, что утечек нет. Конечно отладочную информацию можно убрать. В таком примере программа работает следующим образом: Код
// старт программы 00542E70 TREE created // ввод информации с клавиатуры INPUT info for 0028FEF2 NAME: IVANOV POST: DIRECTOR DISC: 01 DISC: 02 DISC: 03 00540E78 NODE created INPUT info for 0028FEF2 NAME: SIDOROV POST: TEACHER DISC: 02 DISC: 03 DISC: 05 00540ED0 NODE created INPUT info for 0028FEF2 NAME: PETROV POST: TEACHER DISC: 01 DISC: 06 DISC: 07 00540F28 NODE created // вывод информации начинается с этого момента name: PETROV post: TEACHER disciplines: : 01 : 06 : 07 name: SIDOROV post: TEACHER disciplines: : 02 : 03 : 05 name: IVANOV post: DIRECTOR disciplines: : 01 : 02 : 03 00540E78 NODE deleted 00540ED0 NODE deleted 00540F28 NODE deleted 00542E70 TREE deleted Возникнут вопросы - задавайте их здесь. Удачи
2
|
187 / 174 / 18
Регистрация: 22.03.2010
Сообщений: 612
|
|
05.05.2011, 06:24 | 10 |
1
|
4226 / 1795 / 211
Регистрация: 24.11.2009
Сообщений: 27,562
|
|
05.05.2011, 06:34 | 11 |
Во-первых корень троже узел, но не каждый узел - корень. Во-вторых элменты дерева должны быть однотипными. В-третьих любая ветвь - это только совокупность узлов. В-четвёртых деревол не может иметь полей.
1
|
49 / 49 / 14
Регистрация: 08.04.2011
Сообщений: 124
|
|
05.05.2011, 10:21 [ТС] | 12 |
Спасибо всем и fasked'у особенно
Добавлено через 16 минут fasked, Буду разбираться потому как преподу надо только с одной структурой node* как у меня Теоретически возможно переделать (я не прошу вас этого делать) под мой пример структур и функций, в одной программе, без использования других структур, teacher.h tree.h... ??
0
|
05.05.2011, 13:33 | 13 |
Без структуры teacher обойтись, увы, не получится.
А tree - это всего лишь обертка для node. Так что конечно, можно выкинуть. В таком случае заменяйте в сигнатурах функций указатель binary_tree *, на binary_tree_node *, ну и соответственно в теле каждой из функции tree->root изменяйте на доступ без структур, то есть просто root. Контролировать в main тогда следует не структуру binary_tree, а binary_tree_node соответственно, которая будет указателем на корень дерева. Добавлено через 35 минут На самом деле это сложно назвать бинарным деревом, еще похоже, что память течет, да и вообще ТС на Си пишет.
1
|
187 / 174 / 18
Регистрация: 22.03.2010
Сообщений: 612
|
|
20.05.2011, 10:13 | 14 |
бинарное дерево является подмножеством понятия дерево.
поэтому имея данный класс не составит труда сделать с помощью него бин дерево, или замутить производный класс BinTree например. А вот из бинарного дерева сделать дерево не получится а насчёт утечек я и неспорю, там нигде нет деструкторов. Но класс писался по принципу "быстрее и чтоб работало", а кому надо тот и добавит три строки в treeitem.h и три строки в tree.h если кто собирается строить на нём грандизные проекты, а в учебных целях преподу показать думаю прокатит и так Добавлено через 14 минут
0
|
4226 / 1795 / 211
Регистрация: 24.11.2009
Сообщений: 27,562
|
|
20.05.2011, 10:25 | 15 |
Корень может быть только один, иначе это нифига не дерево, дпаже не коряга. Если ФИО - корень и ФИО могут быть разные, то у тебя разве что лес получится.
Добавлено через 4 минуты А теперь сраывни с этим бредом: Тебе в каждом узле задано хранить должность и предметы, то есть построить дерево структур, а не одну структуру представить деревом. Добавлено через 3 минуты Бинарное или двоичное дерево отличается тем, что каждый его узел имеет жёсткое ограничеение на количество своих потомков, а эти потомки называются левым и правым, чего нет в дереве общего вида. Поэтому двоичное дерево проще сделать с ноля, чем переделывать в него корягу общего вида.
0
|
187 / 174 / 18
Регистрация: 22.03.2010
Сообщений: 612
|
|
20.05.2011, 10:49 | 16 |
от общего к частному легко перейти. В данном случае children[0] можно считать как левый, а children[1] как правый потомок и контролировать это в теле программы. Но учитывая наличие готового к работе класса Tree, тут просто грех не воспользоваться наследованием
0
|
4226 / 1795 / 211
Регистрация: 24.11.2009
Сообщений: 27,562
|
|
20.05.2011, 10:56 | 17 |
В данном случае частное проще, чем переход к частному.
0
|
20.05.2011, 11:53 | 18 |
Помимо того, что в бинарном дереве строгое количество потомков, есть еще и определенные алгоритмы вставки/удаления/поиска элементов. И что именно здесь наследовать? Название разве что...
0
|
187 / 174 / 18
Регистрация: 22.03.2010
Сообщений: 612
|
||||||
20.05.2011, 13:12 | 19 | |||||
да собственно почти все функции дерева пригодятся и в бинарном дереве.
остальные все тоже не лишнии, за исключением add. Заместо неё addLeft и addRight можно написать. всяко проще дописать десять строк, чем писать с нуля класс к тому же узкопрофильный. ******* алгоритмов поиска для бинарного дерева много - прямой обратный внутренний нафиг их в классе писать все, если пользователю будет нужен один из них. Пусть сам и напишет в теле программы какой ему надо.
0
|
20.05.2011, 14:12 | 20 |
Начнем с того, что в Вашем классе методов всего пять! Сейчас я объясню, почему же не подойдут оставшиеся четыре. Это не так уж и много. А заодно разберемся чем же так плох Ваш класс, Вы уж простите меня, но написан он через одно место, и Вы, кстати, сами в этом признались.
Метод 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 минут После этой Вашей фразы можно заканчивать разговор Читайте книги, алгоритм поиска в бинарном дереве один! Реализовать его правда можно рекурсивно или не рекурсивно. Вот и вся разница... мдэ... а я то распинался...
0
|
20.05.2011, 14:12 | |
20.05.2011, 14:12 | |
Помогаю со студенческими работами здесь
20
Дерево дерево, странное дерево Дерево, бинарное дерево Дерево... Дерево Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |