КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Удаление узла из дерева
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 пока не дошли до листа:
Дата добавления: 2014-01-06; Просмотров: 376; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |