бинарные деревья

← →
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]
>А что такое симметричный?
левый-корень-правый

Огромное спасибо MBo. А то на лекциях ничего не рассказывают, а сам промучался целый день и смог только сгенерировать бинарное дерево... Вобщем огромное спасибо

бинарные деревья Найти похожие ветки