Бинарное дерево

Деревья

Корневым деревом называется множество элементов, в котором выделен элемент, называемый корнем дерева, а все остальные элементы разбиты на несколько непересекающихся подмножеств, называемых поддеревьями, каждое из которых тоже есть дерево.

Элементы дерева связывают между собой таким образом, чтобы каждый узел был связан с корнями своих поддеревьев. Вышестоящий узел называют предком, нижестоящие - поддеревьями или потомками, узлы одного уровня - братьями. Узел, не имеющий поддеревьев, называют концевым узлом, или листом.

Наиболее распространенными способами представления деревьев в памяти компьютера являются следующие:

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

б) если у каждого узла не более некоторого ограниченного количества потомков, то указатели на потомки можно хранить в векторе;

struct Node

{

void *data;

Node* children[10];

};

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

г) обобщение вариантов (а) и (в) как наиболее общее решение;

struct Node

{

void *data;

Node *parent;

Node *child;

Node *brother;

};

struct Tree

{

Node *root;

};

Бинарное дерево - такое дерево, каждый узел которого содержит не более двух поддеревьев, которые называют соответственно левое и правое поддерево. Такие деревья ещё называют двоичным деревом поиска.

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

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

Поиск в таком дереве проиходит по аналогичному алгоритму.

Рассмотрим пример (рис ххх).

Пусть были добавлены объекты со следующими ключами: 7, 4, 2, 12, 8, 6, 5, 9. "7" помещается в корень. Так как 4<7, соответствующий узел добавляется в левое поддерево. 2<4<7 -> "2" помещается в левое поддерево "4". 12>7 -> "12" помещается в правое поддерево "7". И т.д.