Обход бинарного дерева поиска в глубину

Обход бинарного дерева поиска делится на две основные категории: обход в глубину и обход по уровням.

Обход в глубину делится на три типа: прямой обход дерева, симметричный обход дерева и обратный обход дерева, которые соответственно:

  • 1. Прямой обход:Сначала посетите текущий узел, затем рекурсивно посетите левое и правое поддеревья по порядку.
  • 2. Симметричный обход: Сначала рекурсивно посетите левое поддерево, затем посетите сам узел, затем рекурсивно посетите правое поддерево.
  • 3. Обратный обход: Сначала рекурсивно посетите левое и правое поддеревья, затем посетите сам текущий узел.

Диаграмма результата прямого обхода:

Соответствующий пример кода:

...
// Выполнить прямой обход двоичного дерева поиска с корнем в node, рекурсивный алгоритм
private void preOrder(Node node){

    if( node != null ){
        System.out.println(node.key);
        preOrder(node.left);
        preOrder(node.right);
    }
}
...

Диаграмма результата симметричного обхода:

Соответствующий пример кода:

...
// Выполнить симметричный обход двоичного дерева поиска с корнем в node, рекурсивный алгоритм
private void inOrder(Node node){

    if( node != null ){
        inOrder(node.left);
        System.out.println(node.key);
        inOrder(node.right);
    }
}
...

Диаграмма результата обратного обхода:

Соответствующий пример кода:

...
// Выполнить обход в обратном порядке двоичного дерева поиска с корнем в node, рекурсивный алгоритм
private void postOrder(Node node){

    if( node != null ){
        postOrder(node.left);
        postOrder(node.right);
        System.out.println(node.key);
    }
}
...

Пример кода на Java

Загрузка пакета исходного кода:Скачать

Код файла src/example/binary/Traverse.java:

package example.binary;

/**
* Приоритетный обход
 */

public class Traverse<Key extends Comparable<Key>, Value>  {

    // Узлы в дереве — приватный класс; внешнему миру не нужно знать конкретную реализацию узлов двоичного дерева поиска
    private class Node {
        private Key key;
        private Value value;
        private Node left, right;

        public Node(Key key, Value value) {
            this.key = key;
            this.value = value;
            left = right = null;
        }
    }

    private Node root;  // Корневой узел
    private int count;  // Количество узлов в дереве

    // Конструктор, по умолчанию создаёт пустое двоичное дерево поиска
    public Traverse() {
        root = null;
        count = 0;
    }

    // Вернуть количество узлов в бинарном дереве поиска
    public int size() {
        return count;
    }

    // Вернуть, является ли бинарное дерево поиска пустым
    public boolean isEmpty() {
        return count == 0;
    }

    // Вставить новую пару данных (key, value) в бинарное дерево поиска
    public void insert(Key key, Value value){
        root = insert(root, key, value);
    }

    // Проверить, существует ли key в бинарном дереве поиска
    public boolean contain⟦⟧Key(Key key){
        return contain(root, key);
    }

    // Найти в бинарном дереве поиска значение, соответствующее key. Если значение не существует, вернуть null
    public Value search(⟦⟧Key key){
        return search( root , key );
    }

    // Прямой обход бинарного дерева поиска
    public void preOrder(){
        preOrder(root);
    }

    // Симметричный обход бинарного дерева поиска
    public void inOrder(){
        inOrder(root);
    }

    // Обратный обход бинарного дерева поиска
    public void postOrder(){
        postOrder(root);
    }

    //********************
    //* Вспомогательные функции для бинарного дерева поиска
    //********************

    // Вставка узла (key, value) в бинарное дерево поиска с корнем в node с использованием рекурсивного алгоритма
    // Возвращает корень двоичного дерева поиска после вставки нового узла
    private Node insert(Node node, Key key, Value value){

        if( node == null ){
            count ++;
            return new Node(key, value);
        }

        if( key.compareTo(node.key) == 0 )
            node.value = value;
        else if( key.compareTo(node.key) < 0 )
            node.left = insert( node.left , key, value);
        else    // key > node->key
            node.right = insert( node.right, key, value);

        return node;
    }

    // Проверяет, содержит ли двоичное дерево поиска с корнем в node узел со значением ключа key, используя рекурсивный алгоритм
    private boolean contain(Node node, Key key){

        if( node == null )
            return false;

        if( key.compareTo(node.key) == 0 )
            return true;
        else if( key.compareTo(node.key) < 0 )
            return contain( node.left , key );
        else // key > node->key
            return contain( node.right , key );
    }

    // Найти значение, соответствующее key, в двоичном дереве поиска с корнем в node, рекурсивный алгоритм
    // Вернуть NULL, если значение не существует
    private Value search(Node node, Key key){

        if( node == null )
            return null;

        if( key.compareTo(node.key) == 0 )
            return node.value;
        else if( key.compareTo(node.key) < 0 )
            return search( node.left , key );
        else // key > node->key
            return search( node.right, key );
    }

    // Выполнить прямой обход двоичного дерева поиска с корнем в node, рекурсивный алгоритм
    private void preOrder(Node node){

        if( node != null ){
            System.out.println(node.key);
            preOrder(node.left);
            preOrder(node.right);
        }
    }

    // Выполнить симметричный обход двоичного дерева поиска с корнем в node, рекурсивный алгоритм
    private void inOrder(Node node){

        if( node != null ){
            inOrder(node.left);
            System.out.println(node.key);
            inOrder(node.right);
        }
    }

    // Выполнить обход в обратном порядке двоичного дерева поиска с корнем в node, рекурсивный алгоритм
    private void postOrder(Node node){

        if( node != null ){
            postOrder(node.left);
            postOrder(node.right);
            System.out.println(node.key);
        }
    }
}
Другие расширения