Мастера DELPHI (документация, исходники, скачать)

Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

« предыдущая ветвь | форум | следующая ветвь »

Обход бинарного дерева [D7, XP]

ALoG © (2008-05-11 18:56:00)
Здравствуйте. Как можно реализовать обход бинарного дерева в ширину?

MBo (2008-05-12 05:58:00) [1]
proc TraverseByLevels(Root)
Queue.Put(Root)
while not Queue.Empty do begin
Node = Queue.Get
if Node.Left<>Nil then Queue.Put(Node.Left)
if Node.Right<>Nil then Queue.Put(Node.Right)
end

korneley (2008-05-11 23:44:00) [2]

> А что такое обход в ширину и чем он отличается от обхода
> в глубину? Или, может быть, в высоту? Просветите.

Как я понял, автор хочет по уровням ноды запихивать. Но, по моему, это не в ширину получается, а действительно, в высоту :)

korneley (2008-05-11 23:19:00) [3]
Может тебя спасет TTreeNode.Level?

palva (2008-05-11 22:46:00) [4]

ALoG (11.05.08 18:56)
> обход бинарного дерева в ширину

А что такое обход в ширину и чем он отличается от обхода в глубину? Или, может быть, в высоту? Просветите.

Amoeba (2008-05-11 22:26:00) [5]

> Непонятно, как сделать переход от 1го уровня дерева ко 2му,
> 3му, Nму...

Рекурсию нужно использовать, и будет тебе счастье.

ALoG (2008-05-11 19:37:00) [6]
Непонятно, как сделать переход от 1го уровня дерева ко 2му, 3му, Nму... То есть сначала понятно: корень дерева записываю в очередь, считываю из очереди элемент, заношу куда-либо, удаляю его из очереди... А вот как потом занести в очередь всех сыновей 2го уровня?

Примерно так должно быть:
Temp1:=nil; Temp2 :=nil; Temp1 := значение корня tree;
While (Temp1 < > nil) or (Temp2 < > nil) do
Begin
If (Temp1 < > nil)
Then
:=начало очереди Temp1;
удалить элемент из очереди Temp1;
Всех сыновей -> Temp2; // Это непонятно как
Else
Temp1:=Temp2;
Temp2:= nil;
переход к след.уровню // И это

Palladin (2008-05-11 19:08:00) [7]
а что именно непонятно?

Наверх

	« предыдущая ветвь \| форум \| следующая ветвь »