бинарное дерево?Файл?

AnonymC · Регистрация: 23.06.2009

объясните пожалуйста что означает слово бинарное?

@Андрейка · 21.02.2010, 23:25

МедведЪ,
Бинарное (двоичное) дерево (binary tree) - это упорядоченное дерево, каждая вершина которого имеет не более двух поддеревьев, причем для каждого узла выполняется правило: в левом поддереве содержатся только ключи, имеющие значения, меньшие, чем значение данного узла, а в правом поддереве содержатся только ключи, имеющие значения, большие, чем значение данного узла.

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

Узел дерева, не имеющий потомков, называется листом.

Добавлено через 1 минуту
МедведЪ, а да ещё почитай раздел дискретной математики - графы и его подраздел деревья)
ну и динамические структуры данных посмотри 2 варианта работы с деревом ( рекурсивный и цикловой)

Day · 22.02.2010, 07:14

МедведЪ, Бинарное дерево - это абстакция.
Андрейка все правильно тебе рассказал.
А ПРЕДСТАВИТЬ его - можно в файле, можно на бумажке нарисовать, можно в голове держать,
можно по нему лазить - это уж как получится

Узел дерева, не имеющий потомков, называется листом.

Или сучком

AnonymC · 22.02.2010, 11:52 **[ТС]**

Андрейка, все таки я не понял что такое дерево...может это меню с его подглавами?и подподглавами?может что то

C++

1	case 1:case 2:case 3

?
если нет то приведите код

Day · 22.02.2010, 12:38

МедведЪ,

может это меню с его подглавами?и подподглавами

Да, это дерево, токмо не бинарное. У бинарного - 2 ветки в каждом узле.
Вот конструкция "if... else ..." - это уже бинарное древо, а "if ... else if... else..." -
уже не бинарное. Вообще в программирование деревья - на каждом шагу. Лес, тайга, сельва,
часто и бурелом..."
Бинарные деревья проще в теории (о них можно больше интересного сказать), поэтому
теоретики пытаются прочие дерева свести к бинарным.
Это тоже самое что вместо "switch.. case..." написать "if ... else { if ... else { if... } }"
По-моему легче всего понять смысл дерева - это взять лист бумаги и чего-нибудь на нем нарисовать. Какой-нибудь граф без циклов.

если нет то приведите код

Код тут не поможет. Тут надо привести все мироздание.

AnonymC · 22.02.2010, 12:40 **[ТС]**

понятно, а файл?

Day · 22.02.2010, 13:02

Сообщение от МедведЪ

понятно, а файл?

Хмм.
Файл - это хранилище, картотека. Хотя если хочется (или нужно) можно рассматривать сам файл
как корень, а его записи (или строчки) - как ветки. А буковки - как ветки, а битики (из которых
состоят байты) - как ветки следующего порядка. А можно рассматривать слова как ветки -
все зависит от твоей задачи.
Вот файловая структура (Диск - папки - файлы) - это точно дерево.
Дерево - это мысленная абстракция, которую мы накладываем (или в которую вкладываем),
на занимающую нас часть реального мира, чтобы с ней совладать.
Единственное ограничение дерева (в отличии от общего графа) - циклов быть не должно.
Вот Help какой-нибудь или Интернет - это уже не дерево, щелкая по ссылочкам ты прекрасно можешь вернуться в место, в котором уже побывал.
Короче - дерево это инструмент мышления, как язык, например (естесственный или алгоритмический - без разницы). И очень эффективный.

AnonymC · 22.02.2010, 16:52 **[ТС]**

Day, не понимаю

можно пример?

@Patch · 22.02.2010, 17:36

Сообщение от МедведЪ

не понимаюможно пример?

пожалуйста. библиотечное дерево.

_______________1__а
___________1______аб
_______________0__б
______1___________аб
_1________________абвг
___________1______в
______0___________вг
___________0______г

Позволяет быстро найти нужную букву.
В малом масштабе удобство хранения и скорость поиска оценить трудно, но представьте дерево с тысячей листьев!

AnonymC · 22.02.2010, 17:54 **[ТС]**

Patch,

Добавлено через 17 секунд
что за 1 и 0 там

@Patch · 22.02.2010, 17:59

Сообщение от МедведЪ

что за 1 и 0 там

считай это кодом строки.

мне просто так представлять удобнее.
код - это ветки, а буквы - листья.
чтобы добраться до нужного листа, нужно пройти по веткам, согласно схеме дерева.

без такой бинарной схемы пришлось бы искать нужную букву перебором всего объема данных.

AnonymC · 22.02.2010, 18:01 **[ТС]**

Patch, а можно код С++ с этим файлом?если не трудно...а то не догоняю...или статью где для новичков норм объясняется

@Patch · 22.02.2010, 18:35

ёпрст...
примитивный вариант поиска данных по индексному бинарному дереву.

C++

Node{
     l_Node *Node; //левый узел
     r_Node *Node; //правый узел
     char value;     //ключ
     int mass[100]; //какие-то индексируемые ключами данные
};
Node * find_node(char val, Node * lpNode)
{
     if(val <= lpNode ->Value) //если искомое меньше текущего, или равно ему - ищем слева
     {
         if(lpNode->l_Node == 0) return lpNode;
         return(find_node(val, lpNode->l_Node));
     }
     if(lpNode->r_Node == 0) return lpNode;  //иначе - ищем справа
     return(find_node(val, lpNode->r_Node));
}

