Все о деревьях в структурах данных (Java Edition)

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

Рисунок деревьев, который я рисовал, когда был маленьким мальчиком.

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

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

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

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

• Что такое дерево?
• Пример простого дерева
• Терминология дерева и как это работает
• Как реализовать древовидную структуру в коде

определение

При обучении программированию нам легче понять линейные структуры данных, а не древовидные и графовые структуры данных.

Деревья — это хорошо известные нелинейные структуры данных. Они не хранят данные линейным образом. Они организуют данные иерархически.

Возьмем пример из жизни

Что именно мы подразумеваем под иерархической организацией?

Представьте себе наше генеалогическое древо: бабушки и дедушки, родители, дети, братья и сестры и т. д. Обычно мы организуем генеалогическое древо в виде иерархии.

мое генеалогическое древо

На картинке выше мое генеалогическое древо. тосико, акикадзу, хитоми и такеми — мои бабушка и дедушка.

Тошиаки и Джулиана — мои родители.

ТК, Юдзи, Бруно и Кайо — дети моих родителей (я и мои братья).

Другим примером иерархии является организационная структура бизнеса.

Структура компании также является примером иерархии.

В HTML объектная модель документа (DOM) имеет древовидную структуру.

Объектная модель документа (DOM)

Теги HTML содержат другие теги. У нас есть тег head и тег body. Эти теги содержат характерные элементы. В теге head есть метатеги и теги title. Тег body содержит теги, отображаемые в пользовательском интерфейсе, такие как h1, a, li и так далее.

древовидная терминология

Дерево(tree) называется узлом (node) сущностей. Узлы проходят через ребра (edge)соединять. Каждый узел содержит значение или данные (value/date), и каждый узел может иметь или не иметь дочерних узлов.

