Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/7: Рейтинг темы: голосов - 7, средняя оценка - 5.00
VLK
195 / 164 / 19
Регистрация: 05.05.2013
Сообщений: 1,199
1

Дерево, бинарное дерево

23.08.2013, 14:12. Просмотров 1329. Ответов 13
Метки нет (Все метки)

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

Вот есть список, он линейный, все значения идут друг за другом

Дерево, бинарное дерево



А дерево, этот тот же список, только в нем не линейно идут записи, а в зависимости от записи, например, записи меньше нуля налево, больше 0 на право, а потом, если введенное число больше звена дерева то направо, если меньше звена дерева, то налево, т.е.:

Дерево, бинарное дерево


или это что то другое, более сложное и я все опять не правильно понял?

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

0
Миниатюры
Дерево, бинарное дерево  
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.08.2013, 14:12
Ответы с готовыми решениями:

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

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

Бинарное дерево
Нужно записать в дерево и вывести в форматированном виде каталог файлов(типа...

Бинарное дерево
Столкнулся с уникальной проблемой от которой волосы дыбом встают. Вот код,...

Бинарное дерево
Помогите, пожалуйста. Осталась последняя задача в контрольной. Не знаю даже,...

13
VLK
195 / 164 / 19
Регистрация: 05.05.2013
Сообщений: 1,199
23.08.2013, 14:17  [ТС] 2
Блин не успел отредактировать, самая последняя картинка неверная, на ней не верно записаны значения.
0
MickeyBlueEyes
Студент
120 / 131 / 39
Регистрация: 07.04.2011
Сообщений: 503
23.08.2013, 14:20 3
Начало подразумевает корень, корень тоже имеет начальное значение, допустим 20, и затем при добавлении сравнивается если число 10 меньше числа 20, то ложим в лево, а если не, то в право.
0
VLK
195 / 164 / 19
Регистрация: 05.05.2013
Сообщений: 1,199
23.08.2013, 14:24  [ТС] 4
MickeyBlueEyes, то, что выделено жирным : дерево, этот тот же список, только в нем не линейно идут записи, а в зависимости от записи.

это верное утверждение?
0
zer0mail
2454 / 2090 / 217
Регистрация: 03.07.2012
Сообщений: 7,581
Записей в блоге: 1
23.08.2013, 14:27 5
У бинарного дерева 2 указателя: на правое и левое поддерево (по картинкам это не очевидно). Насколько я помню, ключи в левом поддереве меньше, чем в текущем узле, а в правом -ключи больше или равны текущему.
0
VLK
195 / 164 / 19
Регистрация: 05.05.2013
Сообщений: 1,199
23.08.2013, 14:30  [ТС] 6
zer0mail, т.е. в левой стороне могут (должны присутствовать) правые указатели (PtrR) ну и соответственно наоборот?

т.е. есть звено 14, если от него значение меньше, например 10, то у него уже будет левый указатель (PtrL), а если значение больше, допустим 16 то уже правый указатель (PtrR)


Правильно?
0
Dani
1393 / 637 / 134
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
Завершенные тесты: 1
23.08.2013, 14:34 7
Цитата Сообщение от VLK Посмотреть сообщение
А дерево, этот тот же список, только в нем не линейно идут записи,
Это две разные вещи. Если на картинке обе изображены прямоугольниками - это ничего не дает. Реализация, например, разная, т.к. в списке (у не крайнего элемента) один элемент предшествует и один идет после него. А в дереве (не у корня) - один предок и сколько угодно потомков (получается, нужно заводить, например, список потомков).
И в конце концов, дерево - это обычный граф, только без циклов.

На картинках - бинарное дерево, у которого может быть только 2 потомка. Это разновидность, ведь список, например, тоже может быть нелинейным.
0
VLK
195 / 164 / 19
Регистрация: 05.05.2013
Сообщений: 1,199
23.08.2013, 14:41  [ТС] 8
Ладно, пойду еще литературы читать, вечерком продолжу задавать вопросы.
0
zer0mail
2454 / 2090 / 217
Регистрация: 03.07.2012
Сообщений: 7,581
Записей в блоге: 1
23.08.2013, 14:45 9
У каждого узла 2 указателя (один или даже оба могут быть пустыми). Главное, дерево балансируется "в целом", поэтому при добавлении нового значения (и нового узла) приходится его перестраивать. Условия баланса: левые значения меньше текущего, правые не меньше текущего + ограничения на высоту поддеревьев (иначе можно построить "дерево", где только правые указатели заполнены, т.е фактически список).

Можно, конечно, построить дерево без всяких правил на значения и высоты, но тогда какой с него прок? При поиске надо пройти все узлы (как в списке), а вставлять трудней.

Рекомендую погуглить тему "бинарные деревья поиска" и потом спрашивать, что неясно.
0
VLK
195 / 164 / 19
Регистрация: 05.05.2013
Сообщений: 1,199
23.08.2013, 14:50  [ТС] 10
zer0mail, я просто не совсем понимаю: есть звено, и по логике от него могут отходить всего 2 звена - число больше направо, число меньше налево, но вы говорите о третьем и более ответвлении откуда оно берется, я не понимаю или может мой пример изначально не правильный?

или все же то, что я нарисовал это дерево, но тупое и примитивное?
0
Dani
1393 / 637 / 134
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
Завершенные тесты: 1
23.08.2013, 14:58 11
Цитата Сообщение от VLK Посмотреть сообщение
zer0mail, я просто не совсем понимаю: есть звено, и по логике от него могут отходить всего 2 звена - число больше направо, число меньше налево, но вы говорите о третьем и более ответвлении откуда оно берется, я не понимаю или может мой пример изначально не правильный?
Узел - такая структура, где есть поля для: значение, указателя на левого потомка, на правого потомка.
В дереве есть корень - начальный узел, у которого нет предка. Предок для узла X - это такой узел, Y, где X является потомком (в этом дереве - либо левым, либо правым потомком). Нигде 3 связи нету, если только не захочешь хранить указатель на предка.
Дерево, где максимум два узла могут являться потомками для какого-то узла, называется бинарным. Насколько я помню, бинарное дерево поиска - такое дерево, где при добавлении какого-то значения происходит такая проверка: если это значение меньше текущего - добавить в левое поддерево, иначе - в правое.
Остальное - уже вторично, например, если в двоичное дерево поиска добавлять элементы только в порядке возрастания, то дерево будет выглядеть так:
[]
*\
**[]
***\
****[]
***** \
******[]
Для таких случаев придуманы красно-черные деревья и способы балансировки.
1
Atlant_V
8 / 8 / 0
Регистрация: 14.08.2013
Сообщений: 99
23.08.2013, 15:06 12
вот как выглядит бинарное дерево на примере. Если надо могу поискать код, как раз сегодня писал.
p.s. Извиняюсь за свои художественные таланты, кроме paint ничего на кампе нет
1
Миниатюры
Дерево, бинарное дерево  
zer0mail
2454 / 2090 / 217
Регистрация: 03.07.2012
Сообщений: 7,581
Записей в блоге: 1
23.08.2013, 15:20 13
Цитата Сообщение от VLK Посмотреть сообщение
zer0mail...но вы говорите о третьем и более ответвлении откуда оно берется, я не понимаю или может мой пример изначально не правильный?
Про третье ответвление я не говорил. Почитайте для начала: http://www.declic.narod.ru/ossio/files/book/part_7_3.html
1
VLK
195 / 164 / 19
Регистрация: 05.05.2013
Сообщений: 1,199
23.08.2013, 15:28  [ТС] 14
Короче, всем принявшим участи в обсуждении, спасибо, по большому счету это то, что я рисовал, только я не смог толком нарисовать и толком описать.
0
23.08.2013, 15:28
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.08.2013, 15:28

Бинарное дерево
Написать программу для создания, на основе конструктора,дерева из объектов двух...

Бинарное дерево
дано целочисленнное бинарное дерево. найти: а)количество вершин дереваж...

Бинарное дерево
Разработать и реализовать на языке С следующие функции работой с бинарным...


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

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

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