Если бы мне пришлось выбрать самую важную тему в разработке программного обеспечения, это были бы структуры данных. Один из самых распространенных и простых - дерево - иерархическая структура данных. В этой статье давайте исследуем деревья на Java.
- Что такое двоичное дерево?
- Типы двоичного дерева
- Реализация двоичного дерева
- Обходы по дереву
- Приложения двоичного дерева
Что такое двоичное дерево?
A - это нелинейная структура данных, в которой объекты данных обычно организованы в виде иерархических отношений. Структура нелинейна в том смысле, что, в отличие от массивов, связанных списков, стека и очередей, данные в дереве не организованы линейно. Двоичное дерево - это рекурсивная древовидная структура данных, в которой каждый узел может иметь не более двух дочерних элементов.
У бинарных деревьев есть несколько интересных свойств, когда они идеальны:
- Свойство 1. Общее количество узлов на каждом «уровне» удваивается по мере продвижения вниз по дереву.
- Свойство 2: количество узлов на последнем уровне равно сумме количества узлов на всех других уровнях плюс 1.
Каждый элемент данных, хранящийся в древовидной структуре, называется узлом . Узел дерева состоит из следующих частей:
1. Данные
2. Указатель на левый дочерний элемент
3. Указатель на нужного ребенка.
В Java мы можем представить узел дерева с помощью класса. Ниже приведен пример узла дерева с целочисленными данными.
static class Node {
int value;
Node left, right;
Node(int value){
this.value = value;
left = null;
right = null;
}
Теперь, когда вы знаете, что такое двоичное дерево, давайте рассмотрим различные типы двоичных деревьев.
Типы двоичных деревьев
Полное двоичное дерево
Полное двоичное дерево - это двоичное дерево, в котором каждый узел имеет ровно 0 или 2 дочерних элемента. Пример полностью бинарной косы:
Идеальное двоичное дерево
Бинарное дерево является идеальным двоичным деревом, если все внутренние узлы имеют двух дочерних элементов и все листья находятся на одном уровне. Пример идеальной бинарной косы:
Полное двоичное дерево
Полное двоичное дерево - это двоичное дерево, в котором каждый уровень, кроме, возможно, последнего, полностью заполнен, а все узлы расположены как можно дальше слева. Пример полного двоичного дерева:
Теперь, когда вы знаете о различных типах двоичных деревьев, давайте посмотрим, как создать двоичное дерево.
Реализация двоичного дерева
Для реализации существует вспомогательный класс Node, который будет хранить значения int и ссылаться на каждого дочернего элемента. Первый шаг - найти место, где мы хотим добавить новый узел, чтобы дерево оставалось отсортированным. Мы будем следовать этим правилам, начиная с корневого узла:
- если значение нового узла ниже, чем значение текущего узла, перейдите к левому дочернему элементу
- если значение нового узла больше, чем значение текущего узла, перейдите к правому дочернему элементу
- когда текущий узел нулевой, мы достигли конечного узла, мы вставляем новый узел в эту позицию
Теперь давайте посмотрим, как мы можем реализовать эту логику на примере:
package MyPackage;
public class Tree {
static class Node {
int value;
Node left, right;
Node(int value){
this.value = value;
left = null;
right = null;
}
}
public void insert(Node node, int value) {
if (value < node.value) { if (node.left != null) { insert(node.left, value); } else { System.out.println(" Inserted " + value + " to left of " + node.value); node.left = new Node(value); } } else if (value > node.value) {
if (node.right != null) {
insert(node.right, value);
} else {
System.out.println(" Inserted " + value + " to right of "
+ node.value);
node.right = new Node(value);
}
}
}
public void traverseInOrder(Node node) {
if (node != null) {
traverseInOrder(node.left);
System.out.print(" " + node.value);
traverseInOrder(node.right);
}
}
public static void main(String args[])
{
Tree tree = new Tree();
Node root = new Node(5);
System.out.println("Binary Tree Example");
System.out.println("Building tree with root value " + root.value);
tree.insert(root, 2);
tree.insert(root, 4);
tree.insert(root, 8);
tree.insert(root, 6);
tree.insert(root, 7);
tree.insert(root, 3);
tree.insert(root, 9);
System.out.println("Traversing tree in order");
tree.traverseLevelOrder();
}
}
Вывод:
Binary Tree Example Building tree with root value 5 Inserted 2 to left of 5 Inserted 4 to right of 2 Inserted 8 to right of 5 Inserted 6 to left of 8 Inserted 7 to right of 6 Inserted 3 to left of 4 Inserted 9 to right of 8 Traversing tree in order 2 3 4 5 6 7 8 9
В этом примере мы использовали обход по порядку для обхода дерева. Обход по порядку состоит из первого посещения левого поддерева, затем корневого узла и, наконец, правого поддерева. Есть и другие способы пересечь дерево. Давай проверим их.
Обходы по дереву
По деревьям можно обходить разными способами. Давайте воспользуемся тем же примером дерева, который мы использовали ранее для каждого случая.
Поиск в глубину
Поиск в глубину - это тип обхода, при котором вы продвигаетесь как можно глубже по одному пути, прежде чем выполнить резервное копирование и попробовать другой. Есть несколько способов выполнить поиск в глубину: по порядку, по предварительному заказу и по запросу.
Мы уже проверили обход порядка. Теперь рассмотрим предварительный заказ и пост-заказ.
Просмотр предварительного заказа
При предварительном обходе вы сначала посещаете корневой узел, затем левое поддерево и, наконец, правое поддерево. Вот код.
public void traversePreOrder(Node node) {
if (node != null) {
System.out.print(" " + node.value);
traversePreOrder(node.left);
traversePreOrder(node.right);
}
}
Вывод:
5 2 4 3 8 6 7 9
Просмотр после оформления
При обходе после порядка вы сначала посещаете левое поддерево, затем правое поддерево и в конце корневой узел. Вот код.
public void traversePostOrder(Node node) {
if (node != null) {
traversePostOrder(node.left);
traversePostOrder(node.right);
System.out.print(" " + node.value);
}
}
Вывод:
3 4 2 7 6 9 8 5
Поиск в ширину
Этот тип обхода посещает все узлы уровня перед переходом на следующий уровень. Это как бросить камень в центр пруда. Узлы, которые вы исследуете, «выпадают» из начальной точки. Поиск в ширину также называется порядком уровней и посещает все уровни дерева, начиная с корня и слева направо.
Приложения двоичного дерева
Применения бинарных деревьев включают:
- Используется во многих поисковых приложениях, где данные постоянно поступают / уходят.
- Как рабочий процесс для компоновки цифровых изображений для визуальных эффектов
- Используется почти в каждом маршрутизаторе с высокой пропускной способностью для хранения таблиц маршрутизатора.
- Также используется в беспроводных сетях и распределении памяти
- Используется в алгоритмах сжатия и многом другом
На этом мы подошли к концу статьи «Деревья в Java».
Убедитесь, что вы как можно больше тренируетесь, и вернитесь к своему опыту.
Если вы хотите ознакомиться с другими статьями о самых популярных технологиях на рынке, таких как искусственный интеллект, DevOps, этический взлом, посетите официальный сайт Edureka.
Обязательно обратите внимание на другие статьи в этой серии, которые объясняют различные другие аспекты Java.
5. Строка Java
6. Массив Java
8. Потоки Java
14. Программы Java
17. Сравнимо в Java
26. Учебник по Java
30. 55 самых популярных вопросов на собеседовании с сервлетами
36. 50 лучших вопросов для собеседований по коллекциям Java, которые вам нужно знать
40. Основные вопросы и ответы на собеседовании по MVC, которые вам нужно знать
42. Тупик в Java
46. Деструктор на Яве.
Первоначально опубликовано на https://www.edureka.co 3 сентября 2019 г.
