Введение в бинарное дерево — учебные пособия по структуре данных и алгоритмам

Опубликовано: 26 Февраля, 2023

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

  • Корень: корень дерева — это самый верхний узел дерева, у которого нет родительского узла. В каждом дереве есть только один корневой узел.
  • Родительский узел: узел, который является предшественником узла, называется родительским узлом этого узла.
  • Дочерний узел: узел, который является непосредственным преемником узла, называется дочерним узлом этого узла.
  • Родной брат: дочерние элементы одного и того же родительского узла называются братьями и сестрами.
  • Edge: Edge выступает в качестве связующего звена между родительским узлом и дочерним узлом.
  • Лист: узел, у которого нет дочерних элементов, называется листовым узлом. Это последний узел дерева. В дереве может быть несколько листовых узлов.
  • Поддерево: поддерево узла — это дерево, рассматривающее этот конкретный узел как корневой узел.
  • Глубина: Глубина узла — это расстояние от корневого узла до этого конкретного узла.
  • Высота: высота узла — это расстояние от этого узла до самого глубокого узла этого поддерева.
  • Высота дерева: Высота дерева — это максимальная высота любого узла. Это то же самое, что и высота корневого узла.
  • Уровень: Уровень — это количество родительских узлов, соответствующих данному узлу дерева.
  • Степень узла: степень узла — это количество его дочерних элементов.
  • NULL: количество узлов NULL в двоичном дереве равно (N+1), где N — количество узлов в двоичном дереве.

Зачем использовать древовидную структуру данных?

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

2. Деревья (с некоторым упорядочением, например, BST) обеспечивают умеренный доступ/поиск (быстрее, чем связанный список, и медленнее, чем массивы).
3. Деревья обеспечивают умеренную вставку/удаление (быстрее, чем массивы, и медленнее, чем неупорядоченные связанные списки).
4. Подобно связанным спискам и в отличие от массивов, деревья не имеют верхнего предела количества узлов, поскольку узлы связаны с помощью указателей.

Основные области применения древовидной структуры данных:

  1. Работа с иерархическими данными.
  2. Упростите поиск информации (см. обход дерева).
  3. Управление отсортированными списками данных.
  4. В качестве рабочего процесса для компоновки цифровых изображений для визуальных эффектов.
  5. Алгоритмы маршрутизатора
  6. Форма многоступенчатого принятия решений (см. деловые шахматы).

Что такое бинарное дерево?

A binary tree is a tree data structure composed of nodes, each of which has at most, two children, referred to as left and right nodes and the tree begins from root node.

Представление бинарного дерева:

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

  • Данные
  • Указатель на левого потомка
  • Указатель на правильный дочерний элемент

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

C




// Structure of each node of the tree
 
struct node {
    int data;
    struct node* left;
    struct node* right;
};

C++



// Use any below method to implement Nodes of tree
 
// Method 1: Using "struct" to make
// user-define data type
struct node {
    int data;
    struct node* left;
    struct node* right;
};
 
// Method 2: Using "class" to make
// user-define data type
class Node {
public:
    int data;
    Node* left;
    Node* right;
};
Python



# A Python class that represents
# an individual node in a Binary Tree
 
class Node:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.val = key
Java



// Class containing left and right child
// of current node and key value
class Node {
    int key;
    Node left, right;
 
    public Node(int item)
    {
        key = item;
        left = right = null;
    }
}
C#



// Class containing left and right child
// of current node and key value
 
class Node {
    int key;
    Node left, right;
 
    public Node(int item)
    {
        key = item;
        left = right = null;
    }
}
Javascript



<script>
/* Class containing left and right child of current
   node and key value*/
 
class Node
{
    constructor(item)
    {
        this.key = item;
        this.left = this.right = null;
    }
}
 
// This code is contributed by umadevi9616
</script>
Основные операции с бинарным деревом:
  • Вставка элемента.
  •  Удаление элемента.
  •  Поиск элемента.
  •  Удаление элемента.
  •  Обход элемента. Существует четыре (в основном три) типа обхода бинарного дерева, которые будут обсуждаться далее.
