Алгоритм инфиксный обход дерева

18. Деревья. Двоичные деревья. Двоичное дерево поиска.

Давайте рассмотрим еще одну структуру данных — дерево.

Дерево – связный граф без циклов.
Справочник терминов:
Корень — самый верхний узел дерева.
Ребро — связь между двумя узлами.
Потомок — узел, имеющий родительский узел.
Родитель — узел, имеющий ребро, соединяющее его с узлом-потомком.
Лист — узел, не имеющий узлов-потомков на дереве.
Высота — это длина самого дальнего пути к листу.
Глубина — длина пути к корню.

Например, дерево может выглядеть так:

Структура организации.

Это дерево показывает структуру компании. Узлы представляют людей или подразделения, линии — связи и отношения. Дерево — это самый эффективный способ представления и хранения такой информации.

Дерево на картинке выше очень простое. Оно отражает только отношение родства категорий, но не накладывает никаких ограничений на свою структуру. У генерального директора может быть как один непосредственный подчиненный, так и несколько или ни одного. На рисунке отдел продаж находится левее отдела маркетинга, но порядок на самом деле не имеет значения. Единственное ограничение дерева — каждый узел может иметь не более одного родителя. Самый верхний узел (совет директоров, в нашем случае) родителя не имеет. Этот узел называется «корневым», или «корнем».

2. Двоичное дерево поиска.

Двоичное дерево поиска похоже на дерево из примера выше, но строится по определенным правилам:
У каждого узла не более двух детей.
Любое значение меньше значения узла становится левым ребенком или ребенком левого ребенка.
Любое значение больше или равное значению узла становится правым ребенком или ребенком правого ребенка.

Давайте посмотрим на дерево, построенное по этим правилам:

Обратите внимание, как указанные ограничения влияют на структуру дерева. Каждое значение слева от корня (8) меньше восьми, каждое значение справа — больше либо равно корню. Это правило применимо к любому узлу дерева.

Основными операциями с бинарными деревьями являются добавление элемента в дерево, удаление элемента и поиск элемента в дереве. Сложность каждой из этих операций O(log n) в лучшем случае, и O(n) в худшем. Зависит от сбалансированности дерева.

Добавление элементов (метод add).

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

Мы не знаем точно, в каком порядке добавлялись остальные значения, но можем представить один из возможных путей. Узлы добавляются методом Add, который принимает добавляемое значение.

Рассмотрим подробнее первые шаги.

В первую очередь добавляется 8. Это значение становится корнем дерева. Затем мы добавляем 4. Поскольку 4 меньше 8, мы кладем ее в левого ребенка, согласно правилу 2. Поскольку у узла с восьмеркой нет детей слева, 4 становится единственным левым ребенком.

После этого мы добавляем 2. 2 меньше 8, поэтому идем налево. Так как слева уже есть значение, сравниваем его со вставляемым. 2 меньше 4, а у четверки нет детей слева, поэтому 2 становится левым ребенком 4.

Затем мы добавляем тройку. Она идет левее 8 и 4. Но так как 3 больше, чем 2, она становится правым ребенком 2, согласно третьему правилу.

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

Удаление элементов (метод remove).

Поведение: Удаляет первый узел с заданным значением.
Сложность: O(log n) в среднем; O(n) в худшем случае.
Удаление узла из дерева — одна из тех операций, которые кажутся простыми, но на самом деле таят в себе немало подводных камней.

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

Случай 1: У удаляемого узла нет правого ребенка.

В этом случае мы просто перемещаем левого ребенка (при его наличии) на место удаляемого узла. В результате дерево будет выглядеть так:

Случай 2: У удаляемого узла есть только правый ребенок, у которого, в свою очередь нет левого ребенка.

В этом случае нам надо переместить правого ребенка удаляемого узла (6) на его место. После удаления дерево будет выглядеть так:

Случай 3: У удаляемого узла есть первый ребенок, у которого есть левый ребенок.

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

Поиск значений (метод search).

Возвращает само значение, если такое значение содержится в дереве. В противном случает возвращает null.
Сложность: O(log n) в среднем; O(n) в худшем случае.
Метод проходит по дереву, выполняя в каждом узле следующие шаги:
Если текущий узел null, вернуть null.
Если значение текущего узла равно искомому, вернуть текущий узел.
Если искомое значение меньше значения текущего узла, установить левого ребенка текущим узлом и перейти к шагу 1.
В противном случае, установить правого ребенка текущим узлом и перейти к шагу 1.

Количество узлов в дереве.

Для подсчета получения количества узлов в дереве проще всего добавить переменную, значение которой инкрементируется методом add и декрементируется методом remove.

3. Обход деревьев.

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

Префиксный обход.

Сложность: O(n).
При префиксном обходе алгоритм получает значение текущего узла перед тем, как перейти сначала в левое поддерево, а затем в правое. Начиная от корня, сначала мы получим значение 4. Затем таким же образом обходятся левый ребенок и его дети, затем правый ребенок и все его дети.
Порядок обхода: 4, 2, 1, 3, 5, 7, 6, 8
Префиксный обход обычно применяется для копирования дерева с сохранением его структуры.

