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

Дерево, бинарное дерево - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 5.00
VLK
 Аватар для VLK
192 / 161 / 12
Регистрация: 05.05.2013
Сообщений: 1,221
23.08.2013, 14:12     Дерево, бинарное дерево #1
Читаю про дерево и не до конца понимаю, а точнее понимаю, но вопрос в том, правильно ли я понимаю, надеюсь вы мне подскажите.

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

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


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

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

или это что то другое, более сложное и я все опять не правильно понял?
Миниатюры
Дерево, бинарное дерево  
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.08.2013, 14:12     Дерево, бинарное дерево
Посмотрите здесь:

C++ Бинарное дерево
Бинарное дерево C++
C++ Бинарное дерево
Бинарное дерево C++
Бинарное дерево C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
VLK
 Аватар для VLK
192 / 161 / 12
Регистрация: 05.05.2013
Сообщений: 1,221
23.08.2013, 14:17  [ТС]     Дерево, бинарное дерево #2
Блин не успел отредактировать, самая последняя картинка неверная, на ней не верно записаны значения.
MickeyBlueEyes
Студент
 Аватар для MickeyBlueEyes
120 / 131 / 12
Регистрация: 07.04.2011
Сообщений: 503
23.08.2013, 14:20     Дерево, бинарное дерево #3
Начало подразумевает корень, корень тоже имеет начальное значение, допустим 20, и затем при добавлении сравнивается если число 10 меньше числа 20, то ложим в лево, а если не, то в право.
VLK
 Аватар для VLK
192 / 161 / 12
Регистрация: 05.05.2013
Сообщений: 1,221
23.08.2013, 14:24  [ТС]     Дерево, бинарное дерево #4
MickeyBlueEyes, то, что выделено жирным : дерево, этот тот же список, только в нем не линейно идут записи, а в зависимости от записи.

это верное утверждение?
zer0mail
2187 / 1870 / 187
Регистрация: 03.07.2012
Сообщений: 6,656
Записей в блоге: 1
23.08.2013, 14:27     Дерево, бинарное дерево #5
У бинарного дерева 2 указателя: на правое и левое поддерево (по картинкам это не очевидно). Насколько я помню, ключи в левом поддереве меньше, чем в текущем узле, а в правом -ключи больше или равны текущему.
VLK
 Аватар для VLK
192 / 161 / 12
Регистрация: 05.05.2013
Сообщений: 1,221
23.08.2013, 14:30  [ТС]     Дерево, бинарное дерево #6
zer0mail, т.е. в левой стороне могут (должны присутствовать) правые указатели (PtrR) ну и соответственно наоборот?

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


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

На картинках - бинарное дерево, у которого может быть только 2 потомка. Это разновидность, ведь список, например, тоже может быть нелинейным.
VLK
 Аватар для VLK
192 / 161 / 12
Регистрация: 05.05.2013
Сообщений: 1,221
23.08.2013, 14:41  [ТС]     Дерево, бинарное дерево #8
Ладно, пойду еще литературы читать, вечерком продолжу задавать вопросы.
zer0mail
2187 / 1870 / 187
Регистрация: 03.07.2012
Сообщений: 6,656
Записей в блоге: 1
23.08.2013, 14:45     Дерево, бинарное дерево #9
У каждого узла 2 указателя (один или даже оба могут быть пустыми). Главное, дерево балансируется "в целом", поэтому при добавлении нового значения (и нового узла) приходится его перестраивать. Условия баланса: левые значения меньше текущего, правые не меньше текущего + ограничения на высоту поддеревьев (иначе можно построить "дерево", где только правые указатели заполнены, т.е фактически список).

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

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

или все же то, что я нарисовал это дерево, но тупое и примитивное?
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
23.08.2013, 14:58     Дерево, бинарное дерево #11
Цитата Сообщение от VLK Посмотреть сообщение
zer0mail, я просто не совсем понимаю: есть звено, и по логике от него могут отходить всего 2 звена - число больше направо, число меньше налево, но вы говорите о третьем и более ответвлении откуда оно берется, я не понимаю или может мой пример изначально не правильный?
Узел - такая структура, где есть поля для: значение, указателя на левого потомка, на правого потомка.
В дереве есть корень - начальный узел, у которого нет предка. Предок для узла X - это такой узел, Y, где X является потомком (в этом дереве - либо левым, либо правым потомком). Нигде 3 связи нету, если только не захочешь хранить указатель на предка.
Дерево, где максимум два узла могут являться потомками для какого-то узла, называется бинарным. Насколько я помню, бинарное дерево поиска - такое дерево, где при добавлении какого-то значения происходит такая проверка: если это значение меньше текущего - добавить в левое поддерево, иначе - в правое.
Остальное - уже вторично, например, если в двоичное дерево поиска добавлять элементы только в порядке возрастания, то дерево будет выглядеть так:
[]
*\
**[]
***\
****[]
***** \
******[]
Для таких случаев придуманы красно-черные деревья и способы балансировки.
Atlant_V
8 / 8 / 1
Регистрация: 14.08.2013
Сообщений: 99
23.08.2013, 15:06     Дерево, бинарное дерево #12
вот как выглядит бинарное дерево на примере. Если надо могу поискать код, как раз сегодня писал.
p.s. Извиняюсь за свои художественные таланты, кроме paint ничего на кампе нет
Миниатюры
Дерево, бинарное дерево  
zer0mail
2187 / 1870 / 187
Регистрация: 03.07.2012
Сообщений: 6,656
Записей в блоге: 1
23.08.2013, 15:20     Дерево, бинарное дерево #13
Цитата Сообщение от VLK Посмотреть сообщение
zer0mail...но вы говорите о третьем и более ответвлении откуда оно берется, я не понимаю или может мой пример изначально не правильный?
Про третье ответвление я не говорил. Почитайте для начала: http://www.declic.narod.ru/ossio/fil.../part_7_3.html
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.08.2013, 15:28     Дерево, бинарное дерево
Еще ссылки по теме:

C++ Дерево бинарное
Бинарное дерево. С++ C++
Бинарное дерево C++

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

Или воспользуйтесь поиском по форуму:
VLK
 Аватар для VLK
192 / 161 / 12
Регистрация: 05.05.2013
Сообщений: 1,221
23.08.2013, 15:28  [ТС]     Дерево, бинарное дерево #14
Короче, всем принявшим участи в обсуждении, спасибо, по большому счету это то, что я рисовал, только я не смог толком нарисовать и толком описать.
Yandex
Объявления
23.08.2013, 15:28     Дерево, бинарное дерево
Ответ Создать тему
Опции темы

Текущее время: 05:15. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru