Модели и структуры данных



         

Основные операции над деревьями. - часть 3


Принятые выше названия методов обхода связаны с временем обработки корневой вершины: До того как обработаны оба ее поддерева (Preorder), после того как обработано левое поддерево, но до того как обработано правое (Inorder), после того как обработаны оба поддерева (Postorder). Используемые в переводе названия методов отражают направление обхода в дереве: от корневой вершины вниз к листьям - нисходящий обход; от листьев вверх к корню - восходящий обход, и смешанный обход - от самого левого листа дерева через корень к самому правому листу.

Схематично алгоритм обхода двоичного дерева в соответствии с нисходящим способом может выглядеть следующим образом:

  • 1. В качестве очередной вершины взять корень дерева. Перейти к пункту 2.
  • 2. Произвести обработку очередной вершины в соответствии с требованиями задачи. Перейти к пункту 3.
  • 3.а) Если очередная вершина имеет обе ветви, то в качестве новой вершины выбрать ту вершину, на которую ссылается левая ветвь, а вершину, на которую ссылается правая ветвь, занести в стек; перейти к пункту 2;
  • 3.б) если очередная вершина является конечной, то выбрать в качестве новой очередной вершины вершину из стека, если он не пуст, и перейти к пункту 2; если же стек пуст, то это означает, что обход всего дерева окончен, перейти к пункту 4;
  • 3.в) если очередная вершина имеет только одну ветвь, то в качестве очередной вершины выбрать ту вершину, на которую эта ветвь указывает, перейти к пункту 2.
  • 4. Конец алгоритма.

Для примера рассмотрим возможные варианты обхода дерева (рис.6.26).

При обходе дерева представленного на рис.6.26 этими тремя методами мыполучим следующие последовательности: ABCDEFG ( нисходящий ); CBAFEDG ( смешанный ); CBFEGDA ( восходящий ).

Рис.6.26. Схема дерева

НИСХОДЯЩИЙ ОБХОД (Preorder, r_Preorder).

В соответствии с алгоритмом, приведенным выше, текст процедуры имеет вид:

{=== Программный пример 6.4. Нисходящий обход ===} Procedure Preorder (t: TreePtr); Type Stack=^Zveno; Zveno = record next: Stack; el: pointer; end; Var st: stack; p: TreePtr; (*------------ Процедура занесения в стек указателя ------*) Procedure Push_st (var st:stack; p:pointer); Var q: stack; begin new(q); q^.el:=p; q^.next:=st; st:=g; end; (*----------- Функция извлечения из стека указателя ------*) Function Pop_st (var st: stack):pointer; Var e,p: stack; begin Pop_st:=st^.el; e:=st; st:=st^.next; dispose(e); end; Begin if t = NIL then begin writeln('Дерево пусто'); exit; end else begin st:=nil; Push_st(St,t); end; while st <> nil do { контроль заполнения стека } begin p:=Pop_st(st); while p <> nil do begin { Обработка данных звена } if p^.right <> nil then Push_st(st,p^.right); p:=p^.left; end; end; End; { Preorder }




Содержание  Назад  Вперед