(* Напоминание. *) (* Двоичное дерево (Бинарное дерево) - дерево, в котором *) (* каждая вершина имеет 0, 1 или 2 непосредственных потомков. *) (* Конец напоминания. *) |
(* Подход к представлению деревьев на языке Паскаль: *) (* -1- вершина - запись в динамической памяти; *) (* -2- ребро (a,b) - в записи вершины a есть поле, *) (* содержащее указатель на запись b. *) |
(* Соглашение. *) (* С каждой вершиной дерева связана информация (ключ), *) (* однозначно идентифицирующая эту вершину. *) (* Ключи должны допускать сравнения на больше-меньше-равно. *) (* В Паскале ключами могут быть: integer, char, строки, real *) (* (с оговорками) и др. *) (* Считаем, что ключ имеет целый тип (integer). *) type info = record (* заглушка *) end; pRecord = ^info; pDoTree = ^DoTree; DoTree = record Key : integer; (* ключ *) Left : pDoTree; (* указатель на левое поддерево *) Right : pDoTree; (* указатель на правое поддерево *) REFF : pRecord; (* ассоциированная информация *) end; |
(* NB. В связи с выбранной реализацией вершин появляется *) (* понятия правого и левого поддеревьев (каждой) вершины. *) (* *) (* Пусть R : DoTree - вершина бинарного дерева. *) (* R - лист, если R.Left = nil, R.Right = nil; *) (* R имеет одного (левого) непосредственного потомка, *) (* если R.Left <> nil, R.Right = nil; *) (* R имеет одного (правого) непосредственного потомка, *) (* если R.Left = nil, R.Right <> nil; *) (* R имеет двух непосредственных потомков, *) (* если R.Left <> nil, R.Right <> nil; *) (* *) (* Обозначим: *) (* LK(R) - множество ключей, встречающихся в левом поддереве R *) (* RK(R) - множество ключей, встречающихся в правом поддереве R *) |
(* Дерево поиска - бинарное дерево, для каждой вершины которого *) (* справедливо: x < R.Key < y, *) (* для всех x из LK(R) и для всех y из RK(R). *) (* *) (* Основные операции: *) (* -1- поиск вершины по известному ключу; Find *) (* -2- включить в дерево вершину с заданным ключом. Form *) (* -3- исключить из дерева вершину с заданным ключом; Kill *) (* *) (* ///////////////////////// Пусть //////////////////////////// *) program ...; Type info = record (* заглушка *) end; pRecord = ^info; pDoTree = ^DoTree; DoTree = record Key : integer; (* ключ *) Left : pDoTree; (* указатель на левое поддерево *) Right : pDoTree; (* указатель на правое поддерево *) REFF : pRecord; (* ассоциированная информация *) end; ... Var T : pDotree; (* Дерево *) ... ... begin T:=nil; (* Сначала дерева нет *) ... end. |
(* Find : поиск в дереве вершины с ключом K. *) (* Find(T,K) = nil, если такой вершины в дереве нет, *) (* иначе Find(T,K) = ссылка на вершину с ключом K. *) function Find(X : pDoTree; K : integer) : pDoTree; begin if X = nil then Find:=nil else with X^ do if Key = K then Find:=X else if Key < K then Find:=Find(Right,K) else Find:=Find(Left ,K) end; (* Findm : поиск в дереве вершины с ключом K. Упрощенная версия. *) function Findm(X : pDoTree; K : integer) : pDoTree; begin Findm:=X; (* D = nil / K = Key *) if X <> nil then with X^ do if Key < K then Findm:=Findm(Right,K) else if K < Key then Findm:=Findm(Left ,K) end; |
(* Form : включить в дерево T (новую) вершину с ключом K. *) (* Form(T,K) = указатель на существующую или *) (* вновь созданную вершину с ключом K. *) (* Во вновь созданной вершине REFF = nil. *) function Form(var D : pDotree; K : integer) : pDoTree; begin if D = nil then begin new(D); (* Построить новую вершину *) D^.Key :=K; D^.Reff :=nil; D^.Left :=nil; D^.Right:=nil; Form:=D end; with D^ do if Key = K then Form:=D else if Key < K then Form:=Form(Right,K) else Form:=Form(Left ,K) end; |
(* Kill : удалить в дереве поиска вершину с ключом K. *) (* *) (* Подход: Если в дереве найдется вершина с ключом K, *) (* то (из общих соображений) возможны 4 различных, *) (* случая каждый из которых обрабатывается отдельно. *) procedure Kill(var D : pDoTree; K : integer); var Q : pDoTree; procedure Case41; begin Q^.Key :=D^.Left^.Key; Q^.Reff:=D^.Left^.Reff; Q:=D^.Left; D^.Left:=D^.Left^.Left end; procedure Ki(var D : pDotree); begin with D^ do if Right <> nil then Ki(Right) else begin Q^.Key :=D^.Key; Q^.Reff:=D^.Reff; Q:=D; D:=D^.Left end end; begin if D = nil then Exit; with D^ do if Key < K then Kill(Right,K) else if Key > K then Kill(Left ,K) else begin Q:=D; if Q^.Reff <> nil then Dispose(Q^.Reff); if (Left = nil) and (Right = nil) then D:=nil (* 3 *) else if Left = nil then D:=Right (* 1 *) else if Right = nil then D:=Left (* 2 *) else if Left^.Right = nil then Case41 (* 4.1 *) else Ki(Left); (* 4.2 *) Dispose(Q) end end; |
(* Упрощения *) (* 1. Случай 3: if (Left = nil) and (Right = nil) then D:=nil *) (* покрывается: if Left = nil then D:=Right при Right = nil *) (* Поэтому отдельно случай 3 можно не рассматривать *) (* *) (* 2. Процедура Case41 повторяет операторы из процедуры Ki *) (* для случая D есть D^.Left *) (* Введем в процедуре параметр и получим: *) procedure Kill(var D : pDoTree; K : integer); var Q : pDoTree; procedure Case41(var D : pDoTree); begin Q^.Key :=D^.Key; Q^.Reff:=D^.Reff; Q:=D; D:=D^.Left end; procedure Ki(var D : pDotree); begin if D^.Right <> nil then Ki(D^.Right) else Case41(D) end; begin if D = nil then Exit; with D^ do if Key < K then Kill(Right,K) else if Key > K then Kill(Left ,K) else begin Q:=D; if Q^.Reff <> nil then Dispose(Q^.Reff); if Left = nil then D:=Right (* 1 *) else if Right = nil then D:=Left (* 2 *) else if Left^.Right = nil then Case41(Left) (* 4.1 *) else Ki(Left); (* 4.2 *) Dispose(Q) end end; |
(* Упрощения *) (* 3. Случай 4.1: if Left^.Right = nil then Case41(Left) *) (* эквивалентен: if Left^.Right = nil then Ki(Left) *) (* Поэтому случаи 4.1 и 4.2 можно объединить. *) (* Получим: *) procedure Kill(var D : pDoTree; K : integer); var Q : pDoTree; procedure Case41(var D : pDoTree); begin Q^.Key :=D^.Key; Q^.Reff:=D^.Reff; Q:=D; D:=D^.Left end; procedure Ki(var D : pDotree); begin if D^.Right <> nil then Ki(D^.Right) else Case41(D) end; begin if D = nil then Exit; with D^ do if Key < K then Kill(Right,K) else if Key > K then Kill(Left ,K) else begin Q:=D; if Q^.Reff <> nil then Dispose(Q^.Reff); if Left = nil then D:=Right (* 1 *) else if Right = nil then D:=Left (* 2 *) else Ki(Left); (* 4 *) Dispose(Q) end end; |
(* Упрощения *) (* 4. Объединим процедуры Case41 и Ki. *) (* Окончательно получим: *) procedure Kill(var D : pDoTree; K : integer); var Q : pDoTree; procedure Ki(var D : pDotree); begin if D^.Right <> nil then Ki(D^.Right) else begin Q^.Key :=D^.Key; Q^.Reff:=D^.Reff; Q:=D; D:=D^.Left end end; begin if D = nil then Exit; with D^ do if Key < K then Kill(Right,K) else if Key > K then Kill(Left ,K) else begin Q:=D; if Q^.Reff <> nil then Dispose(Q^.Reff); if Left = nil then D:=Right (* 1 *) else if Right = nil then D:=Left (* 2 *) else Ki(Left); (* 4 *) Dispose(Q) end end; |
(* Соглашение о скобочной записи бинарных деревьев поиска *) (* Дерево c корнем A и ключом nn (= A^.Key ) *) (* - обозначается Tnn, если A^.Left = nil и A^.Right = nil *) (* - обозначается (Tnn nil Правое-Поддерево), если A^.Left = nil *) (* - обозначается (Tnn Левое-Поддерево nil) , если A^.Rigth = nil *) (* - обозначается (Tnn Левое-Поддерево Правое-Поддерево), *) (* если A^.Left <> nil A^.Rigth <> nil *) (* Примеры: T20 *) (* (T25 T9 nil) *) (* (T22 (T11 T5 nil) T30) *) (* (T30 (T10 (T7 T2 T8) (T15 T11 nil)) (T40 T33 T69)) *) |
(* Факультативно. *) (* List : Ввести на печать дерево X в скобочном виде. *) procedure List(X : pDoTree); begin if X = nil then write('nil') else with X^ do if (Left = nil) and (Right = nil) then write('T',Key) else begin write('(T',Key,' '); List(Left); write( ' '); List(Right); write(')') end end; (* Конец факультативного примера. *) |
(* Факультативно. *) (* BT : функция проверки бинарных деревьев на *) (* принадлежность классу деревьев поиска. *) (* BT(X) = true , если X - дерево поиска. *) (* Подход. Использовать определение. *) (* Множества LK и RK достаточно представлять их *) (* максимальными и минимальными элементами: *) (* Lmin, Lmax и Rmin, Rmax соответственно. *) (* Тогда в дереве поиска R: *) (* -1- выполняется: Lmax < R.Key < Rmin *) (* -2- представлены ключи из диапазона [Lmin,Rmax]. *) (* BTW - вспомогательная функция: BTW(X,Kmin,Kmax) = true, *) (* если X - непустое дерево поиска; при этом *) (* Kmin и Kmax - значения максимального *) (* и минимального ключей в дереве X. *) function BTW(X : pDoTree; var Kmin,Kmax : integer) : boolean; var Lmin,Lmax,Rmin,Rmax : integer; begin BTW:=true; (* оптимистический подход *) with X^ do begin (* NB. D <> nil *) if Left = nil then Kmin:=Key else if not BTW(Left ,Lmin,Lmax) then BTW:=false else if Lmax < Key then Kmin:=Lmin else BTW:=false; if Right = nil then Kmax:=Key else if not BTW(Right,Rmin,Rmax) then BTW:=false else if Key < Rmin then Kmax:=Rmax else BTW:=false end end; function BT(X : pDoTree) : boolean; var Tmin,Tmax : integer; begin if X = nil then BT:=true else BT:=BTW(X,Tmin,Tmax) end; (* Конец факультативного примера *) |
(* Факультативно. *) (* BTrees : Программа построения и модификации дерева поиска. *) (* Реализация в виде пригодном для использования в Интернет; *) (* метод задания параметров - POST. >> pasweb.htm *) (* перем.T : указатель на корень дерева. *) (* Первоначально T = nil *) (* Программа получает от пользователя последовательность *) (* целых чисел ISQ[1..N] и обрабатывает ее по следующим *) (* правилам (K = ISQ[I]) : *) (* Если 0 < K <= 999 , то включть в T вершину с ключом K. Form *) (* Если K = 0 , то проверить корректность T. BT *) (* Если -999 <= K < 0, то удалить в T вершину с ключом abs(K). Kill *) (* Если 1000 <= abs(K), то найти в T вершину с ключом Find *) (* abs(K) mod 1000. *) program BTrees; (* Структура программы. Полный текст >> btrees.htm *) const MSQ = 200; type info = record inf : integer end; (* Для определенности *) pRecord = ^info; pDoTree = ^DoTree; DoTree = record Key : integer; (* ключ *) Left : pDoTree; (* указатель на левое поддерево *) Right : pDoTree; (* указатель на правое поддерево *) REFF : pRecord; (* ассоциированная информация *) end; var ISQ : array [1..MSQ] of integer; I,K,N : integer; V,T : pDoTree; (* Дерево *) (* IntSeq - ввод последовательности *) procedure IntSeq(var N : integer); (* целых чисел ISQ[1..N] *) begin end; (* Find : поиск в дереве *) function Find( X:pDoTree;K:integer):pDoTree; (* вершины с ключом K *) begin end; (* Form : включить в дерево D *) function Form(var D:pDoTree;K:integer):pDoTree; (* (новую) вершину с ключом K *) begin end; (* Kill : удалить в дереве D *) procedure Kill(var D:pDoTree;K:integer); (* вершину с ключом K *) begin end; (* BT : функция проверки *) function BT( X:pDoTree ):boolean; (* бинарных деревьев *) begin end; (* List : Ввести на печать дерево D *) procedure List( X:pDoTree); (* в скобочном виде *) begin end; begin T:=nil; IntSeq(N); writeln('Content_type: text/html'); (* <== Обязательно *) writeln; (* <== Обязательно *) writeln('<html><pre>'); writeln(' ':17,'*** Программа BTrees ***'); writeln; write('ISQ[1..':10,N:3,'] = '); for I:=1 to N do write(ISQ[I],' '); writeln; writeln('Начало. T = nil':20); writeln; for I:=1 to N do begin K:=ISQ[I]; if K = 0 then write('BT(T)= ':17,BT(T)) else if 1000 <= abs(K) then begin K:=abs(K) mod 1000; write('Find(T,',K:3,') = '); List(Find(T,K)) end else if 0 < K then begin write('Form(T,',K:3,'); T = '); V:=Form(T,K); with V^ do if REFF = nil then begin new(REFF); REFF^.Inf:=I end; List(T) end else (* K < 0 *) begin K:=abs(K); write('Kill(T,',K:3,'); T = '); Kill(],K); List(T) end; writeln; end; writeln; write('Результат. T = ':17); List(T); writeln; writeln; writeln('Конец.</pre></html>'); end. (* Конец факультативного примера *) |