Удаление узла из дерева
End.
End
Begin
Then
Begin
Begin
Begin
Begin
Begin
Repeat
Begin
Конец поиска
Такого числа нет
Такое число есть
Найдено чисел: 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; процедура формирования бинарного дерева
New(root);
Write('Первое число: ');
ReadLn(root^.Data); первое число - в корень дерева
root^.Left:=Nil;
root^.Right:=Nil;
Write('Очередное число: ');
New(v);
ReadLn(v^.Data);
If (v^.Data = 0) если очередное число - ноль,
Then Break; то выходим из цикла ввода
v^.Left:=Nil;
v^.Right:=Nil;
q:=Root; поисковик - в корень дерева
While (q <> Nil) Do пока не добрались до листа:
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); процедура просмотра дерева
If (base <> Nil) Then
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 пока не добрались до листа:
If (q^.Data = poisk) Then если значение найдено:
flag:=1;
n:=n+1; количество найденных одинаковых значений
End;
If (poisk < q^.Data) спускаемся на следующий узел
Then q:=q^.Left
Else q:=q^.Right;
End; {While} дошли до листа
If (flag = 1)
WriteLn(‘Такое число есть’);
WriteLn(‘Найдено чисел: ’, n);
Else WriteLn(‘Такого числа нет’);
Until (False); конец цикла поиска
ReadLn;
Задача удаления узла в сформированном дереве решается в следующем порядке:
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 пока не дошли до листа: