Глубина вершины бинарного дерева

Динамические структуры данных: бинарные деревья

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

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

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

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

Дерево – это структура данных , представляющая собой совокупность элементов и отношений, образующих иерархическую структуру этих элементов ( рис. 31.1). Каждый элемент дерева называется вершиной (узлом) дерева. Вершины дерева соединены направленными дугами, которые называют ветвями дерева. Начальный узел дерева называют корнем дерева, ему соответствует нулевой уровень. Листьями дерева называют вершины, в которые входит одна ветвь и не выходит ни одной ветви.

Каждое дерево обладает следующими свойствами:

1. существует узел, в который не входит ни одной дуги (корень);
2. в каждую вершину, кроме корня, входит одна дуга.

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

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

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

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

Степенью вершины в дереве называется количество дуг, которое из нее выходит. Степень дерева равна максимальной степени вершины, входящей в дерево . При этом листьями в дереве являются вершины, имеющие степень нуль. По величине степени дерева различают два типа деревьев:

Упорядоченное дерево – это дерево , у которого ветви, исходящие из каждой вершины, упорядочены по определенному критерию.

Деревья являются рекурсивными структурами, так как каждое поддерево также является деревом. Таким образом, дерево можно определить как рекурсивную структуру, в которой каждый элемент является:

Действия с рекурсивными структурами удобнее всего описываются с помощью рекурсивных алгоритмов.

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

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

Обход дерева – это упорядоченная последовательность вершин дерева, в которой каждая вершина встречается только один раз.

При обходе все вершины дерева должны посещаться в определенном порядке. Существует несколько способов обхода всех вершин дерева. Выделим три наиболее часто используемых способа обхода дерева ( рис. 31.2):

Существует большое многообразие древовидных структур данных. Выделим самые распространенные из них: бинарные (двоичные) деревья, красно-черные деревья, В-деревья, АВЛ-деревья , матричные деревья, смешанные деревья и т.д.

Бинарные деревья

Бинарные деревья являются деревьями со степенью не более двух.

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

Каждая вершина бинарного дерева является структурой, состоящей из четырех видов полей. Содержимым этих полей будут соответственно:

• информационное поле (ключ вершины);
• служебное поле (их может быть несколько или ни одного);
• указатель на левое поддерево ;
• указатель на правое поддерево .

По степени вершин бинарные деревья делятся на ( рис. 31.4):

• строгие – вершины дерева имеют степень ноль (у листьев) или два (у узлов);
• нестрогие – вершины дерева имеют степень ноль (у листьев), один или два (у узлов).

В общем случае у бинарного дерева на k -м уровне может быть до 2 k-1 вершин. Бинарное дерево называется полным, если оно содержит только полностью заполненные уровни. В противном случае оно является неполным.

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

Бинарное дерево может представлять собой пустое множество . Бинарное дерево может выродиться в список ( рис. 31.5).

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

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

Источник

Динамические структуры данных: бинарные деревья

Описание бинарного дерева выглядит следующим образом:

где информационное поле – это поле любого ранее объявленного или стандартного типа;

адрес левого (правого) поддерева – это указатель на объект того же типа, что и определяемая структура, в него записывается адрес следующего элемента левого (правого) поддерева .

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

• создание бинарного дерева ;
• печать бинарного дерева ;
• обход бинарного дерева ;
• вставка элемента в бинарное дерево ;
• удаление элемента из бинарного дерева ;
• проверка пустоты бинарного дерева ;
• удаление бинарного дерева .

Для описания алгоритмов этих основных операций используется следующее объявление:

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 > (*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 //прямой обход бинарного дерева 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); > >

Ключевые термины

Бинарное (двоичное) дерево – это дерево , в котором каждая вершина имеет не более двух потомков.

Вершина (узел) дерева – это каждый элемент дерева.

Ветви дерева – это направленные дуги, которыми соединены вершины дерева.

Высота (глубина) дерева – это количество уровней, на которых располагаются его вершины.

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

Корень дерева – это начальный узел дерева, ему соответствует нулевой уровень.

Листья дерева – это вершины, в которые входит одна ветвь и не выходит ни одной ветви.

Неполное бинарное дерево – это дерево , уровни которого заполнены не полностью.

Нестрогое бинарное дерево – это дерево , у которого вершины имеют степень ноль (у листьев), один или два (у узлов).

Обход дерева – это упорядоченная последовательность вершин дерева, в которой каждая вершина встречается только один раз.

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

Полное бинарное дерево – это дерево , которое содержит только полностью заполненные уровни.

Потомки – это все вершины, в которые входят ветви, исходящие из одной общей вершины.

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

Предок – это вершина , из которой исходят ветви к вершинам следующего уровня.

Сбалансированное дерево – это дерево , у которого длины всех путей от корня к внешним вершинам равны между собой.

Степень вершины – это количество дуг, которое выходит из этой вершины.

Степень дерева – это максимальная степень вершин, входящих в дерево .

Строгое бинарное дерево – это дерево , у которого вершины имеют степень ноль (у листьев) или два (у узлов).

Упорядоченное дерево – это дерево , у которого ветви, исходящие из каждой вершины, упорядочены по определенному критерию.

Уровень вершины – это количество дуг от корня дерева до вершины.

Краткие итоги

1. Деревья являются одними из наиболее широко распространенных структур данных в программировании, которые представляют собой иерархические структуры в виде набора связанных узлов.
2. Каждое дерево обладает следующими свойствами: существует узел, в который не входит ни одной дуги (корень); в каждую вершину, кроме корня, входит одна дуга.
3. С понятием дерева связаны такие понятия, как корень, ветвь, вершина, лист, предок, потомок , степень вершины и дерева, высота дерева .
4. Списочное представление деревьев основано на элементах, соответствующих вершинам дерева.
5. Дерево можно упорядочить по указанному ключу.
6. Просмотреть с целью поиска все вершины дерева можно с помощью различных способов обхода дерева .
7. Наиболее часто используемыми обходами являются прямой, симметричный, обратный.
8. В программировании при решении большого класса задач используются бинарные деревья .
9. Бинарные деревья по степени вершин делятся на строгие и нестрогие, по характеру заполнения узлов – на полные и неполные, по удалению вершин от корня – на сбалансированные и почти сбалансированные.
10. Основными операциями с бинарными деревьями являются: создание бинарного дерева ; печать бинарного дерева ; обход бинарного дерева ; вставка элемента в бинарное дерево ; удаление элемента из бинарного дерева ; проверка пустоты бинарного дерева ; удаление бинарного дерева .
11. Бинарные деревья могут применяться для поиска данных в специально построенных деревьях (базы данных), сортировки данных, вычислений арифметических выражений , кодирования.

Источник