Учебное пособие Самара 2015 + 004. 43 Ббк 32. 973 Н 19

b

d

Pric. 10.9 — BsipomnéHHOé ne]3éBO

Hcnous3ys noncK yuga, MOWHO 3I1MéHHTs peKypcnBHyio npoue- pypy po6£tBJléHiis ysaa Ha HepeKypcnBHyio.

HepexypcHBHas npoueqypa uo6iIBJIéHHIl HOBoro ysna B Qé]3éBO
HH R3hIKé IICKIlJIh.

procedure addnode2(skey:integer; var tree:ptr; newdata:’info);

var
r,s:ptr;
t:’info; begin
if not search tree(skey,tree,r) then
begin
neW(b ); { *aHeCeHM e } t:=newdata; { QaHHLX } neW(S) ; { HOBbI/ }
s’.key:=skey;
s’.left:=nil; { ysex } s’.right:=nil; s’.data:=t;
if tree=nil then tree:=s else
if skeyr’.left:=s
else
r’.right:=s
end end;

129

4. 
   Удаление узла из дерева
   

Удаление узла из дерева — существенно более сложный про— цесс, чем поиск, так как удаляемый узел может быть корневым, левым или правым. Узел может давать начало ветвям (в двоич— ном дереве их может быть от 0 до двух).

Наиболее простым случаем является удаление терминально— го узла или узла, из которого выходит только одна ветвь. Для этого достаточно скорректировать соответствующий указатель у предшествующего узла.
Наиболее сложный случай удаление корневого узла под— дерева (или всего дерева) с двумя ветвями, поскольку приходится корректировать несколько указателей. Нужно найти подходящий узел, который можно было бы вставить на место удаляемого, причем этот подходящий узел должен просто перемещаться. Та— кой узел всегда существует. Это либо самый левый узел правой ветви, либо самый правый узел левой ветви.
Если это самый правый узел левой ветви, то для достижения этого узла нужно перейти в следующий от удаляемого узел по левой ветви, а затем переходить в очередные узлы только по пра- вой ветви до тех пор, пока очередной правый указатель не будет равен п i 1. Такой узел может иметь не более одной ветви. Ситуа- ции, возникающие при удалении узла из дерева, показаны на ри- сунке 10.10.

Рис. 10.10 — Удаление узла из дерева

130
HpiiMep ypauéHHII Hs pe]3eBa ysua C KJIIOuou SP.

100 100

20 120

15 50

30
33

P c. 10.11 — H]3iiMep ypaueHiis ysua no ne]3éBII

Hpouepypa ynauéHris yuga noJIWHII ]3asu UIITh TJ3ri cuyuas:

1. 
   ysaa c @£tHHhIM KJIIOUOM B Qé]3éBé HéT;
   
2. 
   ysen c sa@IIHHhIM KJIIOUOM HMééT He 6onee OQHO BéTBH
   

(p c. 10.10);

3. 
   ysen c saQ£tHHhIM KJIIOUOM HMééT QBé BéTBH ]3HG. 10.11).
   

Hpouepypa ypanéHii i ysna @BOHUHOFo pe]3éBlI His II3hIKé H IC-
KIIJIs (IIBTOp npouenypsI — Hnxuayc BH]3T).

procedure delnode(var d: ptr; key: integer); var q: ptr;

procedure del1(var r:ptr); (* xoxaxbHaS ecM O-

MOPaTeLbHaH M OQeQ/ a *)
begin
if r’.right = nil then
begin
q’.key := r’.key;
q’.data := r’.data; q r;
r := r’.left end
else
del1(r’.right)
end; (* KOHem iOKaebHO/ MpOqeQypB *)
131
begin (* Hawaxo OCHOBHO/ MpOqeQypb *)
if d = nil then exit (* Mepewh cxyuah *) else
if key < d’.key then
delnode(d’.left, key)
else
if key > d’.key then
delnode(d’.right, key) else
begin
q := d; (* BiopoH cxyuaH *) if q’.right = nil then
d := q’.left else
if q’.left = nil then
d := q’.right
else (* Tpeixu cxyuax *) del1(q’.left);
dispose(q) (* CodCTBeHHo yDaxeHxe *)
end
end;

BcHOMOFIITëJIhHas pexypcHBHas npouenypa de 11 BhI3hIBtlëTCR TOJII›KO B T]3ëTI›ëM cnyuae. ÖHa npoxoaiiT ,Që)3ëBO QO CIIMOFO H]3iIBOFO ysna JIëBOFo noppe]3öBI1, HIIUHHas c ypauseMoro ysna q , ri 3IIMëHRëT 3HI1UëHHIl nomen ke y ii de L a B q coOTBëTcTByio riMH 3an cflMH nomen ysna r . Hocnë 3Toro ysen, HU KOTO]3sIii yKasbIBaeT r MomHO eCKeMmHT6(r := r’.left)

AHi1JI€1FHUHI›Ie QyHKuHH Hit II3hIKé liii‘.

void dell(node*& r, node*& q) if (r->right == NULL)

q->key = r->key; // MepeHOC QaHHbX
q->data = r->data; q r;
r = r->left;

else

132
del1(r— >right, q);

void del node(node*& d, int key) node* q;

if (d == NULL)
return; else
if (key < d— >key)
del node(d — >left, key); else
if (key > d->key)
del node(d->right, key); else

q d;
if (q->right == NULL) d = q->left;

else
if (q->left == NULL)
d = q->right;
else
del1(q->left, q);
delete q; // YLaxeHxe

5.