Прямой, обратный и симметричный обход дерева

Обход дерева – систематический порядок перечисления всех узлов дерева в соответствие с некоторым правилом упорядочивания этих узлов. При обходе дерева следует различать левого и всех остальных сыновей. Данную последовательность можно обойти, учитывая упорядочивание слева на право.

1. АВС – прямой.

2. ВСА – обратный, сначала сыновья потом родители.

3. ВАС – симметричный (внутренний).

Формально процедуру обхода можно записать следующим образом, если

дерево Т нулевое, то список обхода пуст. Если дерево состоит из одного

элемента, то список обхода заносится и обход завершается. Если корень Т имеет Тn, то различают следующие варианты обхода: при прохождение в прямом порядке обхода сначала посещается корень дерева (поддерева), а

затем слева на право посещаются его деревья T1,T2 …Tk, причем к поддереву Tk переход осуществится, только после того, как все дерево T1 будет обойдено аналогичным образом в начале корень, а потом сыновья поддеревья; симметричный обход дерева T начинается с обхода левого дерева T1

после чего посещается родитель T1, дальше слева на право посещается T2 …Tk, каждое из деревьев Ti посещается аналогичны образом; обратный обход T1, T2 …Tk, а затем n каждое из поддеревьев обходится аналогичным образом.

1. 5, 1, 2, 11, 6, 12, 7, 8, 9, 4, 3, 10.
2. 2, 11, 1, 12, 6, 5, 8, 7, 9, 4, 10, 3.
3. 11, 2, 12, 6, 1, 8, 4, 9, 7, 10, 3, 5.