Первый узел дерева называется корневым узлом (т.е.rootУзел). Если этот корневой узел соединен с другими узлами, то корневой узел является родительским узлом (parent node, связанный с корневым узлом, является дочерним узлом (child node).

Все узлы проходят через ребра (edge)соединять. Это важное понятие в дереве, поскольку оно отвечает за управление отношениями между узлами.

листовой узел (leaves) являются концами дерева, у них нет потомков. Как и у настоящего большого дерева, мы можем видеть, что у дерева есть корни, ветви и листья.

высота дерева (height) и глубина (depth)

• Высота дерева — это длина до листового узла (конец дерева).
• Глубина узла — это его длина до корня.

Резюме терминов

• Корневой узел — это самый верхний узел дерева
• Ребро — это соединение между двумя узлами
• Дочерний узел — это узел, у которого есть родитель
• Родительский узел — это узел, который связан с дочерним узлом.
• Листовой узел — это узел в дереве, у которого нет дочерних узлов (конец дерева).
• Высота — это длина от дерева до конечного узла (конец дерева).
• Глубина - длина от узла к корневому узлу

бинарное дерево

Теперь давайте обсудим специальный тип дерева. Мы называем это бинарным деревом.

«В информатике бинарное дерево — это древовидная структура данных, в которой каждый узел имеет не более двух дочерних элементов, называемых левыми и правыми дочерними элементами» — Wikipedia

Напишем бинарное дерево

Когда мы собираемся реализовать бинарное дерево, первое, что нам нужно помнить, это то, что это набор узлов. Каждый узел имеет три свойства:value,left_child``和right_child.

Итак, как мы достигаем простого бинарного дерева три атрибуты это?

Давайте реализуем пример бинарного дерева

/**
 * Created on 2018/4/16.
 *
 * @author zlf
 * @since 1.0
 */
public class BinaryTree {

    public BinaryTree left; //左节点

    public BinaryTree right; //右节点

    public String data;  //树的内容

    public BinaryTree() {
    }

    /**
     * 构造方法
     *
     * @param data
     * @param left
     * @param right
     */
    public BinaryTree(String data, BinaryTree left, BinaryTree right) {
        this.left = left;
        this.right = right;
        this.data = data;
    }

    /**
     * 构造方法
     *
     * @param data
     */
    public BinaryTree(String data) {
        this(data, null, null);
    }

Хорошо, это наш класс бинарного дерева.

Когда мы создаем экземпляр объекта, мы передаем значение (данные о точке) в качестве параметра классу. Посмотрите на левый дочерний узел и правый дочерний узел класса выше. Оба имеют значение null.

Зачем?

Потому что, когда мы создаем узел, у него еще нет дочерних элементов, только данные узла.

проверка кода

   /**
     * 构建树
     */
    public static void testCreate() {
        BinaryTree node = new BinaryTree("a");

        System.out.println("【node data】:" + node.getData());
        System.out.println("【node left data】:" + (node.left==null?"null":node.left.getData()));
        System.out.println("【node right data】:" + (node.right==null?"null":node.right.getData()));
    }

вывод:

【node data】:a
【node left data】:null
【node right data】:null

Мы можем пройти строку «A» в качестве аргумента на бинарный узел дерева. Если мы выводим значение, узел левого дочернего ребенка и правый дочерний узел, мы можем увидеть значение.

Приступим к операции вставки детали. Итак, что нам нужно сделать?

Есть два требования:

• Если у текущего узла нет левого дочернего элемента, мы создаем новый узел и устанавливаем его слева от текущего узла.

• Если левый узел уже есть, мы создаем новый узел и помещаем его в позицию текущего левого узла. Затем установите исходный левый узел в качестве левого узла нового левого узла.

График выглядит следующим образом:

Вот вставленный код:

 /**
     * 插入节点 ，如果当前的节点没有左节点，我们就创建一个新节点，然后将其设置为当前节点的左节点。
     *
     * @param node
     * @param value
     */
    public static void insertLeft(BinaryTree node, String value) {
        if (node != null) {
            if (node.left == null) {
                node.setLeft(new BinaryTree(value));
            } else {
                BinaryTree newNode = new BinaryTree(value);
                newNode.left = node.left;
                node.left = newNode;
           }
        } 
    }

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

Точно так же мы пишем код для вставки правильного узла

/**
    * 同插入左结点
    * @param node
    * @param value
    */
   public static void insertRight(BinaryTree node, String value) {
       if (node != null) {
           if (node.right == null) {
               node.setRight(new BinaryTree(value));
           } else {
               BinaryTree newNode = new BinaryTree(value);
               newNode.right = node.right;
               node.right = newNode;
           }
       } 
   }

Но это еще не сделано. Мы должны это проверить.

Построим такое дерево:

• имеет корневой узел
• b — левый узел
• c - правый узел
• Узел b равен d (у b нет левого узла)
• Левый узел c равен e
• Правый узел c равен f
• И e, и f не имеют дочерних узлов

Вот код реализации для этого дерева:

/**
     * 测试插入结点
     */
    public static void testInsert() {
        BinaryTree node_a = new BinaryTree("a");
        node_a.insertLeft(node_a, "b");
        node_a.insertRight(node_a, "c");

        BinaryTree node_b = node_a.left;
        node_b.insertRight(node_b, "d");

        BinaryTree node_c = node_a.right;
        node_c.insertLeft(node_c, "e");
        node_c.insertRight(node_c, "f");

        BinaryTree node_d = node_b.right;
        BinaryTree node_e = node_c.left;
        BinaryTree node_f = node_c.right;

        System.out.println("【node_a data】:" + node_a.getData());
        System.out.println("【node_b data】:" + node_b.getData());
        System.out.println("【node_c data】:" + node_c.getData());
        System.out.println("【node_d data】:" + node_d.getData());
        System.out.println("【node_e data】:" + node_e.getData());
        System.out.println("【node_f data】:" + node_f.getData());
    }

вывод:

【node_a data】:a
【node_b data】:b
【node_c data】:c
【node_d data】:d
【node_e data】:e
【node_f data】:f

Вставка завершена

Теперь рассмотрим обход дерева.

Существует два варианта обхода дерева: поиск в глубину (DFS) и поиск в ширину (BFS).

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

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

Ниже мы подробно рассмотрим каждый из алгоритмов обхода.

Поиск в глубину (DFS)

DFS находит путь к конечному узлу перед возвратом и поиском других путей. Давайте посмотрим на пример этого типа обхода.

Выход: 1-2-3-4-5-6-7

Зачем?

Давайте разберем это:

1. Начните с корневого узла (1). вывод
2. Войдите в левый узел (2). вывод
3. Затем перейдите к левому ребенку (3). вывод
4. Вернитесь и идите к правому ребенку (4). вывод
5. 回溯到根结点，然后进入其右孩子（5）。 вывод
6. Введите левого дочернего элемента (6). вывод
7. Вернитесь и идите к правому ребенку (7). вывод
8. Заканчивать

Возврат, когда мы углубляемся в конечные узлы, называется алгоритмом DFS.

Теперь, когда мы знакомы с этим алгоритмом обхода, мы обсудим типы DFS: предварительный порядок, порядок и постпорядок.

обход предварительного заказа

Это в основном похоже на то, что мы сделали в примере выше.

1. Значение выходного узла
2. Введите его левый узел и выведите. тогда и только тогда, когда он имеет левый узел.
3. Введите правильный узел и выведите его. тогда и только тогда, когда он имеет правый узел

/**
     * 前序遍历
     *
     * @param node
     */
    public static void preOrder(BinaryTree node) {
        if (node != null) {

            System.out.println(node.data);

            if (node.left != null) {
                node.left.preOrder(node.left);
            }

            if (node.right != null) {
                node.right.preOrder(node.right);
            }
        }
    }

Неупорядоченный обход

Результат алгоритма упорядочения для этого дерева в примере равен 3–2–4–1–6–5–7.

Сначала левый узел, затем средний и, наконец, правый узел.

Код:

/**
     * 中序遍历
     *
     * @param node
     */
    public static void inOrder(BinaryTree node) {
        if (node != null) {
            if (node.left != null) {
                node.left.inOrder(node.left);
            }

            System.out.println(node.data);

            if (node.right != null) {
                node.right.inOrder(node.right);
            }
        }
    }

1. Введите левый узел и выведите его. тогда и только тогда, когда он имеет левый узел.
2. Выведите значение корневого узла.
3. Введите узел node и выведите его. тогда и только тогда, когда он имеет узловой узел.

пост-порядковый обход

Результат алгоритма обратного порядка для этого дерева в качестве примера: 3–4–2–6–7–5–1.

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

Код:

/**
     * 后序遍历
     *
     * @param node
     */
    public static void postOrder(BinaryTree node) {
        if (node != null) {
            if (node.left != null) {
                node.left.postOrder(node.left);
            }

            if (node.right != null) {
                node.right.postOrder(node.right);
            }

            System.out.println(node.data);
        }
    }

1. Введите выход левого узла,
2. Введите правильный вывод узла
3. выходной корневой узел

Поиск в ширину (BFS)

BFS — это алгоритм обхода, который постепенно углубляется слой за слоем.

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

Пройдемся по дереву слой за слоем. В данном случае это 1-2-5-3-4-6-7.

• Слой 0/0 Глубина: Значение узла 1 Только
• Слой 1/Глубина 1:2 и имеет значение узла 5
• 2 слоя/глубина 2: узлы со значениями 3, 4, 6, 7

Код:

/**
     * 广度排序
     *
     * @param node
     */
    public static void bfsOrder(BinaryTree node) {
        if (node != null) {
            Queue<BinaryTree> queue = new ArrayDeque<BinaryTree>();
            queue.add(node);

            while (!queue.isEmpty()) {
                BinaryTree current_node = queue.poll();

                System.out.println(current_node.data);

                if (current_node.left != null) {
                    queue.add(current_node.left);
                }
                if (current_node.right != null) {
                    queue.add(current_node.right);
                }
            }
        }
    }

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

Для чего именно используется очередь?

Пожалуйста, смотрите объяснение ниже.

1. Сначала добавьте корневой узел в очередь с помощью способа «Добавить».
2. Выполняется, когда очередь не пуста.
3. Получить первый узел в очереди и вывести его значение
4. Добавить левый и правый узлы в очередь
5. С помощью очереди мы выводим значение каждого узла слой за слоем

бинарное дерево поиска

Двоичное дерево поиска иногда называют двоичным упорядоченным деревом или двоичным отсортированным деревом.Значения двоичного дерева поиска хранятся в упорядоченном порядке, так что таблицы поиска и другие операции могут использовать принцип половинного поиска. -Википедия

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

• является обратным бинарным деревом поиска. Поддерево 7-5-8-6 должно быть справа, а поддерево 2-1-3 должно быть слева.
• единственный правильный вариант. Он удовлетворяет свойству бинарного дерева поиска
• Есть проблема: узел со значением 4 должен быть слева от корневого узла, потому что значение этого узла меньше, чем значение 5 корневого узла.

Код для реализации поиска по бинарному дереву

Insert: добавить новый узел в наше дерево

Теперь представьте, что у нас есть пустое дерево, и мы хотим добавить в это пустое дерево несколько узлов со значениями: 50, 76, 21, 4, 32, 100, 64, 52.

Первое, что нам нужно знать, это является ли 50 корневым узлом этого дерева.

Теперь начинаем вставлять узлы один за другим

• 76 больше, чем 50, поэтому 76 вставляется справа.
• 21 меньше 50, поэтому 21 вставляется слева.
• 4 меньше 50. Но у 50 уже есть левый узел со значением 21. Опять же, 4 меньше 21, поэтому вставьте его слева от 21.
• 32 меньше 50. Но у 50 уже есть левый узел со значением 21. Опять же, 32 больше, чем 21, поэтому вставьте его справа от 21.
• 100 больше, чем 50. Но у 50 уже есть правильный узел со значением 76. Опять же, 100 больше, чем 76, поэтому вставьте его справа от 76.
• 64 больше 50. Но у 50 уже есть правильный узел со значением 76. Опять же, 64 меньше 76, поэтому вставьте его слева от 76.
• 52 больше, чем 50. Но у 50 уже есть правильный узел со значением 76. 52 снова меньше, чем 76, но 76 также имеет левый узел со значением 64. 52 также меньше, чем 64, поэтому вставьте 52 слева от 64.

Вы заметили здесь закономерность?

Давайте сломаем это.

1. Является ли новое значение узла больше или меньше значения текущего узла?
2. Если значение нового узла больше текущего узла, перейдите к правому узлу. Если текущий узел не имеет правого узла, вставьте туда новый узел, в противном случае вернитесь к шагу 1.
3. Если значение нового узла меньше текущего узла, перейти к левому узлу. Если текущий узел не имеет левого узла, вставьте туда новый узел, в противном случае вернитесь к шагу 1.
4. Здесь мы не имеем дело с особыми обстоятельствами. Когда значение нового узла к узлу текущего значения, правило использования 3. Рассмотрим равные значения, вставленные в левый узел дочернего ребенка.

Код:

/**
     * 插入树
     *
     * @param node
     * @param value
     */
    public void insertNode(BinaryTree node, Integer value) {
        if (node != null) {
            if (value <= Integer.valueOf(node.data) && node.left != null) {
                node.left.insertNode(node.left, value);
            } else if (value <= Integer.valueOf(node.data)) {
                node.left = new BinaryTree(String.valueOf(value));
            } else if (value > Integer.valueOf(node.data) && node.right != null) {
                node.right.insertNode(node.right, value);
            } else {
                node.right = new BinaryTree(String.valueOf(value));
            }
        }
    }

Это выглядит достаточно просто.

Сила этого алгоритма в его рекурсивной части, строки 9 и 13. Обе строки кода вызывают метод insertNode и используют его для своих левого и правого узлов соответственно. Строки 11 и 15 вставляют новые узлы в дочерние узлы.

узел поиска

Алгоритм, который мы сейчас создадим, касается поиска. Для заданного значения (целого числа) мы ищем наше двоичное дерево поиска с этим значением или без него.

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

Давайте посмотрим на пример.

Предположим, у нас есть это дерево.

Теперь мы хотим узнать, есть ли узел со значением 52.

Давайте сломаем это.

1. Мы начинаем с корневого узла в качестве текущего узла. Заданное значение меньше текущего значения узла? Если да, то я поищу его в левом поддереве.
2. Заданное значение больше, чем текущее значение узла? Если это так, то мы будем искать его в правом поддереве.
3. Если оба правила №1 и №2 ложны, мы можем сравнить текущее значение узла и заданное значение на равенство. Если он возвращает true, то мы можем сказать: «Да, наше дерево имеет заданное значение», иначе мы говорим: «Нет, наше дерево не имеет заданного значения».

Код:

/**
     * 查找节点是否存在
     *
     * @param node
     * @param value
     * @return
     */
    public boolean findNode(BinaryTree node, Integer value) {
        if (node != null) {
            if (value < Integer.valueOf(node.data) && node.left != null) {
                return node.left.findNode(node.left, value);
            }
            if (value > Integer.valueOf(node.data) && node.right != null) {
                return node.right.findNode(node.right, value);
            }
            return value == Integer.valueOf(node.data);
        }
        return false;
    }

Анализ кода:

• Строки 8 и 9 подпадают под правило №1.
• Строки 10 и 11 относятся к правилу №2.
• Строка 13 подпадает под правило №3.

удалить: удалить и реорганизовать дерево

Удаление — более сложный алгоритм, потому что нам нужно обрабатывать разные ситуации. Для данного значения нам нужно удалить узлы с этим значением. Представьте себе следующий сценарий для этого узла: у него нет дочерних элементов, есть один дочерний элемент или два дочерних элемента.

Узел без дочерних элементов (листовой узел).

#        |50|                              |50|
#      /      \                           /    \
#    |30|     |70|   (DELETE 20) --->   |30|   |70|
#   /    \                                \
# |20|   |40|                             |40|

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

Только один дочерний узел (левый или правый дочерний).

#        |50|                              |50|
#      /      \                           /    \
#    |30|     |70|   (DELETE 30) --->   |20|   |70|
#   /            
# |20|

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

Узел с двумя детьми.

#        |50|                              |50|
#      /      \                           /    \
#    |30|     |70|   (DELETE 30) --->   |40|   |70|
#   /    \                             /
# |20|   |40|      

Когда у узла есть два потомка, вам нужно найти узел с наименьшим значением, начиная с правого потомка узла. Мы поместим узел с наименьшим значением на позицию удаленного узла.

Код:

    /**
     * 删除节点
     * @param node
     * @param value
     * @param parent
     * @return
     */
    public boolean removeNode(BinaryTree node, Integer value, BinaryTree parent) {
        if (node != null) {
            if (value < Integer.valueOf(node.data) && node.left != null) {
                return node.left.removeNode(node.left, value, node);
            } else if (value < Integer.valueOf(node.data)) {
                return false;
            } else if (value > Integer.valueOf(node.data) && node.right != null) {
                return node.right.removeNode(node.right, value, node);
            } else if (value > Integer.valueOf(node.data)) {
                return false;
            } else {
                if (node.left == null && node.right == null && node == parent.left) {
                    parent.left = null;
                    node.clearNode(node);
                } else if (node.left == null && node.right == null && node == parent.right) {
                    parent.right = null;
                    node.clearNode(node);
                } else if (node.left != null && node.right == null && node == parent.left) {
                    parent.left = node.left;
                    node.clearNode(node);
                } else if (node.left != null && node.right == null && node == parent.right) {
                    parent.right = node.left;
                    node.clearNode(node);
                } else if (node.right != null && node.left == null && node == parent.left) {
                    parent.left = node.right;
                    node.clearNode(node);
                } else if (node.right != null && node.left == null && node == parent.right) {
                    parent.right = node.right;
                    node.clearNode(node);
                } else {
                    node.data=String.valueOf(node.right.findMinValue(node.right));
                    node.right.removeNode(node.right,Integer.valueOf(node.right.data),node);
                }
                return true;
            }
        }
        return false;
    }

1. Первое: обратите внимание на параметрыvalueиparent. Мы хотим найти значение, равное этомуvalueизnode, иnodeродительский узел для удаленияnodeявляется решающим.
2. Второе: обратите внимание на возвращаемое значение. Наш алгоритм вернет логическое значение. Наш алгоритм возвращается, когда узел найден и удаленtrue. в противном случае вернутьсяfalse.
3. Строки со 2 по 9: мы начинаем искать данное, равное тому, что мы ищемvalueизnode. еслиvalueменьше, чемcurrent nodeзначение, мы входим в левое поддерево и действуем рекурсивно (тогда и только тогда, когдаcurrent nodeОставил детей). Если значение больше, процесс переходит к правому поддереву. Рекурсивная обработка.
4. Строка 10: Мы начинаем думать об алгоритме удаления.
5. Строки с 11 по 13: мы имеем дело с узлами, которые не имеют дочерних узлов и являются левым дочерним элементом родительского узла. Мы удаляем узел, устанавливая для левого дочернего элемента родительского узла значение null.
6. Строки 14 и 15: мы имеем дело с узлами, которые не имеют дочерних узлов и являются правым дочерним элементом родительского узла. Мы удаляем узел, устанавливая для правого потомка родительского узла значение null.
7. Как очистить узел: код для очистки узла я приведу в следующей статье. Эта функция устанавливает левый дочерний элемент узла, правый дочерний элемент и значение null.
8. Строки с 16 по 18: мы имеем дело с узлами, у которых есть только один дочерний элемент (левый дочерний элемент), и это левый дочерний элемент своего родителя. Мы устанавливаем левого дочернего элемента родителя как левого дочернего элемента текущего узла (который является единственным дочерним элементом, который у него есть).
9. Строки с 19 по 21: мы имеем дело с узлами, у которых есть только один дочерний элемент (левый дочерний элемент), и он является правым дочерним элементом своего родителя. Мы устанавливаем правый дочерний элемент родительского узла в качестве левого дочернего элемента текущего узла (который является единственным дочерним элементом, который у него есть).
10. Строки с 22 по 24: мы имеем дело с узлами, у которых есть только один дочерний элемент (правый дочерний элемент) и которые являются левыми дочерними элементами своего родителя. Мы устанавливаем левый дочерний элемент родительского узла правым дочерним элементом текущего узла (который является его единственным дочерним элементом).
11. Строки с 25 по 27: мы имеем дело с узлами, у которых есть только один дочерний элемент (правильный дочерний элемент), и это правильный дочерний элемент своего родителя. Мы устанавливаем правый дочерний элемент родительского узла в качестве правого дочернего элемента текущего узла (который является его единственным дочерним элементом).
12. Строки с 28 по 30: мы имеем дело с узлами, у которых есть как левые, так и правые дочерние элементы. Мы получаем узел с наименьшим значением (код будет указан позже) и устанавливаем его значение в текущий узел. Удаление узла выполняется путем удаления наименьшего узла.
13. Строка 32: Если мы нашли искомый узел, нам нужно вернутьtrue. Мы обрабатываем эти случаи со строк с 11 по 31. так что возвращайся прямоtrue,Достаточно.

• Метод clear_node: установите три свойства узла как пустые — (value, left_child и right_child)

/**
     * 清空n节点
     *
     * @param node
     */
    public void clearNode(BinaryTree node) {
        node.data = null;
        node.left = null;
        node.right = null;
    }

• find_minimum_value Метод: один смотрит вниз по данному левому. Если мы не сможем найти ни одного узла, мы находим один из самых маленьких

/**
     * 查找树中最小值
     */
    public Integer findMinValue(BinaryTree node) {
        if (node != null) {
            if (node.left != null) {
                return node.left.findMinValue(node.left);
            } else {
                return Integer.valueOf(node.data);
            }
        }
        return null;
    }

Оригинальная ссылка:Everything you need to know about tree data structures

Загрузка кода:

Скачать с моего гитхаба,Все о деревьях в структурах данных (Java Edition)

рекомендуемая статья

1. Java для создания серии блокчейнов
2. Серия анализов исходного кода Spring Security
3. Серия Spring Data Jpa

---

🙂 🙂 🙂 Подписывайтесь на апплет WeChatкурс Java-архитектораСкучно по дороге на работу и обратно? Вы все еще читаете романы и новости? Не знаете, как улучшить свои навыки? Да ладно, вот нужные вам статьи по архитектуре Java, инженеры Java читают 1.5w+, чего вы ждете?