Структуры и алгоритмы обработки данных

       

Создание дерева бинарного поиска :


(псевдокод)

  writeln(' Введите элемент массива ');

  readln(key);

  tree:=maketree(key);

  p:=tree;

  while not eof do

    begin

      readln(key);

      v:=maketree(key);

      while p<>nil do

         begin

             q:=p;

             if key<k(p) then p:=left(p)

             else p:=right(p);

         end;

         if p=nil then

            begin

                writeln('Это корень');

                tree:=v;

            end

            else

               if key<k(q) then left(p):=v

               else right(p):=v;

    end;

При обходе дерева слева - направо получаем отсортированный массив 20, 30, 35, 45, 60, 70, 82, 85, 86, 87, 88, 90. Элемент дерева заносится в массив при втором заходе в него (на рисунке вторые заходы показаны зелеными стрелками).



Содержание раздела