Pre-order обход бинарного дерева на Java — рекурсивный алгоритм

Прямой обход (preorder traversal) — это способ обхода дерева, при котором сначала посещается корень, затем левое поддерево, затем правое. Такой обход полезен, например, для создания копии дерева или префиксной записи выражения.

Чтобы понять этот пример, нужно знать:

• Классы и объекты в Java

• Методы в Java

Пример: прямой обход дерева на Java

class Node {
  int item;
  Node left, right;

  public Node(int key) {
  item = key;
  left = right = null;
  }
}

class Tree {
  // root of Tree
  Node root;

  Tree() {
  root = null;
  }

  void preorder(Node node) {
    if (node == null)
      return;

    // traverse the root node
    System.out.print(node.item + "->");
    // traverse the left child
    preorder(node.left);
    // traverse the right child
    preorder(node.right);
  }

  public static void main(String[] args) {
    // create object of tree
    Tree tree = new Tree();

    // create nodes of the tree
    tree.root = new Node(1);
    tree.root.left = new Node(12);
    tree.root.right = new Node(9);
    tree.root.left.left = new Node(5);
    tree.root.left.right = new Node(6);

    // preorder tree traversal
    System.out.println("\nPreorder traversal ");
    tree.preorder(tree.root);
  }
}

Вывод:

Preorder traversal
1->12->5->6->9->

В этом примере мы реализовали структуру дерева и выполнили прямой обход. Порядок «корень → левое → правое» хорошо видно по результату: сначала идёт 1 (корень), затем поддерево с корнем 12, и только потом правый потомок 9.

Подсказка

Запомнить три обхода легко по положению корня: preorder — корень в начале, inorder — в середине, postorder — в конце.