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


Представление бинарных деревьев


Бинарные деревья достаточно просто могут быть представлены в виде списков или массивов. Списочное представление бинарных деревьев основано на элементах, соответствующих узлам дерева. Каждый элемент имеет поле данных и два поля указателей. Один указатель используется для связывания элемента с правым потомком, а другой v с левым. Листья имеют пустые указатели потомков. При таком способе представления дерева обязательно следует сохранять указатель на узел, являющийся корнем дерева.

Можно заметить, что такой способ представления имеет сходство с простыми линейными списками. И это сходство не случайно. На самом деле рассмотренный способ представления бинарного дерева является разновидностью мультисписка, образованного комбинацией множества линейных списков. Каждый линейный список объединяет узлы, входящие в путь от корня дерева к одному из листьев.

pic4_4.gif (3750 bytes)

Рис.4.4. Представление бинарного дерева в виде списковой структуры

Приведем пример программы, которая осуществляет создание и редактирование бинарного дерева, представленного в виде списковой структуры

program bin_tree_edit;

type node=record

name: string;

                left, right: pointer;

       end;

var

        n:integer;

        pnt_s,current_s,root: pointer;

        pnt,current:^node;

        s: string;

procedure node_search (pnt_s:pointer; var current_s:pointer);

{Поиск узла по содержимому}

var

         pnt_n:^node;

begin

pnt_n:=pnt_s; writeln(pnt_n^.name);

if not (pnt_n^.name=s) then

         begin

                if pnt_n^.left <> nil then

                           node_search (pnt_n^.left,current_s);




Начало  Назад  Вперед



Книжный магазин