Реализация бинарных деревьев.

← →
Glex © (2006-01-27 18:55) [0]

Мне нужно за 5 часов научиться полностью работать с бинарными деревьями.
Я нигде не нашёл толкового справочника именно по реализации деревьев в Delphi.
Я попробовал описать тип дерева сам.
Вот:
type pt = ^joint; joint = record Val: integer; Left, Right: pt; end; ... var tree: pt;
Я не имею понятия о правильности придуманного мной описания дерева.

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

ПОМОГИТЕ!!!!!!

← →
Glex © (2006-01-27 18:58) [1]

Я уже всем наверное надоел))))
Но обещаю сделать что-нибудь хорошее для обучения таких же как я потом)

← →
Кефир87 © (2006-01-27 19:36) [2]

Ркурсия!

procedure DoTmthWithNode(node:pt); begin pt.blablabla := 45454; new(pt.Left); new(pt.Right); DoThthWithNode(pt.Left); DoThthWithNode(pt.Right); end;

← →
Кефир87 © (2006-01-27 19:37) [3]

Пальцы кривые 8) Хотя все равно в этом коде нет смысла и в итоге он вызовет переполнение стэка 8)
procedure DoTmthWithNode(node:pt); begin pt.blablabla := 45454; new(pt.Left); new(pt.Right); DoTmthWithNode(pt.Left); DoTmthWithNode(pt.Right); end;

← →
Glex © (2006-01-27 19:52) [4]

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();

← →
Glex © (2006-01-27 19:54) [5]

type pt = ^node; node = record Val: integer; Left, Right: pt; end;

Это правильно, или можно так не извращаться с указателями? =)

← →
Glex © (2006-01-27 20:17) [6]

Умоляю, помогите, и, если реально, предложите способ без рекурсии, но с циклом

← →
Glex © (2006-01-27 20:21) [7]

Исправил ошибки в алгоритме Кефира.

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:29) [8]

Yahoo!!! Кефир, с меня кефир!!!!

Нужно было инициализировать само tree командой new(tree)

← →
Cash © (2006-01-27 20:30) [9]

Ужас! как так без деревьев то жить можно? (особенно без бинарных :D)
Ониж кислород дают.
:) :) :) :)

А если в серьез, то вам сюда, товарищ!:
http://algolist.manual.ru

Если и после этого вопросы будут, отпишись, постараюсь пояснить.

← →
Glex © (2006-01-27 20:43) [10]

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;

← →
Kolan © (2006-01-27 21:23) [11]

Вот глянь
http://www.fvt.rsu.ru/index.php?page=student&selection=main&navigation=help_main&topic=help

Там две статьи к сожалению про деревья недописана.

НО Проекты там рабочие. И автор я вопросы - пожалуйста.

← →
Кефир87 © (2006-01-27 21:52) [12]

> 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:55) [13]

В любом случае советую использовать объекты...
ЗЫ
Там тебе только одна статья нужна, про деревья...

← →
Кефир87 © (2006-01-27 21:57) [14]

ТФУ
procedure DoSmthWithNode(node:pt); begin node.val := 45454; new(node.Left); new(node.Right); DoTmthWithNode(node.Left); DoTmthWithNode(node.Right); end;

И еще раз хочу сказать! В этой процедуре нужно сделать какое-то услове, при котором она не будет вызывать сама себя. Иначе переполнение стэка! Например:
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;

В этом коде надо понять только идею!

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;

> Glex © (27.01.06 18:55)
>
> Мне нужно за 5 часов научиться полностью работать с бинарными
> деревьями.

Боюсь... мы не успели...

UUps.... :)

Ничего, теперь у меня ещё год)

[19]:
Не взяли чтоли?
А тебе куда надо было то?

Реализация бинарных деревьев. Найти похожие ветки