Структура данных и алгоритмы - Дерево

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

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

Важные термины

Ниже приведены важные термины, относящиеся к дереву.

• Path - Путь означает последовательность узлов по краям дерева.

• Root- Узел наверху дерева называется корнем. У каждого дерева есть только один корень и один путь от корневого узла к любому узлу.

• Parent - Любой узел, кроме корневого, имеет одно ребро вверх до узла, называемого родительским.

• Child - Узел ниже данного узла, соединенный его ребром вниз, называется его дочерним узлом.

• Leaf - Узел, не имеющий дочернего узла, называется листовым узлом.

• Subtree - Поддерево представляет потомков узла.

• Visiting - Посещение означает проверку значения узла, когда управление находится на узле.

• Traversing - Перемещение означает прохождение узлов в определенном порядке.

• Levels- Уровень узла представляет собой поколение узла. Если корневой узел находится на уровне 0, то его следующий дочерний узел находится на уровне 1, его внук - на уровне 2 и так далее.

• keys - Ключ представляет собой значение узла, на основании которого должна выполняться операция поиска для узла.

Двоичное представление дерева поиска

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

Мы собираемся реализовать дерево, используя объект узла и соединяя их через ссылки.

Узел дерева

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

struct node {
   int data;   
   struct node *leftChild;
   struct node *rightChild;
};

В дереве все узлы имеют общую конструкцию.

Основные операции BST

Основные операции, которые могут быть выполнены с структурой данных двоичного дерева поиска, следующие:

• Insert - Вставляет элемент в дерево / создает дерево.

• Search - Ищет элемент в дереве.

• Preorder Traversal - Обходит дерево по предварительному заказу.

• Inorder Traversal - Обходит дерево по порядку.

• Postorder Traversal - Обходит дерево в режиме пост-заказа.

В этой главе мы изучим создание (вставку) древовидной структуры и поиск элемента данных в дереве. Мы узнаем о методах обхода дерева в следующей главе.

Вставить операцию

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

Алгоритм

If root is NULL 
   then create root node
return

If root exists then
   compare the data with node.data
   
   while until insertion position is located

      If data is greater than node.data
         goto right subtree
      else
         goto left subtree

   endwhile 
   
   insert data
	
end If

Реализация

Реализация функции вставки должна выглядеть так -

void insert(int data) {
   struct node *tempNode = (struct node*) malloc(sizeof(struct node));
   struct node *current;
   struct node *parent;

   tempNode->data = data;
   tempNode->leftChild = NULL;
   tempNode->rightChild = NULL;

   //if tree is empty, create root node
   if(root == NULL) {
      root = tempNode;
   } else {
      current = root;
      parent  = NULL;

      while(1) {                
         parent = current;

         //go to left of the tree
         if(data < parent->data) {
            current = current->leftChild;                
            
            //insert to the left
            if(current == NULL) {
               parent->leftChild = tempNode;
               return;
            }
         }
			
         //go to right of the tree
         else {
            current = current->rightChild;
            
            //insert to the right
            if(current == NULL) {
               parent->rightChild = tempNode;
               return;
            }
         }
      }            
   }
}

Поисковая операция

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

Алгоритм

If root.data is equal to search.data
   return root
else
   while data not found

      If data is greater than node.data
         goto right subtree
      else
         goto left subtree
         
      If data found
         return node
   endwhile 
   
   return data not found
   
end if

Реализация этого алгоритма должна выглядеть так.

struct node* search(int data) {
   struct node *current = root;
   printf("Visiting elements: ");

   while(current->data != data) {
      if(current != NULL)
      printf("%d ",current->data); 
      
      //go to left tree

      if(current->data > data) {
         current = current->leftChild;
      }
      //else go to right tree
      else {                
         current = current->rightChild;
      }

      //not found
      if(current == NULL) {
         return NULL;
      }

      return current;
   }  
}

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