Реализация. Алгоритм WideOrder Занести в очередь5) корень дерева

Алгоритм WideOrder

1. Занести в очередь⁵⁾ корень дерева.
2. Пока очередь не станет пустой, повторять следующие действия:
1. удалить первый элемент из головы очереди;
2. добавить в хвост очереди всех потомков удаленной вершины.

Для простоты реализации вновь пополним структуру дерева полем next:ukaz, которое будет служить для связки очереди:

head:= root;tail:= root;k:= 0;repeat tail^.next:= head^.left; if head^.left<>nil then tail:= tail^.next; tail^.next:= head^.right; if head^.right<>nil then tail:= tail^.next; inc(k); head^.znachenie:= k; {можно write(head^.znachenie);} head:= head^.nextuntil head = nil;

Рис. 12.5. Последовательность нумерации вершин при обходе дерева в ширину

Дата добавления: 2014-01-03