Обход бинарного дерева

← →
ALoG (2008-05-11 18:56) [0]

Здравствуйте. Как можно реализовать обход бинарного дерева в ширину?

← →
Palladin © (2008-05-11 19:08) [1]

а что именно непонятно?

← →
ALoG (2008-05-11 19:37) [2]

Непонятно, как сделать переход от 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;
переход к след.уровню //И это

← →
Amoeba © (2008-05-11 22:26) [3]

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

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

← →
palva © (2008-05-11 22:46) [4]

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

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

← →
korneley © (2008-05-11 23:19) [5]

Может тебя спасет TTreeNode.Level?

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

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

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

Обход бинарного дерева Найти похожие ветки