DEV Community

faangmaster
faangmaster

Posted on • Updated on

Алгоритмы обхода двоичного дерева

Двоичное дерево — дерево, в котором каждая вершина имеет не более двух дочерних вершин (их называют левым и правым ребенком).

Пример двоичного дерева:

Class BinaryTree:

    class BinaryTree {
      public int value;
      public BinaryTree left;
      public BinaryTree right;

      public BinaryTree(int value) {
        this.value = value;
      }
    }
Enter fullscreen mode Exit fullscreen mode

Чтобы обойти вершины двоичного дерева можно использовать алгоритм поиска в глубину (DFS). Обычно в алгоритмических задачах на двоичные деревья используется рекурсивная версия этого алгоритма. Для деревьев этот алгоритм сильно упрощается, т.к. нам не надо использовать visited. Для деревьев нам не нужно помечать вершины посещенными, потому что в дереве нет циклов по определению. А также мы будем идти от родительских вершин к дочерним.

Поэтому для двоичного дерева алгоритм упрощается до:

    public static void dfs(BinaryTree tree) {
      if (tree == null) {
        return;
      }
      visit(tree);
      dfs(tree.left);
      dfs(tree.right);
    }
Enter fullscreen mode Exit fullscreen mode

Такой алгоритм обхода двоичного дерева называется pre-order traversal: Tree Traversal.

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

Есть еще вариации обхода двоичного дерева, которые называются соответственно in-order (вначале посещаем левого ребенка, потом вершину, потом правого ребенка):

    public static void dfs(BinaryTree tree) {
      if (tree == null) {
        return;
      }
      dfs(tree.left);
      visit(tree);
      dfs(tree.right);
    }
Enter fullscreen mode Exit fullscreen mode

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

И post-order (вначале посещаем левого и правого ребенка, а потом уже саму вершину):

    public static void dfs(BinaryTree tree) {
      if (tree == null) {
        return;
      }
      dfs(tree.left);
      dfs(tree.right);
      visit(tree);
    }
Enter fullscreen mode Exit fullscreen mode

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

Обычно, надо написать какую-то кастомную логику под задачу для каждой посещенной вершины вместо метода visit. Иногда надо добавить дополнительные if-else для рекурсивных вызовов. Иногда надо передавать или возвращать какие-то значения или объекты из метода dfs.

Top comments (0)