Создание бинарного дерева и обход, НЕРЕКУРСИВНО!!! Опции

[TOPEHTO]

нужно к завтраму...
Вот несколько вопросиков вызывают затруднения...
1-создание бинарного дерева нерукурсивно...2-обход бинарного дерева с помощью очереди, в основном интересует сам алгорит а не программная реализация...помогите плиз весь инет облазил-пусто... ...

[volvo]

Ну, в принципе, и с созданием дерева БЕЗ рекурсии тоже нет проблем:

Procedure AddIter(Var root: TTree; X: TType);

  { Функция, создающая новый лист дерева с заданным значением Data }
  Function CreateNode(n: TType): TTree;
  var p: TTree;
  Begin
    New(p);
    p^.Data := n;
    p^.Left := nil; p^.Right := nil;
    CreateNode := p;
  End;

var
  parent, pwalk: TTree;

Begin

  {
    Если корень дерева - нулевой (только начали заполнять дерево, например),
    то создаем новый элемент и запоминаем его, как корень
  }
  if root = nil then root := CreateNode(X)
  else begin

    { Если дерево уже не пустое - тогда начинаем "прогулку" по нему... }

    pWalk := root; { "гулять" начнем с корня }
    while pWalk <> nil do begin { пока не добрались до пустого указателя - делаем следующее }

      { запоминаем текущий элемент, в качестве "родителя" его потомка }
      parent := pWalk;

      {
        переходим в левую лил правую ветвь в зависимости от соотношения величин
        нового элемента и "текущего", которым мы "гуляем" по дереву
      }
      if X < pWalk^.data then pWalk := pWalk^.left
      else pWalk := pWalk^.right

    end;

    {
      Если мы здесь - значит, добрались до пустого указателя...
      Вот теперь делаем то, для чего запоминали родителя текущего элемента:
      опять же в зависимости от того, больше или меньше добавляемое значение,
      чем значение "родителя", создаем новый элемент и запоминаем его в левой,
      или правой ветке...
    }

    if X < parent^.data then parent^.left := CreateNode(X)
    else parent^.right := CreateNode(X);

  end;

End;

Элемент X будет добавлен к дереву... Как видишь, процедура нерекурсивная...

Сообщение отредактировано: volvo - 12.01.2007 7:09