Поиск заданного узла в дереве

Задача поиска заданного узла в сформированном дереве сводится к сравнению искомого числа с информационными частями очередных узлов дерева. Добавим в описание переменных предыдущей программы три переменные:

Var poisk: Integer; искомое число

flag: 0..1; флаг поиска; flag=1 – число найдено

n: Word; количество найденных одинаковых чисел

Искомые числа вводить циклом до ввода 0 – конец поиска:

Что искать: 20

Такое число есть

Найдено чисел: 1

Что искать: 50

Такого числа нет

.........

Что искать: 0

Конец поиска

Программа:

Program Bi_Tree;

Uses WinCRT;

Type TRebro = ^TUzel;

TUzel = Record

Data: Integer;

Left, Right: Rebro;

End;

Var root, q, v: TRebro;

poisk: Integer; искомое число

flag: 0..1; флаг поиска

n: Word; количество найденных одинаковых чисел

Procedure Formir_Tree; процедура формирования бинарного дерева

Begin

New(root);

Write('Первое число: ');

ReadLn(root^.Data); первое число - в корень дерева

root^.Left:=Nil;

root^.Right:=Nil;

Repeat

Write('Очередное число: ');

New(v);

ReadLn(v^.Data);

If (v^.Data = 0) если очередное число - ноль,

Then Break; то выходим из цикла ввода

v^.Left:=Nil;

v^.Right:=Nil;

q:=Root; поисковик - в корень дерева

While (q <> Nil) Do пока не добрались до листа:

Begin

If (v^.Data < q^.Data) если введенное число меньшечисла в очередном узле

Then If (q^.Left <> Nil) и левая ссылка узла не пуста,

Then q:=q^.Left то делаем шаг влево,

Else иначе

Begin если левая ссылка узла пуста,

q^.Left:=v; то подвешиваем туда очередноечисло

Break; и выходим из цикла поиска

End;

If (v^.Data >= q^.Data) если введенное число больше илиравночислу в очередном узле

Then If (q^.Right <> Nil) и правая ссылка узла непуста,

Then q:=q^.Right то делаем шаг вправо,

Else иначе

Begin если правая ссылка узла пуста,

q^.Right:=v; то подвешиваем туда очередное число

Break; и выходим из цикла поиска

End;

End; {While}

Until (False);

End; конец процедуры формирования дерева

Procedure Order(base: TRebro); процедура просмотра дерева

Begin

If (base <> Nil) Then

Begin

Order(base^.Left);

Write(base^.Data:5);

Order(base^.Right);

End;

End; конецпроцедуры просмотра дерева

Begin основная программа

ClrScr;

Formir_Tree; обращение к процедуре формирования дерева

WriteLn;

Writeln('Отсортированная последовательность: ');

Order(root); обращение кпроцедуре просмотра дерева

WriteLn;

Repeat начало цикла поиска

Write(‘Что искать: ’);

ReadLn(poisk); ввод искомого числа

If (poisk = 0) если ввели 0,

Then Break; то выходим из цикла поиска

q:=root; поисковик – в корень дерева

flag:=0; еще ничего не найдено

n:=0; ни одного значения не найдено

While (q <> Nil) Do пока не добрались до листа:

Begin

If (q^.Data = poisk) Then еслизначение найдено:

Begin

flag:=1;

n:=n+1; количество найденных одинаковых значений

End;

If (poisk < q^.Data) спускаемся на следующий узел

Then q:=q^.Left

Else q:=q^.Right;

End; {While} дошли до листа

If (flag = 1)

Then

Begin

WriteLn(‘Такое число есть’);

WriteLn(‘Найдено чисел: ’, n);

End

Else WriteLn(‘Такого числа нет’);

Until (False); конец цикла поиска

ReadLn;

End.

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

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

1. поиск удаляемого узла

2. анализ найденного узла

