New(T);with T^ do Begin inf.slovo:=slovo; inf.count_sl:=1; L:=nil; R:=nil End End Else if slovo < T^.inf.slovo then Slovar(T^.L, slovo) Else if slovo > T^.inf.slovo then Slovar(T^.R, slovo) else T^.inf.count_sl:=T^.inf.count_sl+1 end; { Slovar } Упражнение 4.4. Описать нерекурсивную логическую функцию, проверяющую, входит ли заданный элемент в дерево поиска. Упражнение 4.5. Описать нерекурсивную процедуру или функцию подсчета числа вхождений заданного элемента в дерево поиска. 4.3 Исключение из дерева поиска Алгоритм исключения из упорядоченного дерева должен описывать три случая: 1) Узла с заданным значением в дереве нет. 2) Узел с заданным значением имеет не более одного потомка, т.е. удаляемый узел или терминальная вершина (лист), или вершина с одним 3) Узел с заданным значением имеет двух потомков. Трудности возникают в случае 3), так как удаляемый узел нужно заменить либо на самый правый узел его левого поддерева, либо на самый левый узел его правого поддерева, причем они должны иметь не более одного потомка. Пример 4.4. Описать процедуру исключения узла с заданным значением x из дерева поиска T. procedure Delete(var T: Tree; x: integer); var q: Tree; procedure Del(var p: Tree); Begin if p^.R <> nil then Del(p^.R) Else Begin q^.inf:=p^.inf; q:=p; p:=p^.L End end; { Del } Begin if T = nil then { элемента в дереве нет } Else if x < T^.inf then Delete(T^.L, x) Else if x > T^.inf then Delete(T^.R, x) Else begin { исключение узла T^ } q:=T; if q^.R = nil then T:=q^.L Else if q^.L = nil then T:=q^.R else Del(q^.L); { освобождение памяти, выделенной для размещения узла q^ }
|
