Определение дерева приведите свой пример дерева

Определение и свойства деревьев.

Деревом называется произвольный связный граф без циклов. Деревья обладают следующими свойствами:

любые две вершины соединены единственной простои цепью

количество ребер на единицу меньше количества вершин

при удалении любого ребра дерево становится не связным графом

при добавлении к дереву любого ребра в дереве появляется ровно один простой цикл.

Фактически дерево можно получить из любого связного графа

Утверждение: любой связный граф содержит остовный подграф который является деревом. Этот подграф называется остовыным деревом.

Специальные виды деревьев

1 Корневые деревья

Определение: Корневое дерево — ориентированное дерево, которое удовлетворяет условиям:

a) Имеется ровно один узел в который не входит не одно

В каждый узел кроме корня входит ровно одно ребро

Из корня имеется путь к любому ребру.

Если имеется путь от вершины vl к вершине v2, тогда вершина vl предок вершины v2, а вершина v2 потомок вершины vl.

Вершина которая не имеет потомков называется концевой вершиной или листом. Не концевую вершину называют внутренней. Если V₁ и V₂ дуга корневого дерева, то V₁— отец, a V₂— сын

Глубина дерева — длина пути из корня. Узлы находящиеся на одной глубине называются ярусами дерева.

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

2 Бинарные деревья

Определение: Бинарное дерево — корневое дерево у каждой вершины которого не более двух сыновей.

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

Имеется два способа представления бинарных деревьев:

1. Представление в виде двух массивов: первый массив- левые сыновья, второй — правые.

2. Представление в виде списковой структуры tree_ ptr Tree_mode — запись имеющая структуру:

Element- тип узла; Left: tree_ ptr; Right: tree_ ptr;

3 Полные бинарные деревья

Определение: Полное бинарное дерево — бинарное дерево для которого выполняются условия:

a) Заполнение дерева осуществляется от корня к листьям по уровням.

b) Заполнение уровней осуществляется слева направо.

Полные бинарные деревья представляются в виде одномерного массива: первый элемент массива — корень дерева. Для любого i-того узла элемент с индексом (2i) — левый сын, элемент с индексом (2i+l)- правый сын. Отец узла j — (j/2).

4 Бинарные поисковые деревья

Определение: Бинарное поисковое дерево — дерево поиска,

Все ключи в левом поддереве меньше ключа узла V

В правом поддереве все ключи больше, чем ключ V

В дереве нет одинаковых ключей.

5 Сбалансированные деревья

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

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

6 Способы обхода узлов в бинарных деревьях

Большинство алгоритмов при работе с деревьями посещают каждый узел в некотором порядке.

Существует три наиболее распространенных способа обхода деревьев:

1. Прямой порядок: корень посещается раньше, чем поддеревья

Порядок обхода: корень — левое поддерево — правое поддерево.

Процедура организуется рекурсивно.

2. Обратный порядок (снизу вверх): корень посещается после поддеревьев.

Порядок обхода: левое поддерево — правое поддерево- корень.

3. Внутренний порядок (слева направо )

Порядок обхода: левое поддерево – корень — правое поддерево.

7 Представление множеств с помощью деревьев

Базовыми операциями над множествами являются:

определение принадлежности элемента множества.

объединение не пересекающихся множеств.

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

Чтобы определить, к какому множеству принадлежит некоторый элемент — находим этот элемент и определяем корень множества, к которому он принадлежит. Этот корень — есть имя искомого множества.

Объединение непересекающихся множеств можем реали­зовать тремя способами:

Источник

5.14. Деревья и их свойства

– замкнутые цепи_.

_{2. Любые 2 вершины v и w соединены единственной цепью.}

_{Доказательство следует из определения дерева.}

_{3. Для дерева справедливо следующее соотношение: p = q + 1 (*), где p – число вершин, q – число ребер.}

_{Доказательство (индукцией по p):}

_{а) p = 1 – дерево состоит из одной вершины, q = 0, тогда соотношение (*) выглядит 1 = 1.}

_{б) Пусть соотношение (*) верно для любых деревьев, у которых вершин меньше, чем p.}

