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

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

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);
  }
}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

При выполнении лабораторной работы для каждого задания требуется написать программу на языке С++, в которой выполнено формирование бинарных деревьев в соответствии с постановкой задачи, ввод данных элементов деревьев с учетом типа информационного поля, их обработка и вывод на экран в указанном формате. Для хранения данных бинарных деревьев следует использовать ресурсы динамической памяти. Ввод данных осуществляется с клавиатуры с учетом требований к входным данным, содержащихся в постановке задачи. Ограничениями на входные данные являются максимальный размер строковых данных, диапазоны числовых типов полей структуры и допустимый размер области динамической памяти в языке С++.

Теоретические сведения.

Ознакомьтесь с материалом лекции 31.

Задания к лабораторной работе.

Выполните приведенные ниже задания.

Указания к выполнению работы.

Выполнение работы следует начать с решения задачи 1, реализовав алгоритмы основных операций над бинарным деревом. Каждое из заданий 2, 3 и 4 необходимо решить в соответствии с изученными методами и реализованными алгоритмами формирования, вывода и обработки данных бинарных деревьев в языке С++. Обработку бинарных деревьев следует выполнить на основе базовых алгоритмов: поиск по дереву, вставка элемента в дерево, балансировка дерева, удаление элемента из дерева, удаление всего дерева. При объявлении бинарных деревьев выполните комментирование используемых полей. Программу для решения каждого задания необходимо разработать методом процедурной абстракции, оформив комментарии к коду.

Следует реализовать каждое задание в соответствии с приведенными этапами:

Требования к отчету.

Отчет по лабораторной работе должен соответствовать следующей структуре.

Контрольные вопросы