Сортировка с использованием бинарного дерева.

20.2.3. Сортировка с использованием бинарного дерева.

Сортировка с использованием дерева выполняется по очень простой процедуре: элемент помещается справа от текущего, если он больше и слева, если он меньше. Обход в сортированном порядке выполняется следующим образом: поддерево слева, вершина, поддерево справа.

INPUT: CBDA

PROGRAM TreeSort(INPUT, OUTPUT);

TYPE

Tree = ^NodeType;

NodeType = RECORD

Ch: CHAR

LLink, RLink: Tree;

END;

VAR

Root: Tree;

Ch: CHAR;

BEGIN {TreeSort}

Root := NIL;

WHILE NOT EOLN

DEGIN

READ(Ch);

Insert(Root, Ch)

END;

PrintTree(Root)

END. {TreeSort}

PROCEDURE Insert(VAR Ptr:Tree, Data: CHAR);

BEGIN {Insert}

IF Ptr = NIL

THEN

BEGIN {Создаем лист со значением Data}

NEW(Ptr);

Ptr^.Key := Data;

Ptr^.LLink := NIL;

Ptr^.RLink := NIL;

END

ELSE

IF Ptr^.Ch > Data

THEN

Insert(Ptr.LLink, Data)

ELSE

Insert(Ptr.RLink. Data)

END; {Insert}

PROCEDURE PrintTree(Ptr: Tree);

BEGIN {PrintTree}

IF Ptr <> NIL

THEN {Печатает поддерево слева, вершину, поддерево справа}

BEGIN

PrintTree(Ptr^.LLink);

WRITE(Ch);

PrintTree(Ptr^.RLink);

END;

WRITELN

END; {PrintTree}

⇐ Предыдущая 1 2 34