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

       

Алгоритм создания дерева бинарного поиска


Пусть заданы элементы с ключами: 14, 18, 6, 21, 1, 13, 15. После выполнения нижеприведенного алгоритма получится дерево, изображенное на рис.4.6. Если обойти полученное дерево слева направо, то получим упорядочивание: 1, 6, 13, 14, 15, 18, 21.

Псевдокод

read (key, rec)

tree = maketree(key rec)

p = tree

q = tree

while not eof do

  read (key, rec)

  v = maketree(key, rec)

  while p <> nil do



    q = p

    if key < k(p) then

      p = left(p)

    else

      p = right(p)

    endif

  endwhile

    if key < k(q) then

      left(p) = v

    else

      right(p) = v

  endif

    if q=tree then

          ' только корень'

    endif  

return

Паскаль

read (key, rec);

tree := maketree(key rec);

p := tree;

q := tree;

while not eof do

  begin

    read (key, rec);

    v := maketree(key, rec);

    while p <> nil do

      begin

        q := p;

        if key < p^.k then

          p := p^.left

        else

          p := p^.right;

      end;

      if key < q^.k then

        p^.left := v

      else

        p^.right := v;

end

  if q=tree

    then writeln(‘Только корень’);

exit



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