Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 16.06.2011, 12:35   #1
Cannibal
Форумчанин
 
Регистрация: 17.02.2008
Сообщений: 191
По умолчанию Преоразование бинарного дерева в нерегулярное

вот алгоритм
Цитата:
Правило построения бинарного дерева из любого дерева:
1. В каждом узле оставить только ветвь к старшему сыну (вертикальное соединение);
2. Соединить горизонтальными ребрами всех братьев одного отца;
3. Таким образом перестроить дерево по правилу:
левый сын - вершина, расположенная под данной;
правый сын - вершина, расположенная справа от данной (т.е. на одном ярусе с ней).
4. Развернуть дерево таким образом, чтобы все вертикальные ветви отображали левых сыно-вей, а горизонтальные - правых.

Для обратного преобразования нужно выполнить следующие действия:
1. В каждом узле оставить левую ветвь
2. Правого потомка примсоединить к узлу, находящемуся на уровень выше.
вот реализация
Код:

TBinTree = ^TBinVersh;
TBinVersh = record
  inf : integer;
  left,right : TBinTree;
  end;

TArc =^TListVersh;
TTree = ^TVersh;
TVersh = record
  inf : integer;
  sons : TArc;
  end;
TListVersh = record
  versh : TTree;
  next : TArc;
  end;
  
function createVersh(key: Integer): TTree;
var
  versh: TTree;

begin
  new(versh);
  versh^.inf := key;
  versh^.sons := nil;
  createVersh := Versh;
end;


procedure ToTree(BinTree: TBinTree; var tree: TTree);
var
  Sons: TArc;
begin
  if binTree = nil then
    tree := nil
  Else begin
    write(bintree^.inf:3);
    Tree := CreateVersh(BinTree^.inf);
    new(sons);
    ToTree(BinTree^.Left, sons^.Versh);
    if binTree^.left <> nil then  begin
      new(sons);
      ToTree(BinTree^.Left^.Right, Sons^.versh);
  //    end;
      if sons^.versh<>Nil then begin
        sons^.next := Tree^.Sons;
        tree^.sons := sons;
      end
      else
        sons^.next := nil
      end
    else
      Sons := Nil;
  Tree^.Sons := Sons;
  end;
end;

почему-то процедура не обходит все вершины дерева и в рез. дереве только корневая вершина и вершина правого подподдерева левого поддерева
Mathematicians often mix up Christmas and Halloween, because Dec.25=Oct.31.

Последний раз редактировалось Cannibal; 16.06.2011 в 12:38.
Cannibal вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц



Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Высота бинарного дерева dido171 Помощь студентам 4 02.12.2014 13:30
Обход бинарного дерева cyt Паскаль, Turbo Pascal, PascalABC.NET 2 17.12.2010 03:29
Высота бинарного дерева m9yt Общие вопросы C/C++ 5 13.03.2010 22:17
Составление бинарного дерева [MI_nor] Общие вопросы C/C++ 1 08.05.2009 00:28
создание бинарного дерева zetrix Паскаль, Turbo Pascal, PascalABC.NET 2 30.11.2006 19:32