25. Бинарные деревья. Поиск . Алгоритм представления любого дерева и леса бинарными деревьями.

Существуют m-арные деревья, т.е. такие деревья у которых полустепень исхода каждой вершины меньше или равна m (где m может быть равно 0,1,2,3 и т.д.). Если полустепень исхода каждой вершины в точности равна либо m, либо нулю, то такое дерево называется ПОЛНЫМ m-АРНЫМ ДЕРЕВОМ. При m=2 такие деревья называются соответственно БИНАРНЫМИ, ДВОИЧНЫМ или ПОЛНЫМИ БИНАРНЫМИ. Таким образом, двоичным деревом называется дерево, каждая вершина которого имеет не более двух потомков. Кроме того, на данные, хранимые в вершинах дерева, вводится следующее правило упорядочения: значения вершин левого поддерева всегда меньше, а значения вершин правого поддерева -больше значения в самой вершине. В бинарном дереве имеется два указателя, поэтому удобно узел представить в виде структуры:

structbtree{int val; btree *left,*right;};

Поиск элемента (FIND)

Дано: дерево Т и ключ K.

Задача: проверить, есть ли узел с ключом K в дереве Т, и если да, то вернуть ссылку на этот узел.

Алгоритм:

Если дерево пусто, сообщить, что узел не найден, и остановиться.

Иначе сравнить K со значением ключа корневого узла X.

Если K=X, выдать ссылку на этот узел и остановиться.

Если K>X, рекурсивно искать ключ K в правом поддереве Т.

Если K<X, рекурсивно искать ключ K в левом поддереве Т.

Node* Object::Search(void* d, Node* n){Node* rc = n; if (rc != NULL){ if (isLess(d, n->Data)) rc = Search(d,n->Left);else if (isGreat(d, n->Data)) rc = Search(d,n->Right);}

Return rc;}

Представление любого дерева, леса бинарными деревьями.

Дерево и лес любого вида можно преобразовать единственным образом в эквивалентное бинарное дерево.

Правило построения бинарного дерева из любого дерева:

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

2. Соединить горизонтальными ребрами всех братьев одного отца;

3. Таким образом перестроить дерево по правилу:

левый сын - вершина, расположенная под данной;

правый сын - вершина, расположенная справа от данной (т.е. на одном ярусе с ней).

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

26. Способы обхода бинарного дерева: нисходящий, восходящий, смешанный.

Нисходящий обход:

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

1. В качестве очередной вершины взять корень дерева. Перейти к пункту 2.

2. Произвести обработку очередной вершины в соответствии с требованиями задачи. Перейти к пункту 3.

3. Если очередная вершина имеет обе ветви, то в качестве новой вершины выбрать ту вершину, на которую ссылается левая ветвь, а вершину, на которую ссылается правая ветвь, занести в стек; перейти к пункту 2;

3. Если очередная вершина является конечной, то выбрать в качестве новой очередной вершины вершину из стека, если он не пуст, и перейти к пункту 2; если же стек пуст, то это означает, что обход всего дерева окончен, перейти к пункту 4;

3.Если очередная вершина имеет только одну ветвь, то в качестве очередной вершины выбрать ту вершину, на которую эта ветвь указывает, перейти к пункту 2.

4. Конец алгоритма.

Смешанный обход можно описать следующим образом:

1) Спуститься по левой ветви с запоминанием вершин в стеке;

2) Если стек пуст то перейти к п.5;

3) Выбрать вершину из стека и обработать данные вершины;

4) Если вершина имеет правого сына, то перейти к нему; перейти к п.1.

5) Конец алгоритма.

Восходящий обход:

1. Обходим левую ветвь потом подымаемся вверх и если на уровне обнаруживаем правую ветвь спускаемся по ней потом снова вверх.

2. Добравшись до вершины спускаемся по правой ветви и повторяем пункт 1. НО найдя последнюю вершину заканчиваем

3. По мере всего прохождения записываем A1 B1 C1 C2 B2 A2 D1 E1 F1 F2 E2 D2 G2

27. Поиск минимальной длины ветви дерева.

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

Длина пути – число ребер соединяющих вершины

Глубина дерева – длина пути от корня до произвольной вершины

Высота дерева – максимальная глубина вершины

Если N число вершин, то высота дерева h=log₂N