24. Деревья, бинарные деревья, дерево двоичного поиска.

Дерево - это частный случай графа, наиболее широко применяемый в программировании.

1. Дерево - это связный граф без циклов.

2. Дерево - это связный граф, в котором при N вершинах всегда ровно N-1 ребро.

3. Дерево - это граф, между любыми двумя вершинами которого существует ровно один путь.

Аналогичным образом определяется и ориентированное дерево - как орграф, в котором между любыми двумя вершинами существует не более одного пути. Корневое дерево - это ориентированное дерево, в котором можно выделить вершины трех видов: корень, листья (другое их название: терминальные вершины) и остальные вершины (нетерминальные); причем должны выполняться два обязательных условия:

1. из листьев не выходит ни одна дуга; из других вершин может выходить сколько угодно дуг;

2. в корень не заходит ни одна дуга; во все остальные вершины заходит ровно по одной дуге.

Предок вершины v - это вершина, из которой исходит дуга, заходящая в вершину v. Потомок вершины v - это вершина, в которую заходит дуга, исходящая из вершины v. Бинарное дерево - это корневое дерево, каждая вершина которого имеет не более двух потомков. В таком случае иногда говорят о левом потомке и правом потомке для текущей вершины. Высота корневого дерева - это максимальное количество дуг, отделяющих листья от корня. Каркас графа - это дерево, полученное после выбрасывания из графа некоторых ребер.

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

Если выражаться простым языком, то структура дерева двоичного поиска подчиняется простому правилу: "если больше - направо, если меньше - налево".

25. Алгоритмы обхода дерева.

Обход дерева - это некоторая последовательность посещения всех его вершин.

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

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

Алгоритм PreOrder

1. Начать с корня дерева.

2. Пометить текущую вершину.

3. Совершить прямой обход левого поддерева.

4. Совершить прямой обход правого поддерева.

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

Алгоритм PostOrder

1. Начать с корня дерева.

2. Совершить обратный обход левого поддерева.

3. Совершить обратный обход правого поддерева.

4. Пометить текущую вершину.

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

Последовательность обхода

1. Пометить вершину 0-го уровня (корень дерева).

2. Пометить все вершины 1-го уровня.

3. Пометить все вершины 2-го уровня.

4. ...

Алгоритм WideOrder

1. Занести в очередь корень дерева.

2. Пока очередь не станет пустой, повторять следующие действия: удалить первый элемент из головы очереди;

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

Древесная сортировка.

Алгоритм TreeSort

1. Для сортируемого множества элементов построить дерево двоичного поиска:

   • первый элемент занести в корень дерева;

   • для всех остальных элементов: начать проверку с корня; двигаться влево или вправо (в зависимости от результата сравнения с текущей вершиной дерева) до тех пор, пока не встретится такой же элемент, либо пока не встретится nil. Во втором случае нужно создать новый лист в дереве, куда и будет записано значение нового элемента.

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

Пример:

//рекурсивный метод обхода бинарного дерева

public void PrintTree(Node root)

{

if (root!=null)

{

PrintTree(root.Left);

Console.WriteLine(root.data);

PrintTree(root.Right);

}

}