AnonymC 1182 / 467 / 87 Регистрация: 23.06.2009 Сообщений: 6,390
		1
	бинарное дерево?Файл? 21.02.2010, 21:30. Просмотров 2170. Ответов 12 Метки нет (Все метки) объясните пожалуйста что означает слово бинарное? 0

@Андрейка 423 / 227 / 87 Регистрация: 25.03.2009 Сообщений: 744
	21.02.2010, 23:25	2
	МедведЪ, Бинарное (двоичное) дерево (binary tree) - это упорядоченное дерево, каждая вершина которого имеет не более двух поддеревьев, причем для каждого узла выполняется правило: в левом поддереве содержатся только ключи, имеющие значения, меньшие, чем значение данного узла, а в правом поддереве содержатся только ключи, имеющие значения, большие, чем значение данного узла. Бинарное дерево является рекурсивной структурой, поскольку каждое его поддерево само является бинарным деревом и, следовательно, каждый его узел в свою очередь является корнем дерева. Узел дерева, не имеющий потомков, называется листом. Добавлено через 1 минуту МедведЪ, а да ещё почитай раздел дискретной математики - графы и его подраздел деревья) ну и динамические структуры данных посмотри 2 варианта работы с деревом ( рекурсивный и цикловой) 1

Day 1171 / 981 / 83 Регистрация: 29.10.2009 Сообщений: 1,386
	22.02.2010, 07:14	3
	МедведЪ, Бинарное дерево - это абстакция. Андрейка все правильно тебе рассказал. А ПРЕДСТАВИТЬ его - можно в файле, можно на бумажке нарисовать, можно в голове держать, можно по нему лазить - это уж как получится Узел дерева, не имеющий потомков, называется листом. Или сучком 0

Day 1171 / 981 / 83 Регистрация: 29.10.2009 Сообщений: 1,386
	22.02.2010, 12:38	5
	МедведЪ, может это меню с его подглавами?и подподглавами Да, это дерево, токмо не бинарное. У бинарного - 2 ветки в каждом узле. Вот конструкция "if... else ..." - это уже бинарное древо, а "if ... else if... else..." - уже не бинарное. Вообще в программирование деревья - на каждом шагу. Лес, тайга, сельва, часто и бурелом..." Бинарные деревья проще в теории (о них можно больше интересного сказать), поэтому теоретики пытаются прочие дерева свести к бинарным. Это тоже самое что вместо "switch.. case..." написать "if ... else { if ... else { if... } }" По-моему легче всего понять смысл дерева - это взять лист бумаги и чего-нибудь на нем нарисовать. Какой-нибудь граф без циклов. если нет то приведите код Код тут не поможет. Тут надо привести все мироздание. 1

AnonymC 1182 / 467 / 87 Регистрация: 23.06.2009 Сообщений: 6,390
	22.02.2010, 12:40 [ТС]	6
	понятно, а файл? 0

Day 1171 / 981 / 83 Регистрация: 29.10.2009 Сообщений: 1,386
	22.02.2010, 13:02	7
	Сообщение от МедведЪ понятно, а файл? Хмм. Файл - это хранилище, картотека. Хотя если хочется (или нужно) можно рассматривать сам файл как корень, а его записи (или строчки) - как ветки. А буковки - как ветки, а битики (из которых состоят байты) - как ветки следующего порядка. А можно рассматривать слова как ветки - все зависит от твоей задачи. Вот файловая структура (Диск - папки - файлы) - это точно дерево. Дерево - это мысленная абстракция, которую мы накладываем (или в которую вкладываем), на занимающую нас часть реального мира, чтобы с ней совладать. Единственное ограничение дерева (в отличии от общего графа) - циклов быть не должно. Вот Help какой-нибудь или Интернет - это уже не дерево, щелкая по ссылочкам ты прекрасно можешь вернуться в место, в котором уже побывал. Короче - дерево это инструмент мышления, как язык, например (естесственный или алгоритмический - без разницы). И очень эффективный. 0

AnonymC 1182 / 467 / 87 Регистрация: 23.06.2009 Сообщений: 6,390
	22.02.2010, 16:52 [ТС]	8
	Day, не понимаюможно пример? 0

@Patch 2341 / 497 / 22 Регистрация: 01.04.2009 Сообщений: 2,200
	22.02.2010, 17:36	9
	Сообщение от МедведЪ не понимаюможно пример? пожалуйста. библиотечное дерево. _______________1__а ___________1______аб _______________0__б ______1___________аб _1________________абвг ___________1______в ______0___________вг ___________0______г Позволяет быстро найти нужную букву. В малом масштабе удобство хранения и скорость поиска оценить трудно, но представьте дерево с тысячей листьев! 0

AnonymC 1182 / 467 / 87 Регистрация: 23.06.2009 Сообщений: 6,390
	22.02.2010, 17:54 [ТС]	10
	Patch, Добавлено через 17 секунд что за 1 и 0 там 0

@Patch 2341 / 497 / 22 Регистрация: 01.04.2009 Сообщений: 2,200
	22.02.2010, 17:59	11
	Сообщение от МедведЪ что за 1 и 0 там считай это кодом строки. мне просто так представлять удобнее. код - это ветки, а буквы - листья. чтобы добраться до нужного листа, нужно пройти по веткам, согласно схеме дерева. без такой бинарной схемы пришлось бы искать нужную букву перебором всего объема данных. 0

Опции темы

AnonymC 1182 / 467 / 87 Регистрация: 23.06.2009 Сообщений: 6,390
	22.02.2010, 18:01 [ТС]	12
	Patch, а можно код С++ с этим файлом?если не трудно...а то не догоняю...или статью где для новичков норм объясняется 0