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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 5.00
VLK
194 / 163 / 12
Регистрация: 05.05.2013
Сообщений: 1,225
#1

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

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

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

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

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


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

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

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

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

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

Бинарное дерево - C++
#include "stdafx.h" #include <iostream> #include <conio.h> int last; void add(double volue) { //double *arr = new...

Бинарное дерево - C++
Здравствуйте.Прошу помощи.Никак не могу разобраться в задании.Нужно сделать бинарное дерево и с помощью дерева привести выражение к...

Бинарное дерево - C++
Здравствуйте.Прошу помощи.Никак не могу разобраться в задании.Нужно сделать бинарное дерево и с помощью дерева привести выражение к...

Бинарное дерево - C++
Народ помогите. На С++ нада написать программу бинарного дерева Требования: 1. В программе должен быть шаблонный класс (template...

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

это верное утверждение?
0
zer0mail
2354 / 1984 / 198
Регистрация: 03.07.2012
Сообщений: 7,117
Записей в блоге: 1
23.08.2013, 14:27 #5
У бинарного дерева 2 указателя: на правое и левое поддерево (по картинкам это не очевидно). Насколько я помню, ключи в левом поддереве меньше, чем в текущем узле, а в правом -ключи больше или равны текущему.
0
VLK
194 / 163 / 12
Регистрация: 05.05.2013
Сообщений: 1,225
23.08.2013, 14:30  [ТС] #6
zer0mail, т.е. в левой стороне могут (должны присутствовать) правые указатели (PtrR) ну и соответственно наоборот?

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


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

На картинках - бинарное дерево, у которого может быть только 2 потомка. Это разновидность, ведь список, например, тоже может быть нелинейным.
0
VLK
194 / 163 / 12
Регистрация: 05.05.2013
Сообщений: 1,225
23.08.2013, 14:41  [ТС] #8
Ладно, пойду еще литературы читать, вечерком продолжу задавать вопросы.
0
zer0mail
2354 / 1984 / 198
Регистрация: 03.07.2012
Сообщений: 7,117
Записей в блоге: 1
23.08.2013, 14:45 #9
У каждого узла 2 указателя (один или даже оба могут быть пустыми). Главное, дерево балансируется "в целом", поэтому при добавлении нового значения (и нового узла) приходится его перестраивать. Условия баланса: левые значения меньше текущего, правые не меньше текущего + ограничения на высоту поддеревьев (иначе можно построить "дерево", где только правые указатели заполнены, т.е фактически список).

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

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

или все же то, что я нарисовал это дерево, но тупое и примитивное?
0
Dani
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,282
Записей в блоге: 2
Завершенные тесты: 1
23.08.2013, 14:58 #11
Цитата Сообщение от VLK Посмотреть сообщение
zer0mail, я просто не совсем понимаю: есть звено, и по логике от него могут отходить всего 2 звена - число больше направо, число меньше налево, но вы говорите о третьем и более ответвлении откуда оно берется, я не понимаю или может мой пример изначально не правильный?
Узел - такая структура, где есть поля для: значение, указателя на левого потомка, на правого потомка.
В дереве есть корень - начальный узел, у которого нет предка. Предок для узла X - это такой узел, Y, где X является потомком (в этом дереве - либо левым, либо правым потомком). Нигде 3 связи нету, если только не захочешь хранить указатель на предка.
Дерево, где максимум два узла могут являться потомками для какого-то узла, называется бинарным. Насколько я помню, бинарное дерево поиска - такое дерево, где при добавлении какого-то значения происходит такая проверка: если это значение меньше текущего - добавить в левое поддерево, иначе - в правое.
Остальное - уже вторично, например, если в двоичное дерево поиска добавлять элементы только в порядке возрастания, то дерево будет выглядеть так:
[]
*\
**[]
***\
****[]
***** \
******[]
Для таких случаев придуманы красно-черные деревья и способы балансировки.
1
Atlant_V
8 / 8 / 1
Регистрация: 14.08.2013
Сообщений: 99
23.08.2013, 15:06 #12
вот как выглядит бинарное дерево на примере. Если надо могу поискать код, как раз сегодня писал.
p.s. Извиняюсь за свои художественные таланты, кроме paint ничего на кампе нет
1
Миниатюры
Дерево, бинарное дерево  
zer0mail
2354 / 1984 / 198
Регистрация: 03.07.2012
Сообщений: 7,117
Записей в блоге: 1
23.08.2013, 15:20 #13
Цитата Сообщение от VLK Посмотреть сообщение
zer0mail...но вы говорите о третьем и более ответвлении откуда оно берется, я не понимаю или может мой пример изначально не правильный?
Про третье ответвление я не говорил. Почитайте для начала: http://www.declic.narod.ru/ossio/files/book/part_7_3.html
1
VLK
194 / 163 / 12
Регистрация: 05.05.2013
Сообщений: 1,225
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
Привет! Вот еще темы с ответами:

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

Бинарное дерево - C++
Здравствуйте.Прошу помощи.Никак не могу разобраться в задании.Нужно сделать бинарное дерево и с помощью дерева привести выражение к...

Дерево бинарное - C++
Интересует вопрос, при добавлении нового элемента куда я его должен буду помещать, на какую ветку. Допустим есть дерево с корнем 5 и...

Бинарное дерево - C++
Нужно записать в дерево и вывести в форматированном виде каталог файлов(типа windows) на вход даны имена файлов вида c:\win\1 ...


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

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

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