| Форумы
ЧАТ |
Орешник |
|
| Форумы -» | Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG |
|
| ||
|
|
Новости |
Поиск |
FAQ |
Статьи |
Книги |
Новости VCL
| | Форумы ЧАТ |
Орешник |
|
| |||
| |||
| |||
« предыдущая ветвь | форум | следующая ветвь »
Реализация бинарных деревьев.
Glex © (2006-01-27 18:55:00)Мне нужно за 5 часов научиться полностью работать с бинарными деревьями.
Я нигде не нашёл толкового справочника именно по реализациидеревьев в Delphi.
Я попробовал описать тип дерева сам.
Вот:
type pt = ^joint;
joint = record
Val: integer;
Left, Right: pt;
end;
...
var tree: pt;
Я не имею понятия о правильности придуманного мной описания дерева.
Дальше я попробовал построить дерево по значениям из массива, но у меня ничего не получилось. Я не имею ни малейшего понятия о заполнении такого дерева значениями.
ПОМОГИТЕ!!!!!!
Cash (2006-01-30 19:47:00) [1][19]:
Не взяли чтоли?
А тебе куда надо было то?
Glex (2006-01-30 19:37:00) [2]Ничего, теперь у меня ещё год)
Cash (2006-01-28 15:32:00) [3]UUps.... :)
Кефир87 (2006-01-28 15:14:00) [4]
> Glex © (27.01.06 18:55)
>
> Мне нужно за 5 часов научиться полностью работать с бинарными
> деревьями.
Боюсь... мы не успели...
Cash (2006-01-28 14:31:00) [5]Glex © (27.01.06 20:43) [10]:
А какое из бинарных тебе надо? АВЛ? СДП? или простое?
Кефир нормально расписал, но для понимания надож время,
а его, как я понял, у тебя нету. Так что сабж надо уточнить,
и тогда дам нужный код. Надо только знать какой тип дерева и
какая манипуляция с этим деревом.
Для наглядности, процедура заполнения из масива для СДП выглядит так:
Type
PTN = ^TTN;
TTN = record
Data: Word;
Left: PTN;
Right: PTN;
end;
var
Root: PTN;
Data: array [0..100] of word;
i: integer;
Function AddNode(DI: integer): PTN;
begin
New(Result);
Result^.Data:=DI;
Result^.Left:=nil;
Result^.Right:=nil;
end;
Procedure BuildTree(var R: PTN; DI: integer); // Это то, что надо
begin
if R^.Data < DI then begin
if R^.Right <> nil then BuildTree(R^.Right,DI)
else R^.Right:=AddNode(DI);
end else begin
if R^.Left <> nil then BuildTree(R^.Left,DI)
else R^.Left:=AddNode(DI);
end;
end;
begin
randomize;
for i:=0 to 100 do Data[i]:=random(1000)+1;
Root:=AddNode(Data[0]);
i:=1;
while i < 101 do begin
BuildTree(Root,Data[i]);
inc(i);
end;
end;
Кефир87 (2006-01-27 22:03:00) [6]И еще раз хочу сказать! В этой процедуре нужно сделать какое-то услове, при котором она не будет вызывать сама себя. Иначе переполнение стэка! Например:
procedure DoSmthWithNode(node:pt);
begin
node.val := 45454;
inc(counter);
if conter<100 then
begin
new(node.Left);
new(node.Right);
DoTmthWithNode(node.Left);
DoTmthWithNode(node.Right);
end;
end;
В этом коде надо понять только идею!
Кефир87 (2006-01-27 21:57:00) [7]ТФУ
procedure DoSmthWithNode(node:pt);
begin
node.val := 45454;
new( node.Left);
new( node.Right);
DoTmthWithNode( node.Left);
DoTmthWithNode( node.Right);
end;
Kolan (2006-01-27 21:55:00) [8]В любом случае советую использовать объекты...
ЗЫ
Там тебе только одна статья нужна, про деревья...
Кефир87 (2006-01-27 21:52:00) [9]
> procedure DoSmthWithNode(node:pt);
> begin
> pt.val := 45454;
> new(pt.Left);
> new(pt.Right);
> DoTmthWithNode(pt.Left);
> DoTmthWithNode(pt.Right);
> end;
>
> [Error] Object or class type required
> :((((((
>
Опять пальцы кривые:
procedure DoSmthWithNode( node:pt);
begin
pt.val := 45454;
new( node.Left);
new( node.Right);
DoTmthWithNode( node.Left);
DoTmthWithNode( node.Right);
end;
Kolan (2006-01-27 21:23:00) [10]Вот глянь
http://www.fvt.rsu.ru/index.php?page=student&selection=main&navigation=help_main&topic=help
Там две статьи к сожалению про деревья недописана.
НО Проекты там рабочие. И автор я вопросы - пожалуйста.
Glex (2006-01-27 20:43:00) [11]Cash
Там есть принципы и теория. Это я знаю Но там нет того, что мне надо!
Вопрос реализации на паскале.
Мне серьёзно некогда. 3 часа осталось. Мне техническую сторону, а там сам додумаю!
Ну помогите же кто-нибудь.
В алгоритме кефира правые деревья не будут обойдены даже так
procedure DoSmthWithNode(var node: pt; prevnode: pt);
begin
node.val := 45454;
node.Level:= prevNode.Level+1;
new(node.Left);
new(node.Right);
if Node.Level<=N then
DoSmthWithNode(node.Left, node);
if Node.Level<=N then
DoSmthWithNode(node.Right, node);
end;
Cash (2006-01-27 20:30:00) [12]Ужас! как так без деревьев то жить можно? (особенно без бинарных :D)
Ониж кислород дают.
:) :) :) :)
А если в серьез, то вам сюда, товарищ!:
http://algolist.manual.ru
Если и после этого вопросы будут, отпишись, постараюсь пояснить.
Glex (2006-01-27 20:29:00) [13]Yahoo!!! Кефир, с меня кефир!!!!
Нужно было инициализировать само tree командой new(tree)
Glex (2006-01-27 20:21:00) [14]Исправил ошибки в алгоритме Кефира.
procedure DoSmthWithNode(var node: pt);
begin
node.val := 45454;
new(node.Left);
new(node.Right);
DoSmthWithNode(node.Left);
DoSmthWithNode(node.Right);
end;
вылетает в конец программы на первой строчке 8-|
Glex (2006-01-27 20:17:00) [15]Умоляю, помогите, и, если реально, предложите способ без рекурсии, но с циклом
Glex (2006-01-27 19:54:00) [16]
type pt = ^node;
node = record
Val: integer;
Left, Right: pt;
end;
Это правильно, или можно так не извращаться с указателями? =)
Glex (2006-01-27 19:52:00) [17]
procedure DoSmthWithNode(node:pt);
begin
pt.val := 45454;
new(pt.Left);
new(pt.Right);
DoTmthWithNode(pt.Left);
DoTmthWithNode(pt.Right);
end;
[Error] Object or class type required
:((((((
Я идею понял, но не понимаю синтаксис до конца(
Например, new();
Кефир87 (2006-01-27 19:37:00) [18]Пальцы кривые 8) Хотя все равно в этом коде нет смысла и в итоге он вызовет переполнение стэка 8)
procedure DoTmthWithNode(node:pt);
begin
pt.blablabla := 45454;
new(pt.Left);
new(pt.Right);
DoTmthWithNode(pt.Left);
DoTmthWithNode(pt.Right);
end;
Кефир87 (2006-01-27 19:36:00) [19]Ркурсия!
procedure DoTmthWithNode(node:pt);
begin
pt.blablabla := 45454;
new(pt.Left);
new(pt.Right);
DoThthWithNode(pt.Left);
DoThthWithNode(pt.Right);
end;
Glex (2006-01-27 18:58:00) [20]Я уже всем наверное надоел))))
Но обещаю сделать что-нибудь хорошее для обучения таких же как я потом)
| |
