I buildtree(inputyOutput);

ref = t fe;

= record ЛеД': integer; left, right: ref end ;

ar i,n,nli,x: integer;

root,P,q,r.dmy: ref;

s: array [1 30] of [стек] record n: integer; rf: ref end ;

iiegin [первое целое число есть число узлов]

read(n); new(root); new[dmy); [фиктивный элемент] ; := 1; s[\].n := и; л[1].г/:= roof; (4.41)

repeat и := лр] .и; г := jp] .г/; i :=: j-I; [из стека] if я =0 then rl.right := nil else begin := dm;;

repeat nl :== л div 2; и/* :=;: n-nl-l;

read(x); newiq); q\.key := x; / := г+1; := иг; ; {e c/M/f

и nl; p\.left q; p :~ q until Й = 0;

q\.left := nil; r.right := dmy\.left

end until / = 0; printtree {root\.right,0)

Основные операции с бинарными деревьями

Имеется много задач, которые можно выполнять на древо-№дной структуре; распространенная задача - выполнение йданной операции Р с каждым элементом дерева. Здесь Р рассматривается как параметр более общей задачи посеще- ия всех узлов, или, как это обычно называют, обхода дерева.

Если рассматривать эту задачу как единый последова- ьный процесс, то отдельные узлы посещаются в некотором

Ределенном порядке и могут считаться расположенными .Нейно. В самом деле, описание многих алгоритмов суще-енно упрощается, если можно говорить о переходе к сле-

УЮщему элементу дерева, имея в виду некоторое упоря- Чение.

УЩествуют три принципа упорядочения, которые есте-JSjHo вытекают из структуры деревьев. Так же как и саму.

Древовидную структуру, их удобно выразить с помощью

курсии. Обращаясь к бинарному дереву на рис. 4.24, где обозначает корень, а Л и В - левое и правое поддеревья, ы можем определить такие три упорядочения:

1. Сверху вниз: R, А, В (посетить корень до поддеревьев^

2. Слева направо: А, R, В *

3. Снизу вверх: А, В, R (посетить корень после подд, ревьев)

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

1. Сверху вниз: -\-а/Ъс - d*e/

2. Слевагнаприио:-а.-\- b/c*d -f

3. Снизу вверх: abc/-\-def -

Мы узнаем три формы записи выражений: обход сверху вниз дает префиксную запись, обход снизу вверх - постфикс-

А А

Рис. 4.24. Бинарное дерево.

ную запись, а обход слева направо дает привычную инфикс-ную запись, хотя и без скобок, необходимых для определения порядка выполнения операций.

Теперь выразим эти три метода обхода как три конкретные программы с явным параметром /, означающим дерево, с которым они имеют дело, и неявным параметром Р, означающим операцию, которую нужно выполнить с каждым У^ лом. Введем следующие определения:

type ref = pode

node ~ record,J . (4.45)

left,rig fit: ref

Эти три метода легко сформулировать в виде рекурсИБИ^ процедур; они вновь служат примером того, что действ

ИВекурсивно определенными структурами данных лучше описываются рекурсивными алгоритмами,

jftoceumepreorder(t: ref); begia iS t Ф ml thea begin P(0;

preorderQ.lefi); (4.43)

И---- preorder\t\.right) ...

m end

procedurepostorder(t: ref); Вч. begin iif nil then

B begin posforder(t\.teft) l

posforder(t\.right)} (4.44)

procedure inorder{f: ref); begin if f nil then

begin inorder(t\Jeft);

P{t); (4.45)

inorder(t\.right)

end end

Отметим, что ссылка / передается как параметр-значение. Это отражает тот факт, что здесь существенна сама ссылка (указание) на рассматриваемое поддерево, а не переменная, значение которой есть эта ссылка и которая могла бы изменить значение, если бы t передавался как параметр-пере-ченная.

Пример подпрограммы, осуществляющей обход дерева, - fo подпрограмма печати дерева с соответствующим сдвигом, выделяющим каждый уровень узлов (см. программу 4.3).

Бинарные деревья часто используются для представления Ножеств данных, элементы которых ищутся по уникальному, олько им присущему ключу. Если дерево организовано таким разом, что для каждого узла ti все ключи в левом подде-le Меньше ключа ti, а ключи в правом поддереве больше jj%a ti, то это дерево называется деревом поиска. В дереве иска можно найти место каждого ключа, двигаясь начиная Lорня и переходя на левое или правое поддерево каждого в зависимости от значения его ключа. Как мы видели