Симметричный обход этого дерева

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

Если сыновья узла упорядочиваются слева направо, такое дерево называется упорядоченным. В противном случае дерево называетсянеупорядоченым.

Для упорядоченных деревьев существует три способа рекурсивного описания. Для данных способов существуют правила:

1. Если дерево T является нулевым, то в список обхода заносится нулевая запись.

2. Если дерево состоит ровно из 1 узла, то в список обхода заносится этот узел.

Способы рекурсивного описания:

• Прямой обход— сначала посещается корень, затем узлы поддерева
• Симметричный обход— сначала посещаются все узлы поддерева t₁, затем корень n, затем последовательно в симметричном порядке все узлы поддеревьев t₁,…,t_k
• Обход в обратном порядке— сначала посещаются в обратном порядке все узлы поддерева t₁, затем t₂и т.д., последним посещается корень n.

Схемы алгоритмов обходов:

Только в случае симметричного обхода между сыновьями записывается родитель.

Деревья выражений

Если в каждом узле дерева хранятся некоторые данные, то это значение называется меткой узла. Существуют деревья, метки узлов которых являются числами (операндами), а метки внутренних узлов являются символами математических операций (операторами). Такие деревья называются деревьями выражений. При обходе деревьев выражений составляется список узлов, который можно интерпретировать как запись арифметического выражения. В порядке прямого обхода получается список меток узлов x + a b — c d. Такая форма записи называется префиксной формой выражения. В порядке обратного обхода получается постфиксная форма выражения: a b + c d — x, а в порядке симметричного обхода — инфиксная: (a+b)x(c..d). Вопрос №23. Деревья как АТД, набор операций. Реализация АТД — дерево (с помощью массивов, с использованием списка сыновей). Список операций АТД TREE:

• MAKENULL(T) — создать пустое дерево;
• ROOT(T) — получить метку корня дерева;
• PARENT(n, T) — узнать родителя;
• LEFTMOST_CHILD(n, T) -самый левый сын;
• RIGHT_SIBLING(n, T) — правый брат;
• LABEL(n, T) получить метку узла;
• CREATE(n, T1, T2, . ) — создать дерево из узла-корня и набора поддеревьев.

Рекурсивная функция, которая позволяет обходить дерево в порядке прямого обхода и составлять его список: Функция, которая производит обход дерева не в прямом порядке, использует стек. Для этого можно использовать предыдущую реализацию стека. Основные идея в том, что когда функция дойдет до узла n, стек будет хранить путь от корня до этого узла. Причем корень будет на дне стека, а узел n — на вершине. Сама функция может работать в двух режимах: 1. обход по направлению к потомкам самого левого еще не проверенного пути дерева до тех пор, пока не встретится лист, при этом узлы заносятся в стек. 2. возврат по пройденному пути с поочередным извлечением узлов до тех пор, пока не встретится узел, имеющий еще неописанного правого брата.

Реализация деревьев

Одна из реализаций дерева может быть выполнена на основе массива, где каждый элемент массива – это имя родительского узла. Такая форма дерева очень удобна для реализации PARENT(n, T). Она основана на том свойстве деревьев, что каждый узел, отличающийся от корня, имеет только одного родителя. Однако, она неудобна для написания операторов, дающих информацию о сыновьях. Чтобы реализовать операции этого дерева, нужно условиться о том, что сыновья одного узла нумеруются в возрастающем порядке слева направо. Для представления дерева с помощью списка сыновей можно ввести массив указателей на первый элемент списка сыновей. Каждый указатель является массивом, состоящим из элементов-узлов. Элементы списка сыновей являются сыновьями данного конкретного узла. Список сыновей Такая реализация не очень удобна, если надо реализовать операцию . Возможно следующее изменение представления дерева. В данной реализации заменим массив заголовков на массив области узлов. Элементы этого массива расположены произвольно, каждый элемент — это структура с двумя полями. Первые два поля — это указатели на левых сыновей. Вторые два поля — это указатели на правых братьев. Используя такое представление, можно найти самого левого сына как cellspace [ i ]. node = n. Предположим, что имя узла это n, тогда указатель, стоящий в nodespace[i ]. header, указывает на заголовок самого левого узла в массиве cellspace. Существует модификация предложенного способы представления дерева не с помощью двух массивов, а с помощью одного. Такой способ представления удобен для реализации всех операций АТД дерева, за исключением PARENT. Вопрос №24. Определение двоичных деревьев. Реализация двоичных деревьев в виде массива структур с полями: левый сын, правый сын. Двоичное дерево(бинарное) — это или пустое дерево или дерево у которого любой узел или лист имеет либо левого сына либо или правого сына. Рационально для представления двоичных деревьев использовать массив cellspace, каждый элемент массива — структура. Вопрос №25. Применение двоичных деревьев для конструирования кодов Хаффмана (этапы создания дерева Хаффмана, идея реализации алгоритма).

Источник

Симметричный обход этого дерева

Существует достаточно много алгоритмов работы с древовидными структурами, в которых часто встречается понятие обхода (traversing) дерева или «прохода» по дереву. При таком методе исследования дерева каждый узел посещается только один раз, а полный обход задает линейное упорядочивание узлов, что позволяет упростить алгоритм, так как при этом можно использовать понятие «следующий» узел. т.е. узел стоящий после данного при выбранном порядке обхода.

Существует несколько принципиально разных способов обхода дерева:

Обход в прямом порядке

Каждый узел посещается до того, как посещены его потомки.

Для корня дерева рекурсивно вызывается следующая процедура:

Посетить узел Обойти левое поддерево Обойти правое поддерево

Примеры использования обхода:

• решение задачи методом деления на части
• разузлование сверху
• стратегия «разделяй и властвуй» (Сортировка Фон Hеймана, быстрая сортировка, одновременное нахождение максимума и минимума последовательности чисел, умножение длинных чисел).

Симметричный обход

Посещаем сначало левое поддерево, затем узел, затем — правое поддерево.

Для корня дерева рекурсивно вызывается следующая процедура:

Обойти левое поддерево Посетить узел Обойти правое поддерево

Обход в обратном порядке

Узлы посещаются ‘снизу вверх’.

Для корня дерева рекурсивно вызывается следующая процедура:

Обойти левое поддерево Обойти правое поддерево Посетить узел

Примеры использования обхода:

• анализ игр с полной информацией
• разузлование снизу
• динамическое программирование

Обход в ширину

При обходе в ширину узлы посещаются уровень за уровнем(N-й уровень дерева — множество узлов с высотой N). Каждый уровень обходится слева направо.

Для реализации используется структура queue — очередь с методами

• enqueue — поставить в очередь
• dequeue — взять из очереди
• empty — возвращает TRUE, если очередь пуста, иначе — FALSE

q.enqueue(root); // корень в очередь while (! q.empty) < x = q.dequeue(); visit x; // посетить x if (! x.left.empty) // x.left - левое поддерево q.enqueue(x.left); if (! x.right.empty) // x.right - правое поддерево q.enqueue(x.right); >

Рекурсивные обходы можно, очевидно, организовать и с помощью стека, ‘развернув’ рекурсию.

Источник