Поиск удаляемого узла осуществим с помощью двух переменных-указателей: q – поискового, указывающего на найденный узел, и v, отстающего от него на уровень и всегда указывающего на корень удаляемого узла:

Var root, q, v, r: TRebro;

poisk: Integer; искомое число (узел)

flag: 0..1; флаг поиска: 1 – узел найден, 0 – не найден

Методика удаления узла будет зависеть от того, какого типа этот узел:

a. лист

b. узел с одним поддеревом,

c. узел с двумя поддеревьями.

Добавим в нашу программу процедуру удаления заданного узла. Сначала найдем заданный узел - на него будет указывать ссылка q:

Write(‘Что удалить: ’);

ReadLn(poisk); ввод удаляемого узла

If (poisk = 0) если это 0,

Then Break; то выходим из циклаудаления

q:= root; поисковик q – в корень дерева

v:= q; v отстает на шаг

flag:= 0; еще ничего не найдено

While (q <> nil) Do пока не дошли до листа:

Begin

If (q^.Data = poisk) Then если нашли удаляемый узел:

Begin

flag:= 1; флаг поиска – на 1

Break; и выходим из цикла поиска

End; {If}

v:=q; если еще не нашли: подтянули ссылку v к поисковику q

If (poisk < q^.Data) и сделали шаг по дереву на уровень ниже

Then q:=q^.Left

Else q:=q^.Right;

End; {While}

Если удаляемый узел найден (flag=1), то начинается его анализ:

1. если это лист – то безболезненно его удаляем (q – указатель на удаляемый узел, v – указатель на его предка):

 

 

If (q^.Left = Nil) And (q^.Right = Nil) Then это лист

Begin

If (v^.Left = q) если он подвешен слева от предка,

Then v^.Left:=Nil то вместо него Nil,

Else v^.Right:=Nil; иначе Nil - справа от предка

Dispose(q); освобождаем от него память

{на продолжение}

End;

2. если у него слева – ничего нет, а справа - поддерево:

 

 

If (q^.Left = Nil) And (q^.Right <> Nil) Then

Begin

If (v^.Left = q) если он подвешен слева от предка,

Then v^.Left:=q^.Right то слева вместо него - правое поддерево узла q,

Else v^.Right:=q^.Right; иначе справа вместо него - правое поддерево узла q

Dispose(q); освобождаем от него память

{на продолжение}

End;

3. если у него справа – ничего нет, а слева - поддерево:

 

 

If (q^.Right = Nil) And (q^.Left <> Nil) Then

Begin

If (v^.Left = q) если он подвешен слева от предка,

Then v^.Left:=q^.Left то слева вместо него - левое поддерево узла q,

Else v^.Right:=q^.Left; иначе справа вместо него - левое поддерево узла q

Dispose(q); освобождаем от него память

{на продолжение}

End;

4. если у него и слева и справа – поддеревья. В этом случае нужно:

· сделать шаг влево и идти до конца все время направо или

· сделать шаг вправо и идти до конца все время налево.

q – ссылка на удаляемый узел,

r – ссылка на узел, который поставим на место удаляемого,

v – ссылка на предка узла r.

Найденным узлом r заменим удаляемый узел q:

 

 

If (q^.Right <> Nil) And (q^.Left <> Nil) Then

Begin

v:=q; подтягиваем указатель v к q

r:=q^.Right; ссылкой r делаем шаг вправо

от удаляемого узла

While (r^.Left <> Nil) Do идем все время налево до конца

Begin

v:=r; подтягиваем указатель v к r

r:=r^.Left; и делаем по дереву шаг влево

End; {While}

q^.Data:=r^.Data; помещаем вместо удаляемого узла q найденный самый левый на этом пути,

If (r^.Right = Nil)

Then v^.Left:=Nil а вместо него подвешиваем Nil

Else v^.Left:=r^.Right; или его правое поддерево

Dispose(r); освобождаем память от найденного узла

End;