Бинарное дерево

← →
ReStudent © (2005-10-08 18:51) [0]

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

Алгоритм заполнения дерева:
1. Выбрать очередной идентификатор из входного потока данных. Если очередного идентификатора нет, то построение дерева закончено.

2. Сделать текущим узлом дерева корневую вершину.

3. Сравнить имя очередного идентификатора с именем идентификатора, содержащегося в текущем узле дерева.

4. Если имя очередного идентификатора меньше, то перейти к шагу 5, если равно — прекратить выполнение алгоритма (двух одинаковых идентификаторов быть не должно!), иначе — перейти к шагу 7.

5. Если у текущего узла существует левая вершина, то сделать ее текущим узлом и вернуться к шагу 3, иначе — перейти к шагу 6.

6. Создать новую вершину, поместить в нее информацию об очередном идентификаторе, сделать эту новую вершину левой вершиной текущего узла и вернуться к шагу 1.

7. Если у текущего узла существует правая вершина, то сделать ее текущим узлом и вернуться к шагу 3, иначе — перейти к шагу 8.

8. Создать новую вершину, поместить в нее информацию об очередном идентификаторе, сделать эту новую вершину правой вершиной текущего узла и вернуться к шагу 1.

Алгоритм поиска по дереву:
1. Сделать текущим узлом дерева корневую вершину.

2. Cравнить имя искомого идентификатора с именем идентификатора, содержащимся в текущем узле дерева.

3. Если имена совпадают, то искомый идентификатор найден, алгоритм завершается, иначе надо перейти к шагу 4.

4. Если имя очередного идентификатора меньше, то перейти к шагу 5, иначе - перейти к шагу 6.

5. Если у текущего узла существует левая вершина, то сделать ее текущим узлом и вернуться к шагу 2, иначе — искомый идентификатор не найден, алгоритм завершается.

6. Если у текущего узла существует правая вершина, то сделать ее текущим узлом и вернуться к шагу 2, иначе — искомый идентификатор не найден, алгоритм завершается.

← →
Zeqfreed © (2005-10-08 19:00) [1]

ReStudent © (08.10.05 18:51)
А тебе нужно именно помочь написать программу, или написать программу? Если второе, то ты забыл кое-что указать - цену, а если первое, то ты забыл указать с чем конкретно помочь и в чем у тебя возникли трудности.

← →
TUser © (2005-10-09 11:35) [2]

Алгоритм описан детально. Осталось перевести его на Паскаль.

← →
Igorek © (2005-10-10 10:38) [3]

Напишу. Строка кода - бакс. Предоплата.

← →
ReStudent © (2005-10-11 17:05) [4]

Сюда вообще похоже бесполезно писать.
Все зарабатывают.

← →
Джо © (2005-10-11 17:07) [5]

> [4] ReStudent © (11.10.05 17:05)
> Сюда вообще похоже бесполезно писать.
> Все зарабатывают.

Не все. Некоторые еще и студенты-двоешники :)

← →
ReStudent © (2005-10-11 17:09) [6]

Такая простая для кодера прога. Раз плюнуть для него. Доллар - строка.. блин.

← →
Ketmar (2005-10-11 17:10) [7]

>ReStudent © (11.10.05 17:05) [4]
а ты думал, за твои домашние задания тут драка будет -- кто достойней их напишет?

← →
TUser © (2005-10-11 17:30) [8]

> Такая простая для кодера прога. Раз плюнуть для него. Доллар - строка.. блин.

А еще вот для кодера на форуме постить - не проблема. Они же не будут за тебя вопросы задавать. :)

← →
Игорь Шевченко © (2005-10-11 17:34) [9]

ReStudent © (11.10.05 17:09) [6]

> Такая простая для кодера прога. Раз плюнуть для него. Доллар
> - строка.. блин.

Это демпинг. На самом деле - доллар минута, но для студентов делается скидка.

← →
boriskb © (2005-10-11 17:38) [10]

ReStudent © (08.10.05 18:51)
написать программу,

Интересно как!
Так она в твоем же посте ниже написана!
Тебе закодить? И не осилишь?
Ты даже не двоешник - хуже.

← →
Seg (2005-10-11 17:44) [11]

Такая простая для кодера прога

Вот и обращайся к кодерам, а здесь программисты...

← →
Ketmar (2005-10-11 17:51) [12]

>Seg (11.10.05 17:44) [11]
не все. я -- кодер. термин понимать, исходя из реалий demomaking"а.

