Алгоритм параллельного обхода дерева

From

Mike Roschin (2:5030/243.1)

To

Gennady Mayko

Date

2002-10-05T22:54:01Z

Area

RU.ALGORITHMS

∙Reply to msg from Gennady Mayko(2:5020/400)
∙To All written 01.Oct.2002, 11:27
Ave Gennady Mayko!

 GM> Есть некоторое дерево, точная структура его не известна. Какие есть
 GM> алгоритмы полного обхода дерева 
ВОзможно, что я чего-то не понимаю, но IMHO есть один-единствный способ обхода дерева: взался за корешок -> обошел левую ветку -> обошел правую ветку. Небольшие нюансы - непринципиальны.
 GM> с использованием нескольких потоков (процессоров)? 
 GM> Количество узлов дерева гораздо больше, чем количество потоков,
 GM> которые практически можно создать.

PROCEDURE ОбходДерева ( КорневойУзел : УзелДерева );
  BEGIN
    ВыполнитьОперациюНадУзлом ( КорневойУзел );

    IF ЕстьСвободныйПроцесс THEN    
      ЗапуститьПроцесс ( ОбходДерева ( КорневойУзел->Левое ) );
    ELSE
      ОбходДерева ( КорневойУзел->Левое );
    END;

    IF ЕстьСвободныйПроцесс THEN    
      ЗапуститьПроцесс ( ОбходДерева ( КорневойУзел->Правое ) );
    ELSE
      ОбходДерева ( КорневойУзел->Правое );
    END;

  END ОбходДерева;

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

Get Warped 3.0!  \\Thesis 
--- 
 * Origin:   Слоны по деревьям не лазают! \\The Oxygen.   (2:5030/243.1)