КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Бинарные деревья
Бинарные деревья являются деревьями со степенью не более двух. Бинарное (двоичное) дерево – это динамическая структура данных, представляющее собой дерево, в котором каждая вершина имеет не более двух потомков (рис. 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); } }
Дата добавления: 2014-01-04; Просмотров: 2082; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |