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

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

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

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

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. Применение двоичных деревьев для конструирования кодов Хаффмана (этапы создания дерева Хаффмана, идея реализации алгоритма).

Источник

Дерево

Дерево — структура данных, эмулирующая древовидную структуру в виде набора связанных узлов.

 ┌─────┐ | | Корневой узел └─────┘ / | \ ┌─────┐ ┌─────┐ ┌─────┐ | | | | | | Дочерние узлы └─────┘ └─────┘ └─────┘ / | \ ┌─────┐ ┌─────┐ ┌─────┐ | | | | | | Дочерние узлы дочерних узлов └─────┘ └─────┘ └─────┘ 

Пример — синтаксическое дерево для выражения 2 * sin(3 * z — 7)

 ┌─────┐ | * | └─────┘ / \ ┌─────┐ ┌─────┐ | 2 | | sin | └─────┘ └─────┘ | ┌─────┐ | - | └─────┘ / \ ┌─────┐ ┌─────┐ | * | | 7 | └─────┘ └─────┘ / \ ┌─────┐ ┌─────┐ | 3 | | z | └─────┘ └─────┘ 

Еще один пример — двоичное дерево поиска. Термин «двоичное» означет, что у каждого из узлов есть не более двух дочерних узлов. «Дерево поиска» означает, что все значения в левом поддереве каждого узла меньше или равны значению этого узла, а все значения в правом поддереве — наоборот — больше.

Если в таком дереве нам надо найти значение 7, то нам нужно совершить такие действия:

1. Зайти в узел 0. Искомое 7 больше 0, значит нужно продолжить итерирование вправо;
2. Зайти в узел 8. Искомое 7 меньше 8, значит нужно продолжить итерирование влево;
3. Зайти в узел 5. Искомое 7 больше 5, значит нужно продолжить итерирование вправо;
4. Зайти в узел 7. Это и есть искомое значение, можно закончить итерирование.

5.2 Операции над деревом

5.2.1 Вычисление высоты дерева (height)

function height(tree) < // Если дерево пусто, то его высота равна нулю if (!tree) < return 0; > // Иначе высота равна единице плюс максимальная высота из высот левого и правого поддеревьев return 1 + Math.max(height(tree.left), height(tree.right)); > 

5.2.2 Вычисление размера дерева

function size(tree) < // Если дерево пусто, то его размер равен нулю if (!tree) < return 0; > // Иначе размер равен сумме единицы и размеров левого и правого поддеревьев return 1 + size(tree.left) + size(tree.right); > 

5.3 Обход дерева

Часто возникает задача обхода всех узлов дерева в определенном порядке. Существует два основных способа обхода деревьев:

1. Обход в глубину (depth-first) — обход всего поддерева прежде, чем переход к следущему одноуровневому (sibling) поддереву;
2. Обход в ширину (breadth-first) — обход всего уровня прежде, чем переход к следущему уровню.

5.3.1 Симметричный обход (in-order traversal)

Симметричный обход — это обход двоичного дерева в глубину, при котором сначала обходится левое поддерево, затем сам текущий узел, а после этого — правое поддерево.

function inOrderTraversal(tree) < // Если дерево пусто, то нужно остановить обход if (!tree) < return; > // Обходим сначала левое поддерево inOrderTraversal(tree.left); // Выводим значение в текущем узле console.log(tree.key); // Затем обходим правое поддерево inOrderTraversal(tree.right); > 

Например, если у нас есть такое двоичное дерево поиска:

const tree = < key: 0, left: -1>, right: < key: 8, left: < key: 5, left: 1>, right: 7> >, right: 9> > >; 

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

inOrderTraversal(tree); // -1, 0, 1, 5, 7, 8, 9 

5.3.2 Прямой обход (pre-order traversal)

Этот обход отличается от симметричного тем, что обработка значения в текущем узле производится перед обходом левого поддерева. Так же в отличие от симметричного обхода, этот способ определен для всего множества деревьев (не только для двоичных). Главное условие — обработка текущего узла должна произойти раньше обхода поддеревьев.

function preOrderTraversal(tree) < // Если дерево пусто, то нужно остановить обход if (!tree) < return; > // Сначала выводим значение в текущем узле console.log(tree.key); // Затем обходим левое поддерево preOrderTraversal(tree.left); // В конце обходим правое поддерево preOrderTraversal(tree.right); > 

При прямом обходе того же дерева tree вывод будет таким:

preOrderTraversal(tree); // 0, -1, 8, 5, 1, 7, 9 

5.3.3 Обход в обратном порядке (post-order traversal)

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

function postOrderTraversal(tree) < // Если дерево пусто, то нужно остановить обход if (!tree) < return; > // Сначала обходим левое поддерево postOrderTraversal(tree.left); // Затем обходим правое поддерево postOrderTraversal(tree.right); // В конце выводим значение текущего узла console.log(tree.key); > 

При обратном обходе дерева tree вывод будет таким:

preOrderTraversal(tree); // -1, 1, 7, 5, 9, 8, 0 

5.3.4 Обход дерева по уровням (level traversal)

Обход дерева по уровням — обход в ширину.

В предыдущих случаях (при обходе в глубину) мы неявно использовали некоторую структуру данных для сохранения узлов, в которые нам предстоит зайти в будущем. Эта структура — стек. Каждый раз, когда мы заканчивали работу с текущим узлом, мы возвращались к предыдущему фрейму в стеке вызовов и продолжали обход.

В случае обхода дерева в ширину нам необходимо использовать другую структуру данных — очередь. В этот раз ее использование будет явным.

function levelTraversal(tree) < // Если дерево пусто, то нужно остановить обход if (!tree) < return; > // Создаем очередь и добавляем в нее корневой узел const queue = new ArrayBasedQueue(100); queue.enqueue(tree); // Итерируемся до тех пор, пока очередь не пуста while (!queue.empty()) < // Достаем узел из очереди const node = queue.dequeue(); // Выводим значение узла в консоль console.log(node.key); // Если у узла есть левое поддерево, // добавляем его в очередь if (node.left) < queue.enqueue(node.left); >// То же делаем и с правым поддеревом if (node.right) < queue.enqueue(node.right); >> > 

При обходе в ширину дерева tree вывод будет таким:

levelTraversal(tree); // 0, -1, 8, 5, 9, 1, 7 

Источник