1. Бинарное дерево — это так просто
Эта статья откладывает в сторону некоторые очень горькие и непонятные понятия, чтобы говорить о бинарных деревьях, только для ознакомительного просмотра (или обзора). …
Сначала поговорим о том, что такое дерево:
- деревонелинейныйСтруктура данных относительно линейной структуры данных (связный список, массив),Среднее время работы дерева короче (часто сложность времени сортировки, связанная с деревом, невелика)
В реальной жизни наше общее дерево выглядит так:
Но в мире программирования мы обычно смотрим на дерево «вверх ногами», что нам легко анализировать:
Общее дерево имеет много-много ветвей, а под ветвями много-много ветвей.Если изучить это в программе, то будет оченьбеда. потому что изначальноДеревья нелинейны, а наш компьютерПамять — это линейное хранилищеДа, мы не можем его спроектировать, если он слишком сложный.
Поэтому сначала изучаемпростой и часто используемый--->бинарное дерево
1.1 Некоторые концепции деревьев
Я возьму картинку выше, чтобы проиллюстрировать:
Бинарное дерево означает:Каждый узел не может иметь более двух дочерних элементов., изображение выше представляет собой бинарное дерево.
- Дерево будет иметь по крайней мере один узел (корневой узел)
-
Дерево состоит из узлов, структура данных каждого узла выглядит следующим образом:
- Поэтому, когда мы определяем дерево, часто **->определить узел->узлы соединяются, чтобы стать деревом**, и определение узла:Одни данные, два указателя (указывают на узел, если узел есть, указывают на ноль, если узла нет)
1.2 Статическое создание бинарного дерева
сказал выше,Дерево состоит из нескольких узлов, а узлы соединяются в дерево.,иУзел состоит из одних данных и двух указателей.
- следовательно,Создание дерева фактически создает узлы, а затем соединяет их.
Сначала определите узел с помощью класса Java:
public class TreeNode {
// 左节点(儿子)
private TreeNode lefTreeNode;
// 右节点(儿子)
private TreeNode rightNode;
// 数据
private int value;
}
Давайте возьмем это бинарное дерево в качестве примера для его построения:
Для облегчения построения я дал ему конструктор с параметрами и методами set и get:
public TreeNode(int value) {
this.value = value;
}
Итак, мы создали 5 узлов:
public static void main(String[] args) {
//根节点-->10
TreeNode treeNode1 = new TreeNode(10);
//左孩子-->9
TreeNode treeNode2 = new TreeNode(9);
//右孩子-->20
TreeNode treeNode3 = new TreeNode(20);
//20的左孩子-->15
TreeNode treeNode4 = new TreeNode(15);
//20的右孩子-->35
TreeNode treeNode5 = new TreeNode(35)
}
Текущее их состояние следующее:
Итак, подключаем:
//根节点的左右孩子
treeNode1.setLefTreeNode(treeNode2);
treeNode1.setRightNode(treeNode3);
//20节点的左右孩子
treeNode3.setLefTreeNode(treeNode4);
treeNode3.setRightNode(treeNode5);
После завершения подключения наше дерево создано.
1.3 Обход бинарного дерева
Выше сказано, что наше дерево создано, так как же это доказать? ? мыЕсли вы можете перебирать его как массив (посмотрите на его данные), то он создан~
Стоит отметить, что:Существует три способа обхода бинарного дерева.
- обход предварительного заказа
- Сначала посетите корневой узел, затем посетите левый узел и, наконец, посетите правый узел (корень-> левый-> правый)
- Неупорядоченный обход
- Сначала посетите левый узел, затем корневой узел и, наконец, правый узел (левый-> корень-> правый)
- пост-порядковый обход
- Сначала посетите левый узел, затем посетите правый узел и, наконец, посетите корневой узел (левый->правый->корень).
Возьмем приведенное выше бинарное дерево в качестве примера:
- еслиобход предварительного заказа:
10->9->20->15->35 - еслиНеупорядоченный обход:
9->10->15->20->35- Возможно, потребуется объяснить место: после посещения 10 узлов найдены 20 узлов,Но есть дочерние узлы до 20,следовательноПервыйПосещен 15-й узел, левый сын 20-го. Так как 15-й узел не имеет сына. Итак, вернитесь к 20 узлам и посетите 20 узлов. Последнее посещение 35 узлов
- еслипост-порядковый обход:
9->15->35->20->10- Возможно, потребуется объяснить место: сначала посетить 9 узлов, затем следует посетить 20 узлов,Но есть дочерние узлы до 20,следовательноПервыйПосещен 15-й узел, левый сын 20-го. Так как 15-й узел не имеет сына. Итак, я пошел посетить узел 35. Поскольку у узла 35 нет сына, я вернулся к узлу 20 и, наконец, вернулся к узлу 10.
Краткое содержание одной фразы:Предварительный порядок (корень-> левый-> правый), средний порядок (левый-> корень-> правый), обратный порядок (левый-> правый-> корень). Если вы посещаете узел с дочерними элементами, сначала обработайте дочерние элементы, а затем верните
Независимо от обхода сначала, если обход каждого узла обращается к узлу с дочерними элементами, дочерние элементы обрабатываются первыми (логика та же самая).
- Таким образом, мы можем легко думать орекурсия
- Восстановление экспорта:Когда дочернего узла нет, верните
Следовательно, мы можем написать этоКод обхода предзаказа:
/**
* 先序遍历
* @param rootTreeNode 根节点
*/
public static void preTraverseBTree(TreeNode rootTreeNode) {
if (rootTreeNode != null) {
//访问根节点
System.out.println(rootTreeNode.getValue());
//访问左节点
preTraverseBTree(rootTreeNode.getLefTreeNode());
//访问右节点
preTraverseBTree(rootTreeNode.getRightNode());
}
}
Результат такой же, как мы только что сказали:
мы повторно используемНеупорядоченный обходПозвоните еще раз:
/**
* 中序遍历
* @param rootTreeNode 根节点
*/
public static void inTraverseBTree(TreeNode rootTreeNode) {
if (rootTreeNode != null) {
//访问左节点
inTraverseBTree(rootTreeNode.getLefTreeNode());
//访问根节点
System.out.println(rootTreeNode.getValue());
//访问右节点
inTraverseBTree(rootTreeNode.getRightNode());
}
}
Результат такой же, как мы только что сказали:
что интересно:Мы можем восстановить исходное двоичное дерево по порядку и обратному порядку или по порядку и обратному порядку., но исходное двоичное дерево не может быть восстановлено с помощью предварительного заказа и последующих действий.
- Это:Через порядок и предварительный порядок или порядок и обратный порядок мы можем определить двоичное дерево!
2. Динамически создать бинарное дерево
Мы создали двоичное дерево вручную выше.Вообще говоря, мы даем вам массив и позволяем вам превратить массив в двоичное дерево.На данный момент нам нужно динамически создать двоичное дерево.
В бинарном дереве также есть особый вид бинарного дерева:бинарное дерево поиска
- определение:Вся левая сторона текущего корневого узла меньше корневого узла, а правая сторона текущего корневого узла больше корневого узла..
- Проницательный человек увидит, что этоУзнать номер очень удобно и быстро
Часто мы динамически создаем бинарные деревья для созданиябинарное дерево поиска
2.1 Динамическое создание бинарного дерева
Предположим, у нас есть массив:int[] arrays = {3, 2, 1, 4, 5};
Затем шаги для создания бинарного дерева следующие:
- Сначала сделайте 3 корневым узлом
- Затем приходит 2, мы сравниваем его с 3, он меньше 3, затем ставим его слева от 3
- Затем приходит 1, мы сравниваем ее с 3, она меньше 3, затем помещаем ее слева от 3, теперь слева от 3 находится 2, поэтому по сравнению с 2 она меньше 2, и поставить его слева от 2
- Затем приходит число 4, мы сравниваем его с числом 3, оно больше, чем число 3, и помещаем его справа от числа 3.
- Затем входит 5, мы сравниваем его с 3, оно больше 3, затем помещаем его справа от 3, теперь справа от 3 находится 4, поэтому оно больше 4, и оно помещается на правая сторона 4
Тогда наше бинарное дерево поиска успешно установлено,Независимо от любого поддерева, левая сторона меньше корня, а правая сторона больше корня.
2.2 Реализация кода
Наша реализация кода также очень проста,Если он меньше текущего корневого узла, поместите его слева от текущего корневого узла, если он больше текущего корневого узла, то поместите его справа от текущего корневого узла.
Поскольку он создается динамически, мы должны использовать класс для представления корневого узла.
public class TreeRoot {
private TreeNode treeRoot;
public TreeNode getTreeRoot() {
return treeRoot;
}
public void setTreeRoot(TreeNode treeRoot) {
this.treeRoot = treeRoot;
}
}
Сравните с корнем, который больше, больший идет вправо, а меньший идет влево:
/**
* 动态创建二叉查找树
*
* @param treeRoot 根节点
* @param value 节点的值
*/
public static void createTree(TreeRoot treeRoot, int value) {
//如果树根为空(第一次访问)，将第一个值作为根节点
if (treeRoot.getTreeRoot() == null) {
TreeNode treeNode = new TreeNode(value);
treeRoot.setTreeRoot(treeNode);
} else {
//当前树根
TreeNode tempRoot = treeRoot.getTreeRoot();
while (tempRoot != null) {
//当前值大于根值，往右边走
if (value > tempRoot.getValue()) {
//右边没有树根，那就直接插入
if (tempRoot.getRightNode() == null) {
tempRoot.setRightNode(new TreeNode(value));
return ;
} else {
//如果右边有树根，到右边的树根去
tempRoot = tempRoot.getRightNode();
}
} else {
//左没有树根，那就直接插入
if (tempRoot.getLefTreeNode() == null) {
tempRoot.setLefTreeNode(new TreeNode(value));
return;
} else {
//如果左有树根，到左边的树根去
tempRoot = tempRoot.getLefTreeNode();
}
}
}
}
}
Тестовый код:
int[] arrays = {2, 3, 1, 4, 5};
//动态创建树
TreeRoot root = new TreeRoot();
for (int value : arrays) {
createTree(root, value);
}
//先序遍历树
preTraverseBTree(root.getTreeRoot());
System.out.println("---------------公众号：Java3y");
//中序遍历树
inTraverseBTree(root.getTreeRoot());
System.out.println("---------------公众号：Java3y");
В-третьих, запрос корреляции бинарного дерева поиска
3.1 Глубина дерева запросов
Глубину дерева запросов можно представить следующим образом:Отношение поддерева слева к количеству слов справа, кто больше, тот кому и вернется, то соедините корневой узел +1.
public static int getHeight(TreeNode treeNode) {
if (treeNode == null) {
return 0;
} else {
//左边的子树深度
int left = getHeight(treeNode.getLefTreeNode());
//右边的子树深度
int right = getHeight(treeNode.getRightNode());
int max = left;
if (right > max) {
max = right;
}
return max + 1;
}
}
3.1 Максимальное значение дерева запросов
При обходе бинарного дерева поиска из приведенного выше предварительного порядка внимательные учащиеся могут обнаружить:Результат неупорядоченного обхода бинарного дерева поиска находится в отсортированном порядке~
Тогда, если наше бинарное дерево не является бинарным деревом поиска, мы имеемКак проверить его максимальное значение??
Это можно сделать следующим образом:
- Найдите максимальное значение слева -> рекурсия
- Найдите максимальное значение справа -> рекурсия
/**
* 找出树的最大值
*
* @param rootTreeNode
*/
public static int getMax(TreeNode rootTreeNode) {
if (rootTreeNode == null) {
return -1;
} else {
//找出左边的最大值
int left = getMax(rootTreeNode.getLefTreeNode());
//找出右边的最大值
int right = getMax(rootTreeNode.getRightNode());
//与当前根节点比较
int currentRootValue = rootTreeNode.getValue();
//假设左边的最大
int max = left;
if (right > max) {
max = right;
}
if (currentRootValue > max) {
max = currentRootValue;
}
return max ;
}
}
Четвертый, последний
Рекурсия используется независимо от того, проходит ли она по дереву, находит глубину или находит максимальное значение.Рекурсия часто используется в нелинейных структурах данных....
Применение дерева также очень обширно. В этой статье кратко объясняется структура данных дерева. Я не понимаю сложных вещей. Может быть, я продолжу углубляться, когда буду использовать его позже...
Если в статье есть какие-либо ошибки, пожалуйста, поправьте меня, и мы сможем общаться друг с другом. Учащиеся, привыкшие читать технические статьи в WeChat и желающие получить больше ресурсов по Java, могутОбратите внимание на публичный аккаунт WeChat: Java3y