Главная страница
    Top.Mail.Ru    Яндекс.Метрика
Форум: "Основная";
Текущий архив: 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
15-1169657987
Rouse_
2007-01-24 19:59
2007.02.18
Мини ММП в пятницу


11-1148065780
AndreyRus
2006-05-19 23:09
2007.02.18
KOL&amp;ClearType bug


1-1167063016
Sam Stone
2006-12-25 19:10
2007.02.18
Уход модальных форм на задний план


2-1170190894
Marker
2007-01-31 00:01
2007.02.18
Цветные строки в TMemo


1-1166132647
el_n
2006-12-15 00:44
2007.02.18
бинарные деревья





Afrikaans Albanian Arabic Armenian Azerbaijani Basque Belarusian Bulgarian Catalan Chinese (Simplified) Chinese (Traditional) Croatian Czech Danish Dutch English Estonian Filipino Finnish French
Galician Georgian German Greek Haitian Creole Hebrew Hindi Hungarian Icelandic Indonesian Irish Italian Japanese Korean Latvian Lithuanian Macedonian Malay Maltese Norwegian
Persian Polish Portuguese Romanian Russian Serbian Slovak Slovenian Spanish Swahili Swedish Thai Turkish Ukrainian Urdu Vietnamese Welsh Yiddish Bengali Bosnian
Cebuano Esperanto Gujarati Hausa Hmong Igbo Javanese Kannada Khmer Lao Latin Maori Marathi Mongolian Nepali Punjabi Somali Tamil Telugu Yoruba
Zulu
Английский Французский Немецкий Итальянский Португальский Русский Испанский