30. Деревья. Основные понятия и определения. Поиск, добавление и удаление узла. Рекурсивные алгоритмы.

• Опишем дерево как указатель на узел следующим образом:

  • type Link = ^Node;

  • Node = record

  • elem: Tbase;

  • left, right: Link

  • end;

• Узел состоит из трех полей:

  • в поле elem хранится элемент (некоторое значение, числовое, строковое, запись и т.п.),

поля left и right хранят ссылки на левое и правое поддеревья, соответственно.

Поиск по дереву:

• Procedure Search(x: integer; var T: Link);

• begin

• if T = nil then

• begin

• new(T); T^.elem:=x;

• T^.left:=nil;T^.right:=nil;

• end

• else

• if x<T^.elem then search(x, T^.left)

• else if x>T^.elem then search(x, T^.right);

• end;

Удаление элемента:

• procedure Delete(x: integer;var T:Link);

• var P:Link;

• procedure Del(var R: Link);

• begin

• if R^.right <> nil

• then del(R^.right)

• else begin

• P:=R; R:=R^.left

• end;

• end;