Деревья, виды, способы представления, структуры данных, обходы дерева

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

Каждый элемент дерева называется вершиной (узлом) дерева.

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

Начальный узел дерева называют корнем дерева, ему соответствует нулевой уровень.

Листьями дерева называют вершины, в которые входит одна ветвь и не выходит ни одной ветви.

Каждое дерево обладает следующими свойствами:

• существует узел, в который не входит ни одной дуги (корень);

• в каждую вершину, кроме корня, входит одна дуга.

Деревья особенно часто используют на практике при изображении различных иерархий.

Потомки – это все вершины, в которые входят ветви, исходящие из одной общей вершины.

Предок – это вершина, из которой исходят ветви к вершинам следующего уровня.

Уровень потомка на единицу превосходит уровень его предка.

Корень дерева не имеет предка, а листья дерева не имеют потомков.

Высота (глубина) дерева определяется количеством уровней, на которых располагаются его вершины. Высота пустого дерева рана нулю, высота дерева из одного корня – единице. На первом уровне дерева может быть только одна вершина – корень дерева, на втором – потомки корня дерева, на третьем – потомки потомков корня дерева и т.д.

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

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

Степень дерева равна максимальной степени вершины, входящей в дерево. При этом листьями в дереве являются вершины, имеющие степень нуль.

Упорядоченное дерево – это дерево, у которого ветви, исходящие из каждой вершины, упорядочены по определенному критерию.

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

• либо пустой структурой;

• либо элементом, с которым связано конечное число поддеревьев.

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

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

Обход дерева – это упорядоченная последовательность вершин дерева, в которой каждая вершина встречается только один раз.

При обходе все вершины дерева должны посещаться в определенном порядке. Существует несколько способов обхода всех вершин дерева.

 

• прямой порядок – сначала посещается корень n дерева Т, затем все узлы поддерева Т1, далее все узлы поддерева Т2, и т.д., Тк;

• симметричный – сначала посещается все узлы поддерева Т1, далее корень n, далее все узлы поддерева Т2, и т.д., Тк;

• обратный – сначала посещается все узлы поддерева Т1, далее все узлы поддерева Т2, и т.д., Тк, последним посещается корень n.

 

 

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

 

Представление деревьев с помощью указателей

Двоичные деревья поиска, операции добавления элементов.

Двоичные деревья поиска (binary search tree, BST)

В двоичном дереве поиска каждая вершина может иметь (или не иметь) левого и правого ребенка, каждая вершина, кроме корня имеет родителя. При представлении с использованием указателей мы храним для каждой вершины дерева, помимо значения ключа key также указатели left, right и р (поддеревья левое, правое и родитель). Если ребенка (или родителя – для корня) нет, соответствующее поле содержит NULL.

Ключи в двоичном дереве поиска хранятся с соблюдением свойства упорядоченности.

Пусть х произвольная вершина двоичного дерева поиска. Если вершина у находится в левом поддереве вершины х, то key[y] < key[x]. Если у находится в правом поддереве х, то key[y] >key[x].

typedef int T;

struct Node{

T inf;

Node* left;

Node* right;

Node(T w): inf(w), left(0), right(0) { }

~Node(){ }

};

Добавление

class BTree{

Node* root;

Node* _Add(Node *r, T s)

{

if(r == 0)

r = new Node(s);

else if(s < r->inf)

r->left = _Add(r->left, s);

else

r->right = _Add(r->right, s);

return r;

}