Вспомогательные операции над бинарным деревом:
  • Нахождение высоты дерева
  •  Найдите уровень дерева
  •  Нахождение размера всего дерева.
Применение бинарного дерева:
  • В компиляторах используются деревья выражений, которые являются приложением двоичных деревьев.
  •  Деревья кодирования Хаффмана используются в алгоритмах сжатия данных.
  •  Priority Queue — еще одно приложение бинарного дерева, которое используется для поиска максимума или минимума с временной сложностью O(1).
  •  Представлять иерархические данные.
  •  используется в программном обеспечении для редактирования, таком как Microsoft Excel и электронные таблицы.
  •  полезно для сегментации индексации в базе данных полезно для хранения кеша в системе,
  •  синтаксические деревья используются для большинства известных компиляторов для программирования, таких как GCC и AOCL, для выполнения арифметических операций.
  •  для реализации приоритетных очередей.
  •  используется для поиска элементов за меньшее время (бинарное дерево поиска)
  •  используется для обеспечения быстрого выделения памяти в компьютерах.
  •  выполнять операции кодирования и декодирования.
Обход бинарного дерева:
Алгоритмы обхода дерева можно разделить на две категории:
  • Алгоритмы поиска в глубину (DFS)
  •  Алгоритмы поиска в ширину (BFS)
Обход дерева с использованием алгоритма поиска в глубину (DFS) можно разделить на три категории:
  • Обход в предварительном порядке (текущий-левый-правый: посетите текущий узел перед посещением любых узлов внутри левого или правого поддеревьев. Здесь обход является корнем — левым дочерним элементом — правым дочерним элементом. Это означает, что сначала проходится корневой узел, а затем его левый дочерний элемент. и, наконец, правильный ребенок.
  •  Обход в порядке (левый-текущий-правый): посетите текущий узел после посещения всех узлов внутри левого поддерева, но до посещения любого узла в правом поддереве. Здесь обход левый дочерний – корень – правый дочерний. Это означает, что сначала проходится левый дочерний элемент, затем его корневой узел и, наконец, правый дочерний элемент.
  •  Обход в обратном порядке (влево-вправо-текущий): посещение текущего узла после посещения всех узлов левого и правого поддеревьев. Здесь обход левый дочерний – правый дочерний – корень. Это означает, что сначала прошел левый потомок, затем правый потомок и, наконец, его корневой узел.
Обход дерева с использованием алгоритма поиска в ширину (BFS) можно дополнительно отнести к одной категории:
  • Обход по порядку уровней: посещайте узлы по уровню и слева направо на одном уровне. Здесь обход осуществляется по уровням. Это означает, что сначала прошел самый левый ребенок, а затем другие дети того же уровня слева направо.
Давайте пройдём по следующему дереву всеми четырьмя методами обхода:
Предзаказ Обход вышеуказанного дерева: 1-2-4-5-3-6-7
 По порядку обход вышеуказанного дерева: 4-2-5-1-6-3-7
 Пост-порядковый обход вышеуказанного дерева: 4-5-2-6-7-3-1
 Порядок обхода вышеприведенного дерева: 1-2-3-4-5-6-7
Реализация бинарного дерева:
Давайте создадим простое дерево с 4 узлами. Созданное дерево будет выглядеть следующим образом.
Ниже приведена реализация бинарного дерева:
Описание: Дерево — это иерархическая структура данных. Основные области применения деревьев включают поддержку иерархических данных, обеспечение умеренного доступа и операции вставки/удаления. Двоичные деревья — это частные случаи дерева, в котором каждый узел имеет не более двух дочерних элементов.
Ниже приведены набор 2 и набор 3 этого поста.
 Свойства бинарного дерева
 Типы бинарного дерева
 Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсуждаемой выше.

            

                            

                    
                                    

                        

                
РЕКОМЕНДУЕМЫЕ СТАТЬИ