Сторож, не сердись, я не хотел тебя ругать или презирать.Сегодня я просто хочу поделиться со всеми знаниями о деревьях, но я все же хочу сказать, что как программист, у тебя есть дерево в твое сердце? У вас закончатся очки? Ближе к дому, дерево является одной из наших часто используемых структур данных.Существует много типов деревьев, таких как двоичное дерево, двоичное дерево поиска, сбалансированное двоичное дерево, красно-черное дерево, B-дерево, B+-дерево и т. д. Сегодня мы поговорим о деревьях, связанных с бинарными деревьями.
Что такое дерево?
Для начала нам нужно узнать, что такое дерево? Наше обычное дерево растет вверх и имеет ответвления, но не образует замкнутого контура.Дерево по структуре данных похоже на дерево, которое мы обычно видим, а точнее похоже на корень дерева.Я нарисовал рисунок-схему , чтобы каждый мог лучше понять дерево.
Дерево также будет включать в себя три концепции高度,深度,层, давайте посмотрим на определения этих трех существительных:
высокий: самый длинный путь от узла к конечному узлу, считая от 0
глубина: количество ребер, которые следуют за узлом к этому узлу, начиная с 0
Этаж: Расстояние между узлом и корневым узлом, считая от 1
Зная понятия трех существительных, мы используем картинку, чтобы представить эти три понятия более ярко.
Выше приведены основные понятия деревьев.Существует много типов деревьев.В основном мы изучаем бинарные деревья.
бинарное дерево
Двоичное дерево соответствует своему названию, и каждый элемент имеет не более двух узлов, называемых левыми и правыми узлами. Конечно, не каждый элемент должен иметь два узла, у некоторых могут быть только левые узлы, а у некоторых могут быть только правые узлы. Точно так же, как страна открывает двух детей, не всем нужно иметь двоих детей. Давайте посмотрим на типичное бинарное дерево.
Основываясь на различных режимах хранения дерева, чтобы лучше использовать пространство для хранения, двоичное дерево делится на полное двоичное дерево и неполное двоичное дерево.Давайте сначала посмотрим, что такое полное двоичное дерево и неполное бинарное дерево?
Определение полного бинарного дерева: Листовые узлы находятся в двух нижних слоях, листовые узлы последнего слоя расположены слева, и, кроме последнего слоя, количество узлов других слоев должно достигать максимального
Может быть, вы не можете понять, просто взглянув на определение.Давайте посмотрим на несколько картинок, и вы сможете понять, что такое полное бинарное дерево и неполное бинарное дерево.
1. Полное бинарное дерево
2. Неполное бинарное дерево
Выше мы сказали, что режим хранения на основе дерева отличается, и он делится на полное бинарное дерево и неполное бинарное дерево, тогда давайте рассмотрим режим хранения дерева.
режим хранения бинарного дерева
Существует два режима хранения двоичного дерева, один из которых основан на указателе или ссылке.Метод хранения двоичной цепочки, один основан на массивепоследовательное хранение
Метод хранения двоичной цепочки
Метод хранения цепочки относительно прост и понятен.Каждый узел имеет три поля, в одном поле хранится значение узла, а в двух других полях хранятся ссылки на левый и правый узлы. Мы можем легко нанизать все дерево по байтам, и структура метода хранения цепочки, вероятно, растет так.
последовательное хранение
Метод последовательного хранения реализован на основе массива.Массив представляет собой упорядоченное пространство памяти.Если мы найдем координаты узлаi=1, левый узел равен 2 *i= 2, правый узел 2 *i+ 1 = 3, и так далее, каждый узел вычисляется так, а затем дерево преобразуется в массив, а в свою очередь, по этому правилу, мы также можем преобразовать массив в дерево. Увидев это, я думаю, вы, должно быть, заметили некоторые недостатки.Если это несбалансированное бинарное дерево, вызовет ли оно много траты места? Правильно, поэтому вам нужно разделить полные бинарные деревья и неполные бинарные деревья. Давайте рассмотрим два режима хранения дерева на основе массива по отдельности.
Метод последовательного хранения полного двоичного дерева
Метод последовательного хранения неполного бинарного дерева
Из рисунка видно, что после преобразования дерева в массив полное бинарное дерево использует массив для хранения только одного места хранения с индексом 0, а неполное бинарное дерево тратит впустую много места.Если дерево является полным бинарным деревом, использование хранения массива экономит место, чем хранение цепочки, потому что хранилище массива не требует хранения информации о левых и правых узлах.
Мы узнали об определении, типе и методе хранения бинарного дерева выше.Далее давайте узнаем об обходе бинарного дерева.Обход бинарного дерева также является часто встречающейся проблемой на собеседованиях.
Обход бинарного дерева
Чтобы понять обход двоичного дерева, нам сначала нужно создать экземпляр двоичного дерева. Мы используем цепочку хранения для определения дерева. Создание экземпляра дерева требует информации об узле дерева для хранения информации об узле, потому что мы используем только Цепное хранилище, поэтому информация о нашем узле выглядит следующим образом.
/**
* 定义一棵树
*/
public class TreeNode {
// 存储值
public int data;
// 存储左节点
public TreeNode left;
// 存储右节点
public TreeNode right;
public TreeNode(int data) {
this.data = data;
}
}
После определения информации об узле мы можем инициализировать дерево.Следующий процесс инициализации дерева:
public static TreeNode buildTree() {
// 创建测试用的二叉树
TreeNode t1 = new TreeNode(1);
TreeNode t2 = new TreeNode(2);
TreeNode t3 = new TreeNode(3);
TreeNode t4 = new TreeNode(4);
TreeNode t5 = new TreeNode(5);
TreeNode t6 = new TreeNode(6);
TreeNode t7 = new TreeNode(7);
TreeNode t8 = new TreeNode(8);
t1.left = t2;
t1.right = t3;
t2.left = t4;
t4.right = t7;
t3.left = t5;
t3.right = t6;
t6.left = t8;
return t1;
}
После вышеуказанных шагов наше дерево будет расти, как показано на рисунке ниже, а число представляет собой значение узла.
После того, как у нас есть дерево, мы можем пройти по дереву.Существует три способа обхода двоичного дерева: обход в прямом порядке, обход по порядку и последующий обход.Три метода обхода связаны с порядком вывода узла. Давайте рассмотрим эти три метода обхода по отдельности.
обход предварительного заказа
обход предварительного заказа: Для любого узла в дереве сначала выведите узел, затем его левое поддерево и, наконец, его правое поддерево.
Чтобы облегчить ваше понимание, на основе бинарного дерева, которое мы определили выше, я сделал динамическую диаграмму потока выполнения трех методов обхода. Надеюсь, это будет полезно для вашего чтения. Давайте посмотрим на динамическую диаграмму потока выполнения обхода предварительного заказа.
// 先序遍历，递归实现 先打印本身，再打印左节点，在打印右节点
public static void preOrder(TreeNode root) {
if (root == null) {
return;
}
// 输出本身
System.out.print(root.data + " ");
// 遍历左节点
preOrder(root.left);
// 遍历右节点
preOrder(root.right);
}
Неупорядоченный обход
Неупорядоченный обход: Для любого узла в дереве сначала напечатать его левое поддерево, затем напечатать себя и, наконец, напечатать его правое поддерево.
Как и в случае обхода в предварительном порядке, давайте взглянем на динамическую диаграмму потока выполнения обхода в порядке.
// 中序遍历 先打印左节点，再输出本身，最后输出右节点
public static void inOrder(TreeNode root) {
if (root == null) {
return;
}
inOrder(root.left);
System.out.print(root.data + " ");
inOrder(root.right);
}
пост-порядковый обход
пост-порядковый обход: Для любого узла в дереве сначала выведите его левое поддерево, затем правое поддерево и, наконец, выведите сам узел.
Как и в случае с первыми двумя обходами, после понимания концепции давайте сначала посмотрим на картинку.
// 后序遍历 先打印左节点，再输出右节点，最后才输出本身
public static void postOrder(TreeNode root) {
if (root == null) {
return;
}
postOrder(root.left);
postOrder(root.right);
System.out.print(root.data + " ");
}
Обход бинарного дерева по-прежнему очень прост. Хотя есть три метода обхода, все они одинаковы, но порядок вывода разный. После стольких знаний выше, я считаю, что у вас должно быть много знаний о бинарных деревьях. Далее Давайте взгляните на обычное и специальное бинарное дерево:бинарное дерево поиска
бинарное дерево поиска
Двоичное дерево поиска также называют двоичным деревом поиска. Из названия мы можем понять, что этот вид дерева должен иметь превосходные преимущества в поиске. Это действительно так. Двоичное дерево поиска действительно дерево, рожденное для поиска, но это не только поддерживает быстрый поиск данных, а также поддерживает быструю вставку и удаление данных. Так как же это сделать? Начнем с концепции бинарных деревьев поиска.
бинарное дерево поиска: Для любого узла в дереве значение каждого узла в левом поддереве должно быть меньше значения этого узла, а значение правого узла поддерева больше значения этого узла.
Трудно понять? Не можете вспомнить? Это не имеет значения, ниже я определяю бинарное дерево поиска, давайте медленно разбираться в дереве.
Поскольку бинарное дерево поиска имеет в своем названии слово search, давайте начнем изучение бинарного дерева поиска с поиска по бинарному дереву поиска.
Найти операцию бинарного дерева поиска
Из-за особенностей бинарного дерева поиска нам нужно найти кусок данных, сначала сравнить его с ведомым узлом, если значение равно ведомому узлу, затем вернуть корневой узел, если он меньше корневого узла , он должен находиться в левом поддереве, если рекурсивно просматривается левый дочерний элемент. Подойдет дерево, если оно больше, оно находится в правом поддереве, а правое поддерево может быть рекурсивным. Таким образом, может быть достигнут быстрый поиск, потому что каждый поиск уменьшает данные наполовину, что несколько похоже на двоичный поиск.Эта функция реализует быструю вставку и удаление.
Затем мы используем динамическую диаграмму, чтобы лучше понять процесс поиска в двоичном дереве поиска.Нам нужно найти узел, значение которого равно 37 в приведенном выше двоичном дереве поиска.Давайте посмотрим, как реализована блок-схема. .
- 1. Сначала сравнить 37 с 62, 37
- 2. Значение узла левого поддерева равно 58, 37
- 3. Значение узла левого поддерева равно 47, 37
- 4. Значение узла левого поддерева равно 35, 37 > 35, поиск в правом поддереве
- 5. Значение узла в правом поддереве равно 37, 37 = 37, вернуть узел
Поговорив о концепции поиска, давайте взглянем на кодовую реализацию операции поиска бинарного дерева поиска.
/**
* 根据值查找树
* @param data 值
* @return
*/
public TreeNode find(int data) {
TreeNode p = tree;
while (p != null) {
if (data < p.data) p = p.left;
else if (data > p.data) p = p.right;
else return p;
}
return null;
}
Операция вставки бинарного дерева поиска
Вставка аналогична поиску.Он также начинается с корневого узла.Если вставляемые данные больше, чем данные узла, а правое поддерево узла пусто, новые данные будут вставлены непосредственно в позицию правый дочерний узел; если он не пуст, затем рекурсивно пройти по правому поддереву, чтобы найти позицию вставки. Аналогично, если вставляемые данные меньше значения узла, а левое поддерево узла пусто, вставляем новые данные в позицию левого подузла; если оно не пусто, то рекурсивно обходим левый подузел. поддерево, чтобы найти позицию вставки.
Предположим, мы хотим вставить 63, мы используем динамическую диаграмму, чтобы увидеть процесс вставки.
- 1. 63 > 62, продолжить поиск в правом поддереве дерева.
- 2. 63
- 3. 63
Давайте посмотрим на код реализации операции вставки бинарного дерева поиска.
/**
* 插入树
* @param data
*/
public void insert(int data) {
if (tree == null) {
tree = new TreeNode(data);
return;
}
TreeNode p = tree;
while (p != null) {
// 如果值大于节点的值，则新树为节点的右子树
if (data > p.data) {
if (p.right == null) {
p.right = new TreeNode(data);
return;
}
p = p.right;
} else { // data < p.data
if (p.left == null) {
p.left = new TreeNode(data);
return;
}
p = p.left;
}
}
}
Удалить операцию бинарного дерева поиска
Логика удаления сложнее поиска и вставки, есть три случая удаления:
первый случай: если у удаляемого узла нет дочерних узлов, нам нужно только напрямую установить указатель на удаляемый узел в родительском узле равным нулю. Например, удалите узел 51 на рисунке.
второй случай: Если удаляемый узел имеет только один дочерний узел (только левый дочерний узел или правый дочерний узел), нам нужно только обновить указатель на удаляемый узел в родительском узле, чтобы он указывал на дочерний узел. узел узла, который необходимо удалить. Например, удалите узел 35 на рисунке.
третий случай: Это сложнее, если удаляемый узел имеет двух дочерних узлов. Нам нужно найти наименьший узел в правом поддереве этого узла и заменить его удаляемым узлом. Затем удалите наименьший узел, потому что у наименьшего узла не должно быть левого дочернего узла (если есть левый дочерний узел, это не самый маленький узел), поэтому мы можем применить два вышеуказанных правила для удаления этого наименьшего узла. Например, удалите узел 88 на рисунке.
Первые два случая немного проще, а в третьем случае я сделал динамическую картинку, надеюсь она вам поможет.
Давайте посмотрим на код реализации операции удаления бинарного дерева поиска.
public void delete(int data) {
TreeNode p = tree; // p指向要删除的节点，初始化指向根节点
TreeNode pp = null; // pp记录的是p的父节点
while (p != null && p.data != data) {
pp = p;
if (data > p.data) p = p.right;
else p = p.left;
}
if (p == null) return; // 没有找到
// 要删除的节点有两个子节点
if (p.left != null && p.right != null) { // 查找右子树中最小节点
TreeNode minP = p.right;
TreeNode minPP = p; // minPP表示minP的父节点
while (minP.left != null) {
minPP = minP;
minP = minP.left;
}
p.data = minP.data; // 将minP的数据替换到p中
p = minP; // 下面就变成了删除minP了
pp = minPP;
}
// 删除节点是叶子节点或者仅有一个子节点
TreeNode child; // p的子节点
if (p.left != null) child = p.left;
else if (p.right != null) child = p.right;
else child = null;
if (pp == null) tree = child; // 删除的是根节点
else if (pp.left == p) pp.left = child;
else pp.right = child;
}
Мы узнали некоторые связанные знания о бинарном дереве поиска выше.Поскольку бинарное дерево поиска в крайних случаях вырождается в связанный список, например, каждый узел имеет только один левый узел, а временная сложность становится O(n) , чтобы избежать этой ситуации, новое дерево называетсяСбалансированное бинарное дерево поиска, Поскольку эта статья немного длинная, я считаю, что все здесь немного устали, я не буду вводить здесь соответствующие знания о сбалансированных бинарных деревьях поиска.
Наконец
Сделайте небольшую рекламу, добро пожаловать, чтобы отсканировать код и подпишитесь на общедоступную учетную запись WeChat: «Технический блог брата Пинтоу», давайте вместе добьемся прогресса.
использованная литература
- Красота структур данных и алгоритмов (время гиков)