Форум программистов, компьютерный форум, киберфорум
Наши страницы
Delphi для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.71/7: Рейтинг темы: голосов - 7, средняя оценка - 4.71
xq
0 / 0 / 0
Регистрация: 14.09.2014
Сообщений: 321
#1

Выполнить симметричную прошивку бинарного дерева поиска

02.06.2015, 19:39. Просмотров 1204. Ответов 5
Метки нет (Все метки)

Выполнить симметричную прошивку бинарного дерева поиска. Обойти его согласно симметричному порядку следования элементов.
У меня есть часть кода для этого,но не знаю как это все сделать в работающем виде.


Delphi
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
Узел прошитого бинарного дерева имеет иную структуру
 
     Type ptr = ^node;        
   node = record    
    info : integer; {Информационное поле}
    ltag, rtag : boolean; {Тэги прошивочных нитей}
           left, right : pt;  {Указатели на левое и правое поддеревья}
end;
 
Логические поля в прошитом дереве могут принимать следующие значения.
1.  ltag=true, следовательно, left представляет собой обычную связь.
2.  ltag=false, следовательно, left указывает на узел-предшественник.
3.  rtag=true, следовательно, right  представляет собой обычную связь.
4.  rtag=false, следовательно, right указывает на узел-преемник.
 
 
Программный код процедур симметричного обхода sim_print и прошивки правых связей rightsew будет выглядеть так:
 
procedure sim_print(var x:pt);
       procedure rightsew( var p:pt);
         begin
            if y <> nil then
               begin
                  if y^.right=nil then
                    begin
                        y^.rtag := false;
                        y^.right := p;
                  end
               else    y^.rtag := true;
            end;
           y:=p;
        end;
    begin
      if  x<> nil then
        begin
        sim_print(x^.left);
        rightsew(x);
        sim_print(x^.right);
     end;
 
1.  Переход к корню дерева ( p := HEAD^.left ). 
2.  До тех пор, пока p^.left<>nil, повторять: p := p^.left,  то есть идти по левой ветви до самого левого узла. 
3.  Обработка узла p, например, печать p^.info. 
4.  Если p^.rtag равен false, то p := p^.right  и переход к шагу 3 ( к преемнику). Иначе p:= p^.right  и переход к шагу 2. 
Алгоритм заканчивает работу, когда p станет равным HEAD.
Добавлено через 15 часов 10 минут
Хелп

Добавлено через 7 часов 3 минуты
апп
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.06.2015, 19:39
Ответы с готовыми решениями:

Сортировка бинарного дерева
Помогите, пожалуйста, с задачей. Создать сбалансированное бинарное дерево....

Копирование заданного бинарного дерева
Составить программу копирования заданного бинарного дерева в бинарное дерево

Формирование бинарного дерева по скобочной записи
Я думаю тема не раз поднималась, но толкового ничего не нарыл. Суть задачи...

Ошибка в коде создания бинарного дерева
Написала программу для создания бинарного дерева. Ничего необычного, однако...

Поиск минимальной глубины бинарного дерева
Всем доброго времени суток! Помогите пожалуйста найти минимальную глубину...

5
xq
0 / 0 / 0
Регистрация: 14.09.2014
Сообщений: 321
03.06.2015, 21:49  [ТС] #2
Помогите пожалуйста :/
0
xq
0 / 0 / 0
Регистрация: 14.09.2014
Сообщений: 321
04.06.2015, 22:56  [ТС] #3
апп
0
northener
05.06.2015, 00:36
  #4

Не по теме:

Может кто подскажет, что понимается под прошивкой бинарного дерева?
Мне уж скоро на пенсию, а я до сих пор этого не знаю! :)

0
xq
0 / 0 / 0
Регистрация: 14.09.2014
Сообщений: 321
05.06.2015, 20:19  [ТС] #5
Цитата Сообщение от northener Посмотреть сообщение
Может кто подскажет, что понимается под прошивкой бинарного дерева?
Мне уж скоро на пенсию, а я до сих пор этого не знаю!
Держите файлик. Там все подробно расписано
0
Вложения
Тип файла: rar Документ Microsoft Word.rar (134.8 Кб, 55 просмотров)
xq
0 / 0 / 0
Регистрация: 14.09.2014
Сообщений: 321
09.06.2015, 02:10  [ТС] #6
app
0
09.06.2015, 02:10
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.06.2015, 02:10

Подсчёт вершин на N-ом уровне не пустого бинарного дерева
Доброго времени суток! Пожалуйста прошу помочь решить задачку, подскажите хотя...

Поиск по бинарному дереву, построение бинарного дерева
Сделал 3 процедуры: 1. строит бинарное дерево 2. рекурсивная процедура...

Функция, находящая наибольший элемент непустого бинарного дерева
Описать функцию, которая находит наибольший элемент непустого дерева, прошу,...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru