Реализация двоичного дерева в Java

Первоначально опубликовано в моем личном блоге 27 января 2020 года.

Подробнее в серии о структурах данных.

Узнав, как реализовать стек, различные типы связанных списков и даже хеш-карту в Java, сегодня мы увидим, как мы можем построить собственное двоичное дерево на Java. Подобно другим структурам данных, о которых мы говорили, у нас также есть узел. Он очень похож на узел в двойном связанном списке (DLL), но вместо предыдущего и следующего указателя в DLL у нас есть левый и правый указатели в двоичном дереве. Это связано с тем, что двоичное дерево будет иметь максимум двух дочерних элементов, один слева, а другой справа от узла. Опять же, как и в других сообщениях о структурах данных, которые я написал, я не собираюсь объяснять, что такое двоичное дерево и как оно работает. Мы сразу приступим к реализации. Итак, приступим.

Двоичное дерево

Прежде чем мы начнем с кода, нам нужно иметь справочное дерево, чтобы понимать код и проверять вывод кода. Также гораздо легче понять функционирование дерева, если у нас есть пример для работы. Итак, это как раз то, что мы собираемся сделать. Я выполнил болезненную задачу, придумав иллюстративную диаграмму для этого поста, и вот она:

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

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

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

В обходе перед заказом мы «посещаем» узел перед посещением его дочерних узлов. Итак, порядок будет таким:

Узел - ›Левый дочерний элемент -› Правый дочерний элемент

В нашем примере результат обхода предварительного заказа таков:

1 2 4 5 3 6 7

Для обхода

Как следует из названия, при обходе по порядку мы сохраняем естественный порядок обхода слева направо. Итак, порядок такой:

Левый дочерний элемент - ›Узел -› Правый дочерний элемент

В нашем примере результат обхода по порядку таков:

4 2 5 1 6 3 7

Обход почтового заказа

В обходе почтового заказа узел идет после дочерних элементов. Итак, мы сначала посещаем левого дочернего элемента, затем правого дочернего элемента, а затем узла, как показано ниже:

Левый дочерний элемент - ›Правый дочерний элемент -› Узел

В нашем примере результат обхода почтового заказа следующий:

4 5 2 6 7 3 1

В нашем коде мы попытаемся реализовать эти три типа обходов.

Код

Как обычно, сначала мы увидим класс Node.

public class Node<T> {

    private T data;
    private Node<T> left;
    private Node<T> right;

    public Node() {}

    public Node(T value) { this.data = value; }

    public T getData() {
        return data;
    }

    public void setData(T data) {
        this.data = data;
    }

    public Node<T> getLeft() {
        return left;
    }

    public void setLeft(Node<T> left) {
        this.left = left;
    }

    public Node<T> getRight() {
        return right;
    }

    public void setRight(Node<T> right) {
        this.right = right;
    }
}

Как я упоминал ранее, у нас есть левый и правый указатели, указывающие на левого потомка и правого потомка. Мы используем этот класс Node как основу нашего класса BinaryTree. Определение класса двоичного дерева выглядит так:

public class BinaryTree<T> {
    
    private Node<T> rootNode;

    public Node<T> getRootNode() {
        return rootNode;
    }

    public void setRootNode(Node<T> rootNode) {
        this.rootNode = rootNode;
    }

}

Теперь мы добавляем методы обхода. Убедитесь, что вы помните, как работает каждый обход. Для этих методов обхода мы собираемся использовать рекурсию, то есть вызывать метод изнутри самого метода. Мы делаем это, потому что нам нужно пройти по дереву до самого низа в том же порядке, в каком оно представлено. Итак, сначала давайте посмотрим на обход предварительного заказа.

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

public static void traversePreOrder(Node node) {

    System.out.print(node.getData() + " ");

    if (node.getLeft() != null) {
        traversePreOrder(node.getLeft());
    }

    if (node.getRight() != null) {
        traversePreOrder(node.getRight());
    }
}

