Структуры данных. Деревья - 20 стр.

UptoLike

ВУЗ: 

ЮФУ | Ростов-на-Дону

Составители: 

Рубрика: 

22
4.1 Построение дерева поиска
Алгоритм создания дерева поиска основан на следующих правилах :
Если новый элемент меньше, чем значение в узле, то он должен добавлять-
ся в левое поддерево, если больше, то в правое.
Если в дереве есть узел с таким значением, то возможны варианты :
а) новый узел добавляется в правое поддерево
,
б) новый узел добавляется в левое поддерево,
в) добавление не происходит.
Инфиксный обход такого дерева дает упорядоченную по возрастанию
(неубыванию в случае добавления одинаковых элементов ) последовательность.
Пример 4.1. Упорядочить по неубыванию последовательность целых чи-
сел, которая вводится из текстового файла.
program UP;
type Tree = ^Node;
Node = record
inf : integer;
L,R : Tree
end;
var x : integer; Root : Tree;
F : text; imf : string;
{ процедура добавления значения x в дерево поиска
T }
procedure InTree(var T : Tree; x : integer);
var flag : boolean;
p,n : Tree; { указатели на текущий и новый элементы }
begin
new(n); n^.inf:=x; { создание нового узла }
n^.L:=nil; n^.R:=nil;

Страницы