Главная  Терминология Хоора 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 [ 77 ] 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133

1етим, что ее параметр р передается как параметр-пере-ен&ая, а не как параметр-значение. Это существенно, по-кольку в случае включения переменной должно присваи* аться некоторое новое значение ссылке, которая перед этим ямела значение nil. Для входной последовательности, состоящей из 21 числа, которая обрабатывалась с помощью про-rtiaMMbi 4.3, построившей дерево на рис. 4.23, программа 4.4 г r,opjj.o.g дерево поиска, показанное на рис. 4.27,


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

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

procedore search(x: integer; var p: ref); begin

if л: < p\.key tbe:nsearch(x,p\.left) else

Iif л; > p\.key then search{x,p\.right) else is. p Ф s then p].count := p\.count -f I else begin {вкдючение] new(p); with p\ do begin Arej ;= x; left :-s; right := s; count end end

(4.50)



program ireesearch(mput,output);

{поиск с включением по двоичному дереву]

type ref = [word;

word = record Arej*: integer;

count: integer; . left, right: ref;

end ;

var root: ref; k: integer;

procedure )n ree(w; ref; I: integer);

var /: integer; begin if w Ф. nil then withrit do begin prmttfeeXfeft,

for j := 1 to / do wife( y,

writeln(key);

printtree(right, l+l)

end ;

procedure scfl -c/j(x: integer; var p: ref); begin

if p = nil then

begin {слова нет в дереве; включить его] new (р); with р\ do

begin Агед := х; count := 1; left :- nil; right еН end end else

if л; < ptkey then search(x, p\.left) else if л: > pt.A:e>then5ecA-c(x, p\.right) else p\.count := p\.count + 1 end {secret} ;

begin fofl/ := nil; . .

while -leof (input) do

begin read(k); search(k, root) end ; printtree(root,0) end

Программа 4.4. Поиск с включениями.



Еще раз, теперь уже последний, построим альтернативную росию этой программы, отказавшись от использования ре-\рсии. Но сейчас избежать рекурсии не так просто, как случае без включения, так как для того, чтобы производить слючение, нужно помнить пройденный путь по крайней мере на один шаг назад. В программе 4.4 он запоминается автома-jjjqecKH при использовании параметра-переменной.

Чтобы праБйльно привязать включаемую компоненту, мы должны иметь ссылку на ее предка и знать, включается она g качестве правого или левого поддерева. Для этого вводятся две переменные: р2 и d (для направления):

procedure даа7с/г(х: integer; root: ref);

var pl,p2: ref; d: integer; begin p2 := root; pi := p2\.right; d := I; while {plnil) Л (dO) do begin p2 := pi;

if x < рЦ.кеу then

begin pi := pl\.Ieft; d := ~l end else if л: > рЦ.кеу then

begin p\ := p\\.right; d := 1 end else d:=0 end ;

ii d - 0 then pl.count : pll.count f I else begin [включение] new{pl); with рЦ do

begin/се; := л:; left := nil: right := nil; count := 1 end ;

if d < 0 then p2\.Ieft := pi else p2\.right := pi

(4.51)

Как и в случае поиска с включением по списку, используются две ссылки р1 и р2, такие, что в процессе поиска р2 всегда Указывает на предикат plf. Чтобы удовлетворить этому условию в начале поиска, вводится вспомогательный фиктивный Элемент, н-а который указывает root. Начало действительного Дерева поиска обозначается ссылкой rootf .right. Поэтому программа должна начинаться операторами

new{root); root\.right := nil

Вместо начального присваивания

ЙЬ.. root := nil




1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 [ 77 ] 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133