Форум: "Основная";
Текущий архив: 2007.02.18;
Скачать: [xml.tar.bz2];
Вниз
бинарные деревья Найти похожие ветки
← →
el_n (2006-12-15 00:44) [0]Приветствую.
Кто нибудь сталкивался с бинарными деревьями?
Вопроса, и оба простейшие, однако, меня они вводят в ступор:
1) как осуществить симметричный проход дерева
2) как при прямом (на худой конец симметричном) проходах определить уровни для каждой вершины дерева?
поделитесь сорцем, или советом, кто может.
← →
MBo © (2006-12-15 07:24) [1]три из четырех распространенных обходов дерева в рекурсивном виде выглядят примерно так:
procedure Traverse(Node: PNode);
begin
if Node = Nil then Exit;
//1
Traverse(Node.Left) ;
//2
Traverse(Node.Right) ;
//3
end;
В одно из помеченных мест вставляется вывод метки узла
PrintOut(Node.Data);
А для определения уровня нужно этой процедуре добавить еще один параметр Level, а внутренние вызовы делать с Level+1
← →
ors_archangel © (2006-12-20 06:36) [2]Пример, который я использую как альтернативный код при быстрой сортировке для малых подфайлов. Я здесь написал, что использую фланговый обход... видимо, что это то же, что и симметричный, так как процедура называется LookupInOrder - а "inorder" означает "по внутреннему порядку", а обход по внутреннему порядку и симметричный обход уже точно помню, что одно и то же.
procedure TreeSort;
{ Сортировка бинарным деревом (не путать с пирамидальной!):
1. создаём бинарное дерево по значениям блока (без балансировки)
2. делаем фланговый обход, записывая извлекаемые значения }
type
PTreeItem = ^TTreeItem;
TTreeItem = record
val: int;
left,right: PTreeItem;
end;
function LookupInOrder(ai: PInt; item: PTreeItem): PInt;
{$ifdef PURE_PASCAL}
begin
if item.left <> nil then ai := LookupInOrder(ai, item.left); // идём влево
ai^ := item.val; // запись значения (относительный корень)
inc(ai);
if item.right <> nil then ai := LookupInOrder(ai, item.right); // идём направо
result := ai;
end;
{$else}
asm
@@0:
mov ecx,[edx].TTreeItem.left
test ecx,ecx
jz @@1
push edx
mov edx,ecx
call @@0
pop edx
@@1:
mov ecx,[edx]
mov [eax],ecx
add eax,4
mov ecx,[edx].TTreeItem.right
test ecx,ecx
jz @@2
mov edx,ecx
jmp @@0
@@2:
end;
{$endif}
var
ai: PInt;
t: int;
i: int;
tree: TTreeItem;
slot: array[0..QSORT_SMALL-1] of TTreeItem;
item: PTreeItem;
begin
ai := al;
{ build B-tree }
tree.val := ai^;
tree.left := nil;
tree.right := nil;
inc(ai);
for i := 1 to c-1 do begin
t := ai^;
item := @tree;
with slot[i] do begin
val := t;
left := nil;
right := nil;
end;
repeat
if t <= item.val then
if item.left = nil then begin
item.left := @slot[i];
item := item.left;
break;
end else
item := item.left
else
if item.right = nil then begin
item.right := @slot[i];
item := item.right;
break;
end else
item := item.right;
until false;
inc(ai);
end;
{ write sorted values }
LookupInOrder(al, @tree);
end;
← →
TUser © (2006-12-20 07:22) [3]> симметричный проход дерева
А что это? Я знаю обходы дерева - прямой, обратный и смешанный, вроде так. А что такое симметричный?
← →
MBo © (2006-12-20 07:37) [4]>TUser © (20.12.06 07:22) [3]
>А что такое симметричный?
левый-корень-правый
← →
Alex xandr © (2006-12-24 16:56) [5]Огромное спасибо MBo. А то на лекциях ничего не рассказывают, а сам промучался целый день и смог только сгенерировать бинарное дерево... Вобщем огромное спасибо
← →
Alex xandr © (2006-12-24 16:57) [6]Огромное спасибо MBo. А то на лекциях ничего не рассказывают, а сам промучался целый день и смог только сгенерировать бинарное дерево... Вобщем огромное спасибо
Страницы: 1 вся ветка
Форум: "Основная";
Текущий архив: 2007.02.18;
Скачать: [xml.tar.bz2];
Память: 0.47 MB
Время: 0.036 c
