Правила обратного обхода дерева

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

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

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

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

Источник

Обход двоичного дерева на Python

Да, двоичные деревья — не самая любимая тема программистов. Это одна из тех старых концепций, о целесообразности изучения которых постоянно ведутся споры. В работе вам довольно редко придется реализовывать двоичные деревья и обходить их, так зачем же уделять им так много внимания на технических собеседованиях?

Сегодня мы не будем переворачивать двоичное дерево (ффухх!), но рассмотрим пару методов его обхода. К концу статьи вы поймете, что двоичные деревья не так страшны, как кажется.

Что такое двоичное дерево?

Недавно мы разбирали реализацию связных списков на Python. Каждый такой список состоит из некоторого количества узлов, указывающих на другие узлы. А если бы узел мог указывать не на один другой узел, а на большее их число? Вот это и есть деревья. В них каждый родительский узел может иметь несколько узлов-потомков. Если у каждого узла максимум два узла-потомка (левый и правый), такое дерево называется двоичным (бинарным).

В приведенном выше примере «корень» дерева, т. е. самый верхний узел, имеет значение 1. Его потомки — 2 и 3. Узлы 3, 4 и 5 называют «листьями»: у них нет узлов-потомков.

Строим двоичное дерево на Python

Как построить дерево на Python? Реализация будет похожей на наш класс Node в реализации связного списка. В этом случае мы назовем класс TreeNode .

Определим метод __init__() . Как всегда, он принимает self . Также мы передаем в него значение, которое будет храниться в узле.

class TreeNode: def __init__(self, value):

Установим значение узла, а затем определим левый и правый указатель (для начала поставим им значение None ).

class TreeNode: def __init__(self, value): self.value = value self.left = None self.right = None

И… все! Что, думали, что деревья куда сложнее? Если речь идет о двоичном дереве, единственное, что его отличает от связного списка, это то, что вместо next у нас тут есть left и right .

Давайте построим дерево, которое изображено на схеме в начале статьи. Верхний узел имеет значение 1. Далее мы устанавливаем левые и правые узлы, пока не получим желаемое дерево.

tree = TreeNode(1) tree.left = TreeNode(2) tree.right = TreeNode(3) tree.left.left = TreeNode(4) tree.left.right = TreeNode(5)

Обход двоичного дерева

Итак, вы построили дерево и теперь вам, вероятно, любопытно, как же его увидеть. Нет никакой команды, которая позволила бы вывести на экран дерево целиком, тем не менее мы можем обойти его, посетив каждый узел. Но в каком порядке выводить узлы?

Самые простые в реализации обходы дерева — прямой (Pre-Order), обратный (Post-Order) и центрированный (In-Order). Вы также можете услышать такие термины, как поиск в ширину и поиск в глубину, но их реализация сложнее, ее мы рассмотрим как-нибудь потом.

Итак, что из себя представляют три варианта обхода, указанные выше? Давайте еще раз посмотрим на наше дерево.

При прямом обходе мы посещаем родительские узлы до посещения узлов-потомков. В случае с нашим деревом мы будем обходить узлы в таком порядке: 1, 2, 4, 5, 3.

Обратный обход двоичного дерева — это когда вы сначала посещаете узлы-потомки, а затем — их родительские узлы. В нашем случае порядок посещения узлов при обратном обходе будет таким: 4, 5, 2, 3, 1.

При центрированном обходе мы посещаем все узлы слева направо. Центрированный обход нашего дерева — это посещение узлов 4, 2, 5, 1, 3.

Давайте напишем методы обхода для нашего двоичного дерева.

Pre-Order

Начнем с определения метода pre_order() . Наш метод принимает один аргумент — корневой узел (расположенный выше всех).

Дальше нам нужно проверить, существует ли этот узел. Вы можете возразить, что лучше бы проверить существование потомков этого узла перед их посещением. Но для этого нам пришлось бы написать два if-предложения, а так мы обойдемся одним.

def pre_order(node): if node: pass

Написать обход просто. Прямой обход — это посещение родительского узла, а затем каждого из его потомков. Мы «посетим» родительский узел, выведя его на экран, а затем «обойдем» детей, вызывая этот метод рекурсивно для каждого узла-потомка.

# Выводит родителя до всех его потомков def pre_order(node): if node: print(node.value) pre_order(node.left) pre_order(node.right)

Просто, правда? Можем протестировать этот код, совершив обход построенного ранее дерева.

Post-Order

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

Вместо «посещения» родительского узла и последующего «обхода» детей, мы сначала «обойдем» детей, а затем «посетим» родительский узел. То есть, мы просто передвинем print на последнюю строку! Не забудьте поменять имя метода на post_order() во всех вызовах.

# Выводит потомков, а затем родителя def post_order(node): if node: post_order(node.left) post_order(node.right) print(node.value)

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

In-Order

Наконец, напишем метод центрированного обхода. Как нам обойти левый узел, затем родительский, а затем правый? Опять же, нужно переместить предложение print!

# выводит левого потомка, затем родителя, затем правого потомка def in_order(node): if node: in_order(node.left) print(node.value) in_order(node.right)

Вот и все, мы рассмотрели три простейших способа совершить обход двоичного дерева.

Источник