Версия для печати темы

Нажмите сюда для просмотра этой темы в обычном формате

Форум «Всё о Паскале» _ Теоретические вопросы _ Создание бинарного дерева и обход

Автор: TOPEHTO 11.01.2007 21:40

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

Автор: volvo 11.01.2007 21:57

Здесь был: http://pco.iis.nsk.su/ICP/Practice/dd8-3/node6.html
?

Автор: TOPEHTO 11.01.2007 22:09

СПС громаднейшее, и как вы находи это, Я 2 дня в инете жил не нашео=(
а что насчет 1 вопроса... rolleyes.gif ...сорри за наглость сессия е-мое... mega_chok.gif ...

Автор: TOPEHTO 11.01.2007 23:40

НУ народ посдкажи те про дерево плиз...

Автор: volvo 11.01.2007 23:45

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

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 будет добавлен к дереву... Как видишь, процедура нерекурсивная...

Автор: TOPEHTO 12.01.2007 0:40

А можешь объяснить алгоритм хотя бы в 2-х словах? плиз wink.gif

Автор: TOPEHTO 12.01.2007 5:30

См.личку плиз

Автор: volvo 12.01.2007 7:09

Комментарии добавлены ...