Прямой, обратный и симметричный обход дерева
Обход дерева – систематический порядок перечисления всех узлов дерева в соответствие с некоторым правилом упорядочивания этих узлов. При обходе дерева следует различать левого и всех остальных сыновей. Данную последовательность можно обойти, учитывая упорядочивание слева на право.
А
ВС
– прямой.ВСА – обратный, сначала сыновья потом родители.
ВАС – симметричный (внутренний).
Формально процедуру обхода можно записать следующим образом, если
дерево Т нулевое, то список обхода пуст. Если дерево состоит из одного
элемента, то список обхода заносится и обход завершается. Если корень Т имеет Тn, то различают следующие варианты обхода: при прохождение в прямом порядке обхода сначала посещается корень дерева (поддерева), а
затем слева на право посещаются его деревья T1,T2 …Tk, причем к поддереву Tk переход осуществится, только после того, как все дерево T1 будет обойдено аналогичным образом в начале корень, а потом сыновья поддеревья; симметричный обход дерева T начинается с обхода левого дерева T1
после чего посещается родитель T1, дальше слева на право посещается T2 …Tk, каждое из деревьев Ti посещается аналогичны образом; обратный обход T1, T2 …Tk, а затем n каждое из поддеревьев обходится аналогичным образом.
5, 1, 2, 11, 6, 12, 7, 8, 9, 4, 3, 10.
2, 11, 1, 12, 6, 5, 8, 7, 9, 4, 10, 3.
11, 2, 12, 6, 1, 8, 4, 9, 7, 10, 3, 5.
Помеченные деревья или деревья выражений
Помеченное дерево – деревья узлы, которые хранят значения. В дереве выражений, каждый внутренний узел не лист хранит не арифметическую операцию (бинарную), а лист является переменной или константой, т.е. аргументом операции.
(
а
+ в)*(а - с), чтобы вычислить это выражение
а, в, +, а, с, -, * получим обратный обход
или постфиксное (польскую) представление
выражения, который используется при
вычисление выражения в нем – P1
P2 Ө, где P1,P2
постфикс соответствующего выражения.
Здесь не требуется скобок для вычисления операций, потому что расставлена как к структуре дерева.
+ а в – а с , Ө P1 P2, префиксная форма запись подвыражения.
а + в * в – с, P1 Ө P2 симметричный (внутренний) инфикс, скобки в данном случае нужны.
Примеры решения задач:
Вычислить 5 9 10 * + Перевести из постфикса в префикс 2 4 3 * - 5 4 + +
Пусть E1 и E2 подвыражения арифметического вида E1 Ө E2, причем Е1 соответствие левого поддерева, а Е2 правое поддерево с корнем в узле Ө. Таки образом Ө соответствует арифметической операции бинарного вида, т.е. Е1 и Е2 построен в подобных структурах. Тогда обход этого дерева в прямом порядке, Ө Р1 Р2 соответствует префиксной форме записи арифметического выражения. Здесь Р1 и Р2 префиксные формы записи выражений Е1 и Е2. Скобки в префиксном выражение не требуются, так как всегда можно посмотреть Ө Р1 Р2 слева на право без возврата, чтобы определить самый короткий префикс Р1 как единственный возможный в выражение Р1 Р2 (Ө Р1 Р2 ≡ Р). Аналогично обратный обход записывается в виде Р1 Р2 Ө, где Р1 и Р2 постфиксная форма записи поддеревьев Е1 и Е2, скобки также не требуются, так как с одной стороны двигаясь слева на право в выражениях Р1 и Р2 всегда можно выделить Е1, как самый короткий постфикс. А с другой стороны само дерево выражений, так как сама структура дерева однозначно определяет приоритет операций, а разбирая префиксное или постфиксное выражение можно однозначно реконструировать самом дерево чего нельзя добиться в случае с инфиксной формой записи.