мере, как программа может строить дерево. Предположи что нужно сформировать дерево, содержащее узлы типа, on! санного в (4.39), а значениями узлов будут п чисел, про^! тайных из входного файла. Для усложнения задачи потпр буем построить дерево с п узлами и минимальной высотой.

Чтобы достичь минимальной высоты при данном числр узлов, нужно располагать максимально возможное число уз. лов на всех уровнях, кроме самого нижнего. Это можно сде^ лать очень просто, если распределять все поступающие ysjjj

Рис. 4.22. Идеально сбалансированные деревья.

поровну слева и справа от каждого узла. В результате построенное дерево при данном п имеет вид, как показано на рис. 4.22 для п = 1, ..., 7.

Правило равномерного распределения при известном чиШе узлов п лучше всего формулируется с помощью рекурсии:

1. Взять один узел в качестве корня.

2. Построить левое поддерево с п1 = п div2 узлами тем способом.

3. Построить правое поддерево с пг = п - п1- 1 узлами тем же способом.

Это правило описано рекурсивной процедурой tree, вХО' дяшей в программу 4.3, которая читает входной файл и стро идеально сбалансированное дерево. Мы получаем такое опр^ деление:

gfam bwIdiree(inpUt,output);

node = record key: integer; .Ш left, right: ref

Щ end;

J,: integer; root: ref;

function /тф: integer)! ref;-------

yatnewnode: ref; X, til, nr: integer; legin [построение идеально сбалансированного дерева с п узлами]

if и = О then tree := nil else

hegin nl : n div 2; nr :~ n~nl-l;

tread(x); new{newiode); yiiiknewnode\ do begya key := x; left : iree(iil); right :=i treeQir) end ; tree := newnods end №d {tree} ;

jitoceumeprinttreeQ: .ref; h: integer);

Ш i: integer;-hgia [печать дерева t со сдвигом h]

t Ф nil then

with ft do

begin printtree($eft, Л+1);

ifor f I to h do mite{ ); writeln(key); printtree(righf, A+l) t d

e d {printtree} j

bgin [первое целое число есть число узлов} read(n);

root:~ iree(n);

printtree(root,0) М.

Программа 4.3. Построение идеально сбалансированного дерева.

Дерево идеально сбалансировано, если для каледого

его

узла количества узлов в левом и правом поддереве pg личаются не более чем на 1.

Предположим, например, что имеются следующие входнг, -данные для дерева с 21 узлом:

21 8 9 И 15 19 20 21 7 3 2 1 5 6 4 13 14 10 12 17 16 18

Тогда программа 4.3 строит идеально сбалансированное де. рево, показанное на рис. 4.23.

Рис. 423. Дерево, построенное с помощью программы 4.3.

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

Преимущество рекурсивного алгоритма особенно наглядно по сравнению с его нерекурсивной формулировкой. Читателю предлагается проявить свою изобретательность и написать нерекурсивную программу, строящую такие же деревья, прежде чем смотреть на (4.41). Эта программа приведена без дальнейших комментариев и может служить упражнением для читателя. Ему предлагается выяснить, как и почему о^ работает.