Бинарные деревья
Бинарные деревья являются деревьями со степенью не более двух.
Бинарное (двоичное) дерево – это динамическая структура данных, представляющее собой дерево, в котором каждая вершина имеет не более двух потомков (рис. 3). Таким образом, бинарное дерево состоит из элементов, каждый из которых содержит информационное поле и не более двух ссылок на различные бинарные поддеревья. На каждый элемент дерева имеется ровно одна ссылка.
 |
Рис.3. Бинарное дерево и его организация
Каждая вершина бинарного дерева является структурой, состоящей из четырех видов полей. Содержимым этих полей будут соответственно:
· информационное поле (ключ вершины);
· служебное поле (их может быть несколько или ни одного);
· указатель на левое поддерево;
· указатель на правое поддерево.
По степени вершин бинарные деревья делятся на (рис. 4):
· строгие – вершины дерева имеют степень ноль (у листьев) или два (у узлов);
· нестрогие – вершины дерева имеют степень ноль (у листьев), один или два (у узлов).
В общем случае у бинарного дерева на k-м уровне может быть до 
вершин. Бинарное дерево называется полным, если оно содержит только полностью заполненные уровни. В противном случае оно является неполным.
Рис.4. Виды бинарных деревьев
Дерево называется сбалансированным, если длины всех путей от корня к внешним вершинам равны между собой. Дерево называется почти сбалансированным, если длины всевозможных путей от корня к внешним вершинам отличаются не более, чем на единицу.
Бинарное дерево может представлять собой пустое множество. Бинарное дерево может выродиться в список (рис. 5).
Рис. 5. Список как частный случай бинарного дерева
Структура дерева отражается во входном потоке данных так: каждой вводимой пустой связи соответствует условный символ, например, '*' (звездочка). При этом сначала описываются левые потомки, затем, правые. Для структуры бинарного дерева, представленного на следующем рисунке 6, входной поток имеет вид: ABD*G***CE**FH**J**.
 |
Рис. 6. Адресация в бинарном дереве
Бинарные деревья могут применяться для поиска данных в специально построенных деревьях (базы данных), сортировки данных, вычислений арифметических выражений, кодирования (метод Хаффмана) и т.д.
Описание бинарного дерева выглядит следующим образом:
struct имя_типа {
информационное поле;
[служебное поле;]
адрес левого поддерева;
адрес правого поддерева;
};
где информационное поле – это поле любого ранее объявленного или стандартного типа;
адрес левого (правого) поддерева – это указатель на объект того же типа, что и определяемая структура, в него записывается адрес следующего элемента левого (правого) поддерева.
Например:
struct point {
int data;//информационное поле
int count; //служебное поле
point *left;//адрес левого поддерева
point *right;//адрес правого поддерева
};
Основными операциями, осуществляемыми с бинарными деревьями, являются:
· создание бинарного дерева;
· печать бинарного дерева;
· обход бинарного дерева;
· вставка элемента в бинарное дерево;
· удаление элемента из бинарного дерева;
· проверка пустоты бинарного дерева;
· удаление бинарного дерева.
Для описания алгоритмов этих основных операций используется следующее объявление:
struct BinaryTree{
int Data; //поле данных
BinaryTree* Left; //указатель на левый потомок
BinaryTree* Right; /указатель на правый потомок
};
. . . . . . . . . .
BinaryTree* BTree = NULL;
Приведем функции перечисленных основных операций при работе с бинарным деревом.
//создание бинарного дерева
void Make_Binary_Tree(BinaryTree** Node, int n){
BinaryTree** ptr;//вспомогательный указатель
srand(time(NULL)*1000);
while (n > 0) {
ptr = Node;
while (*ptr != NULL) {
if ((double) rand()/RAND_MAX < 0.5)
ptr = &((*ptr)->Left);
else ptr = &((*ptr)->Right);
}
(*ptr) = new BinaryTree();
cout << "Введите значение ";
cin >> (*ptr)->Data;
n--;
}
}
//печать бинарного дерева
void Print_BinaryTree(BinaryTree* Node, int l){
int i;
if (Node != NULL) {
Print_BinaryTree(Node->Right, l+1);
for (i=0; i< l; i++) cout << " ";
printf ("%4ld", Node->Data);
Print_BinaryTree(Node->Left, l+1);
}
else cout << endl;
}
//прямой обход бинарного дерева
void PreOrder_BinaryTree(BinaryTree* Node){
if (Node != NULL) {
printf ("%3ld",Node->Data);
PreOrder_BinaryTree(Node->Left);
PreOrder_BinaryTree(Node->Right);
}
}
//обратный обход бинарного дерева
void PostOrder_BinaryTree(BinaryTree* Node){
if (Node != NULL) {
PostOrder_BinaryTree(Node->Left);
PostOrder_BinaryTree(Node->Right);
printf ("%3ld",Node->Data);
}
}
//симметричный обход бинарного дерева
void SymmetricOrder_BinaryTree(BinaryTree* Node){
if (Node != NULL) {
PostOrder_BinaryTree(Node->Left);
printf ("%3ld",Node->Data);
PostOrder_BinaryTree(Node->Right);
}
}
//вставка вершины в бинарное дерево
void Insert_Node_BinaryTree(BinaryTree** Node,int Data) {
BinaryTree* New_Node = new BinaryTree;
New_Node->Data = Data;
New_Node->Left = NULL;
New_Node->Right = NULL;
BinaryTree** ptr = Node;//вспомогательный указатель
srand(time(NULL)*1000);
while (*ptr != NULL) {
double q = (double) rand()/RAND_MAX;
if ( q < 1/3.0) ptr = &((*ptr)->Left);
else if ( q > 2/3.0) ptr = &((*ptr)->Right);
else break;
}
if (*ptr != NULL) {
if ( (double) rand()/RAND_MAX < 0.5 )
New_Node->Left = *ptr;
else New_Node->Right = *ptr;
*ptr = New_Node;
}
else{
*ptr = New_Node;
}
}
//удаление вершины из бинарного дерева
void Delete_Node_BinaryTree(BinaryTree** Node,int Data){
if ( (*Node) != NULL ){
if ((*Node)->Data == Data){
BinaryTree* ptr = (*Node);
if ( (*Node)->Left == NULL && (*Node)->Right == NULL ) (*Node) = NULL;
else if ((*Node)->Left == NULL) (*Node) = ptr->Right;
else if ((*Node)->Right == NULL) (*Node) = ptr->Left;
else {
(*Node) = ptr->Right;
BinaryTree ** ptr1;
ptr1 = Node;
while (*ptr1 != NULL)
ptr1 = &((*ptr1)->Left);
(*ptr1) = ptr->Left;
}
delete(ptr);
Delete_Node_BinaryTree(Node,Data);
}
else {
Delete_Node_BinaryTree(&((*Node)->Left),Data);
Delete_Node_BinaryTree(&((*Node)->Right),Data);
}
}
}
//проверка пустоты бинарного дерева
bool Empty_BinaryTree(BinaryTree* Node){
return ( Node == NULL ? true : false );
}
//освобождение памяти, выделенной под бинарное дерево
void Delete_BinaryTree(BinaryTree* Node){
if (Node != NULL) {
Delete_BinaryTree(Node->Left);
Delete_BinaryTree(Node->Right);
delete(Node);
}
}