Постфиксный обход.

Сложность: O(n).
При постфиксном обходе мы посещаем левое поддерево, правое поддерево, а потом, после обхода всех детей, переходим к самому узлу.
Порядок обхода: 1, 3, 2, 6, 8, 7, 5, 4
Постфиксный обход часто используется для полного удаления дерева, так как в некоторых языках программирования необходимо убирать из памяти все узлы явно, или для удаления поддерева. Поскольку корень в данном случае обрабатывается последним, мы, таким образом, уменьшаем работу, необходимую для удаления узлов.

Инфиксный обход.

Сложность: O(n).
Инфиксный обход используется тогда, когда нам надо обойти дерево в порядке, соответствующем значениям узлов. В примере выше в дереве находятся числовые значения, поэтому мы обходим их от самого маленького до самого большого. То есть от левых поддеревьев к правым через корень.
Порядок обхода: 1, 2, 3, 4, 5, 6, 7, 8
В примере этот обход используется в методе print.

Приложение к лекции.

using System; namespace ConsoleApplication44 < internal class Program < public static void Main(string[] args) < BinaryTree tree = new BinaryTree(15, null); tree.Add(25); tree.Add(23); tree.Add(29); tree.Add(17); tree.Add(31); tree.Add(5); tree.Remove(23); if (tree.Search(25) == null) < Console.WriteLine("Элемент не найден!"); >else < Console.WriteLine("Элемент найден!"); >tree.Print(); > > public class BinaryTree < private BinaryTree _parent, _left, _right; private int _value; public BinaryTree(int value, BinaryTree parent) < _value = value; _parent = parent; >public void Add(int value) < if (value < _value) < if (_left == null) < _left = new BinaryTree(value, this); >else if (_left != null) < _left.Add(value); >> else < if (_right == null) < _right = new BinaryTree(value, this); >else if (_right != null) < _right.Add(value); >> > private BinaryTree Search(BinaryTree tree, int value) < if (tree == null) < return null; >if (value == tree._value) < return tree; >if (value > tree._value) < return Search(tree._right, value); >else < return Search(tree._left, value); >> public BinaryTree Search(int value) < return Search(this, value); >public bool Remove(int value) < //Проверяем, существует ли данный узел BinaryTree tree = Search(value); if (tree == null) < //Если узла не существует, вернем false return false; >BinaryTree curTree; //Если удаляем корень if (tree == this) < if (tree._right != null) < curTree = tree._right; >else < curTree = tree._left; >while (curTree._left != null) < curTree = curTree._left; >int temp = curTree._value; Remove(temp); tree._value = temp; return true; > //Удаление листьев if (tree._left == null && tree._right == null && tree._parent != null) < if (tree == tree._parent._left) < tree._parent._left = null; >else < tree._parent._right = null; >return true; > //Удаление узла, имеющего левое поддерево, но не имеющее правого поддерева if (tree._left != null && tree._right == null) < //Меняем родителя tree._left._parent = tree._parent; if (tree._parent != null && tree == tree._parent._left) < tree._parent._left = tree._left; >else if (tree._parent != null && tree == tree._parent._right) < tree._parent._right = tree._left; >return true; > //Удаление узла, имеющего правое поддерево, но не имеющее левого поддерева if (tree._left == null && tree._right != null) < //Меняем родителя tree._right._parent = tree._parent; if (tree._parent != null && tree == tree._parent._left) < tree._parent._left = tree._right; >else if (tree._parent != null && tree == tree._parent._right) < tree._parent._right = tree._right; >return true; > //Удаляем узел, имеющий поддеревья с обеих сторон if (tree._right != null && tree._left != null) < curTree = tree._right; while (curTree._left != null) < curTree = curTree._left; >//Если самый левый элемент является первым потомком if (curTree._parent == tree) < curTree._left = tree._left; tree._left._parent = curTree; curTree._parent = tree._parent; if (tree._parent != null && tree == tree._parent._left) < tree._parent._left = curTree; >else if (tree._parent != null && tree == tree._parent._right) < tree._parent._right = curTree; >return true; > //Если самый левый элемент НЕ является первым потомком else < if (curTree._right != null) < curTree._right._parent = curTree._parent; >curTree._parent._left = curTree._right; curTree._right = tree._right; curTree._left = tree._left; tree._left._parent = curTree; tree._right._parent = curTree; curTree._parent = tree._parent; if (tree._parent != null && tree == tree._parent._left) < tree._parent._left = curTree; >else if (tree._parent != null && tree == tree._parent._right) < tree._parent._right = curTree; >return true; > > return false; > private void Print(BinaryTree node) < if (node == null) return; Print(node._left); Console.Write(node + " "); if (node._right != null) < Print(node._right); >> public void Print() < Print(this); Console.WriteLine(); >public override string ToString() < return _value.ToString(); >> >

Итоги занятия.

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

А на следующем занятии мы убедимся в том, что одно дерево хорошо, а лес лучше! Но в лесу так легко заблудиться…

Источник