Предыдущая страница реферата | 1  2  3  4  5  6  7 | Следующая страница реферата

end;

/* C++ */

int Find(BinTree *Tree, BT x)

{ if (!Tree) return 0;

 else if (Tree->inf==x) return 1;

      else if (x < Tree->inf) return Find(Tree->L, x);

    else return Find(Tree->R, x);

}

По сравнению с предыдущими задача удаления узла из дерева реализуется несколько сложнее. Можно выделить два случая удаления элемента x (случай отсутствия элемента в дереве является вырожденным):

1) узел, содержащий элемент x, имеет степень не более 1 (степень узла — число поддеревьев, выходящих из этого узла);

2) узел, содержащий элемент x, имеет степень 2.

Случай 1 не представляет сложности. Предыдущий узел соединяется либо с единственным поддеревом удаляемого узла (если степень удаляемого узла равна 1), либо не будет иметь поддерева совсем (если степень узла равна 0).

Намного сложнее, если удаляемый узел имеет два поддерева. В этом случае нужно заменить удаляемый элемент самым правым элементом из его левого поддерева.

{Turbo Pascal}

function Delete(Tree: U; x: BT) : U;

var P, v : U;

begin

  if (Tree=nil)

  then writeln('такого элемента в дереве нет!')

  else if x < Tree^.inf then Tree^.L := Delete(Tree^.L, x) {случай 1}

                        else

                         if x > Tree^.inf

                         then Tree^.R := Delete(Tree^.R, x) {случай 1}

                         else

                         begin {случай 1}

Рекомендуем скачать другие рефераты по теме: бесплатно ответы, управление реферат.



Предыдущая страница реферата | 1  2  3  4  5  6  7 | Следующая страница реферата

Поделитесь этой записью или добавьте в закладки