← →
pasha_golub © (2005-10-11 17:54) [13]

А может у автора дети малые, жена и теща на шее, а сам он с утра до ночи работает, вагоны разгружая. А вы так на него... Изверги.

← →
Игорь Шевченко © (2005-10-11 17:55) [14]

pasha_golub © (11.10.05 17:54) [13]

А нафига ему тогда программа ? :)

← →
Ketmar (2005-10-11 17:56) [15]

>Игорь Шевченко © (11.10.05 17:55) [14]
оптимизировать процесс разгрузки вагонов и траекторию спирания грузов.

← →
pasha_golub © (2005-10-11 18:01) [16]

Ketmar (11.10.05 17:56) [15]
Прально, грузы можно ведь складывать в виде бинарного дерева, а потом быстро искать

← →
DiamondShark © (2005-10-11 18:02) [17]

Тогда бакса за строку маловато будет...

← →
Ketmar (2005-10-11 18:13) [18]

>DiamondShark © (11.10.05 18:02) [17]
дык это ж только начало торга...

← →
ReStudent © (2005-10-11 20:47) [19]

невпепенно крутые программисты

← →
Kerk © (2005-10-11 20:52) [20]

ReStudent © (11.10.05 20:47) [19]

"втупил в разговор" (с)

:))

← →
ReStudent © (2005-10-11 20:54) [21]

может ещё и за трёп бабло будете брать?

← →
Gero © (2005-10-11 20:55) [22]

> ReStudent ©

С чем возникли проблемы при написании?

← →
Gero © (2005-10-11 20:57) [23]

> может ещё и за трёп бабло будете брать?

Может и будем.

← →
ReStudent © (2005-10-11 21:07) [24]

> С чем возникли проблемы при написании?

Допустим структура задана, дерево заполнено.
Как и где указывается корень дерева? Чтоб сделать текущий указатель корнем дерева.

← →
Kerk © (2005-10-11 21:15) [25]

ReStudent © (11.10.05 21:07) [24]
Допустим структура задана, дерево заполнено.

Нифига не допустим. Если все это сделано, то проблем с корнем у тебя не будет.

← →
TUser © (2005-10-11 21:43) [26]

> Как и где указывается корень дерева?

При этом существует переменная, которая есть, например, указатель на корень дерева.

> Если все это сделано, то проблем с корнем у тебя не будет.

А вот это, кстати, не факт. Я тут рассказал про сортировку двусвязного списка. Рассказывал студентке одной. Вроде бы ей было не понятно, что элементы этого списка просты ссылаются друг на друга, не обызаны идти последовательно в памяти, и что надо просто переписать указатели. Простые вещи могут вызывать у начинающих затруднения - это нормально.

← →
Kerk © (2005-10-11 21:47) [27]

TUser © (11.10.05 21:43) [26]
Простые вещи могут вызывать у начинающих затруднения - это нормально.

Ну это понятно. Просто не пойму.. как можно построить дерево, но не знать где у него корень. ИМХО тут скорее проблема в непонимании того как дерево строится.

← →
TUser © (2005-10-11 21:49) [28]

> ИМХО тут скорее проблема в непонимании того как дерево строится.

Проблема - в непонимании, как готовый алгоритм преобразовать в код, имхо.

У меня такого указателя - на корень. Есть просто указатель на узел, на правй и левй подузел. И всё.

Type pt=^node;
node = Record
Data : string[10];
left,right : pt;
end;

← →
Sergey_Masloff (2005-10-11 22:08) [31]

Ну так указатель на корень и будет деревом. Если он nil то дерево пустое. Если он не nil но у того узла на который он указывает left = right = nil то это дерево из одного корня. И так далее

> Просто не пойму.. как можно построить дерево, но не знать
> где у него корень. ИМХО тут скорее проблема в непонимании
> того как дерево строится.

Запросто. Любой ацикличный граф - это дерево. Ты дерево сделал и послал кому-то. Ты не знаешь где корень (для тебя это граф, хотя ты в курсе, что это дерево, но не знаешь где корень), получатель - знает (для него это дерево). Во загнул! :)

> может ещё и за трёп бабло будете брать?

Будем. за букву наших ответов - с тебя рупь. Иначе - бан.

Халявщики - маст дай.

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

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

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

Теперь проблем с определением корня нет???

Удалено модератором

Бинарное дерево Найти похожие ветки