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

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

Структура дерева отражается во входном потоке данных так: каждой вводимой пустой связи соответствует условный символ, например, '*' (звездочка). При этом сначала описываются левые потомки, затем, правые. Для структуры бинарного дерева, представленного на следующем рисунке, входной поток имеет вид: ABD*G***CE**FH**J**. Бинарные деревья могут применяться для поиска данных в специально построенных деревьях (базы данных), сортировки данных, вычислений арифметических выражений, кодирования (метод Хаффмана) и т.д.

Приведем функции перечисленных основных операций при работе с бинарным деревом. //создание бинарного дерева 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 > (*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 Data); Print_BinaryTree(Node->Left, l+1); } else cout 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 Left); else if ( q > 2/3.0) ptr = &((*ptr)->Right); else break; } if (*ptr != NULL) { if ( (double) rand()/RAND_MAX 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); } }