Как видите, мы сначала печатаем значение узла, затем переходим к левому узлу и, наконец, переходим прямо сейчас. Таким образом, текущий узел идет первым, следовательно, pre в обходе предварительного заказа. В первой итерации этого вызова функции мы передадим корневой узел в качестве аргумента. Таким образом, сначала «посещается» корневой узел, а затем все левые дочерние элементы корневых узлов посещаются в предварительном порядке. Результат этой функции будет следующим:

1 2 4 5 3 6 7

Для обхода

В порядке обхода, как я уже объяснил, будет в естественном порядке слева направо. Вот код для этого:

public static void traverseInOrder(Node node) {

    if (node.getLeft() != null) {
        traverseInOrder(node.getLeft());
    }

    System.out.print(node.getData() + " ");

    if (node.getRight() != null) {
        traverseInOrder(node.getRight());
    }
}

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

4 2 5 1 6 3 7

Обход почтового заказа

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

public static void traversePostOrder(Node node) {

    if (node.getLeft() != null) {
        traversePostOrder(node.getLeft());
    }

    if (node.getRight() != null) {
        traversePostOrder(node.getRight());
    }

    System.out.print(node.getData() + " ");
}

Мы получим следующий результат для обхода почтового заказа:

4 5 2 6 7 3 1

Полный класс BinaryTree выглядит так:

public class BinaryTree<T> {
    
    private Node<T> rootNode;

    public Node<T> getRootNode() {
        return rootNode;
    }

    public void setRootNode(Node<T> rootNode) {
        this.rootNode = rootNode;
    }
    
    public static void traverseInOrder(Node node) {

        if (node.getLeft() != null) {
            traverseInOrder(node.getLeft());
        }

        System.out.print(node.getData() + " ");

        if (node.getRight() != null) {
            traverseInOrder(node.getRight());
        }
    }

    public static void traversePreOrder(Node node) {

        System.out.print(node.getData() + " ");

        if (node.getLeft() != null) {
            traversePreOrder(node.getLeft());
        }

        if (node.getRight() != null) {
            traversePreOrder(node.getRight());
        }
    }

    public static void traversePostOrder(Node node) {

        if (node.getLeft() != null) {
            traversePostOrder(node.getLeft());
        }

        if (node.getRight() != null) {
            traversePostOrder(node.getRight());
        }

        System.out.print(node.getData() + " ");
    }
}

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

Тестирование

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

BinaryTree<Integer> binaryTree = new BinaryTree<>();
Node<Integer> rootNode = new Node<>(1);
binaryTree.setRootNode(rootNode);

После настройки корневого узла мы можем начать добавлять потомков к корневому узлу следующим образом:

binaryTree.getRootNode().setLeft(new Node<>(2)); binaryTree.getRootNode().setRight(new Node<>(3));

Затем мы начнем добавлять дополнительные узлы к этим двум узлам следующим образом:

binaryTree.getRootNode().getLeft().setLeft(new Node<>(4));
binaryTree.getRootNode().getLeft().setRight(new Node<>(5));

binaryTree.getRootNode().getRight().setLeft(new Node<>(6));
binaryTree.getRootNode().getRight().setRight(new Node<>(7));

Это полный код для создания двоичного дерева, которое я представил на иллюстрации в начале этого поста. Теперь давайте посмотрим, как пройти по этому дереву:

System.out.println("Pre order traversing:");
BinaryTree.traversePreOrder(binaryTree.getRootNode());
System.out.println();

System.out.println("In order traversing:");
BinaryTree.traverseInOrder(binaryTree.getRootNode());
System.out.println();

System.out.println("Post order traversing:");
BinaryTree.traversePostOrder(binaryTree.getRootNode());
System.out.println();

Это довольно просто. Вывод этого кода выглядит следующим образом:

Pre order traversing:
1 2 4 5 3 6 7 
In order traversing:
4 2 5 1 6 3 7 
Post order traversing:
4 5 2 6 7 3 1

Перемещение работает так, как мы и ожидали. Итак, мы закончили.

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

Реализация двоичного дерева в Java

Двоичное дерево

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

Для обхода

Обход почтового заказа

Код

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

Для обхода

Обход почтового заказа

Тестирование

Вопросы по теме