_{в) Рассмотрим дерево с p вершинами. Уберем ребро, соединяющее вершины v и w. Наш граф разбился на 2 подграфа и . , – деревья, так как они связны и не имеют замкнутых цепей. Поэтому для них верно индукционное предположение:}

_{VWV W}

_.

_{4. Если любые 2 вершины v и w в дереве соединить ребром, то получим ровно одну замкнутую цепь.}

_{Доказательство следует из свойства 2.}

_{5. Пусть G = (p, q) – дерево, где p > 1. Тогда в дереве G существуют хотя бы 2 вершины v и w такие, что .}

_{Доказательство. Как известно, (по свойству 3). Предположим, что не существуют 2 вершины, степень которых равна 1, т.е. пусть , а у остальных вершин , где . Тогда получаем, что . Пришли к противоречию, значит, существуют вершины v и w такие, что .}

_{Определение. Вершины в дереве, степень которых равна 1, называются концевыми.}

_{где max(n) – глубина (количество ярусов) дерева, – корень дерева (корень – это некоторая выделенная вершина).}

5.15. Деревья и операции над ними

_{1. Ребро – дерево с корнем (код 01), дереву из одного ребра дается код 01.}

_{2. Если у нас есть дерево с корнем, то результат присоединения этого дерева к ребру – также есть дерево с корнем.}

_{При этом пусть дерево с корнем имеет код А, тогда дереву, полученному в результате операции 2, ставится код 0А1.}

_{3. Если у нас есть два дерева с корнем,}

_{то результат склеивания этих деревьев также есть дерево с корнем. Если при этом у одного дерева код А, а у другого код В, тогда у дерева, которое получается склеиванием этих деревьев, код будет АВ.}

_{Замечание. Любое дерево с корнем можно получить при помощи вышеуказанных трех операций, при этом всегда можно определить его код.}

_{Пример. Пусть дано корневое дерево Т, определить его код, где}

_{Решение: Исходное дерево Т получено из деревьев двукратным применением операции 3, где}

_{1) Дерево получено из дерева с помощью операции 2, где}

_,

_{Дерево получено из дерева операции 1 двукратным применением}

_{операции 3, тогда код дерева A‘ = 010101, следовательно, код дерева A = 00101011.}

_{2) Дерево Т2 получено с помощью операции 1, его код – 01.}

_{3) Дерево Т3 получено из дерева операции 1 двукратным применением операции 2, тогда код дерева Т3 В = 000111.}

_{В итоге код корневого дерева Т есть код А01В = 0010101101000111.}

_{1) Длина кода дерева равна удвоенному числу его ребер (2q).}

_{2) В любом начальном отрезке (если считать код дерева слева) число нулей числа единиц.}

_{3) Во всем коде число нулей равно числу единиц.}

_{Встает логичный вопрос: как восстанавливать по коду дерево?}

_{Берем произвольный код дерева, где , q – число ребер дерева. Идем слева направо и отмечаем такой момент, когда число нулей совпадает с числом 1. При этом возможны два случая:}

_{1) Пусть равенство наступит в конце кода, тогда , т.е. дерево с кодом получено из дерева с кодом с помощью операции 2.}

_{2) Пусть равенство наступит, не доходя до конца кода, т.е. , а это означает, что дерево с кодом получено из деревьев соответственно с кодами и с помощью операции 3.}

_{Аналогично, т.е. согласно пунктам 1) и 2), восстанавливаем по кодам соответствующие им деревья. Этот процесс называется декодированием. Не сложно доказать (мы практически уже показали), что между деревом и его кодом существует взаимно однозначное соответствие.}

_{Пример. Построить корневое дерево по его коду .}

_{Решение: q = 7. , где . Таким образом, дерево с кодом получено из деревьев соответственно с кодами с трехкратным применением операции 3. Аналогично, дерево с кодом получено из дерева операции 1 с применением операции 2; деревья с кодами и – деревья операции 1; дерево с кодом получено из дерева операции 1 с двукратным применением операции 2. В итоге дерево Т выглядит следующим образом:}

Источник