Студопедия

КАТЕГОРИИ:


Архитектура-(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; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.041 сек.