Бинарное дерево на Java — пошаговая реализация с разбором

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

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

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

• Методы в Java

Пример: реализация бинарного дерева на Java

// class to create nodes
class Node {
  int key;
  Node left, right;

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

class BinaryTree {
  Node root;

  // Traverse tree
  public void traverseTree(Node node) {
    if (node != null) {
      traverseTree(node.left);
      System.out.print(" " + node.key);
      traverseTree(node.right);
    }
  }

  public static void main(String[] args) {

    // create an object of BinaryTree
    BinaryTree tree = new BinaryTree();

    // create nodes of the tree
    tree.root = new Node(1);
    tree.root.left = new Node(2);
    tree.root.right = new Node(3);
    tree.root.left.left = new Node(4);

    System.out.print("\nBinary Tree: ");
    tree.traverseTree(tree.root);
  }
}

Вывод:

Binary Tree:  4 2 1 3

В этом примере мы реализовали бинарное дерево на Java. Класс Node представляет один узел и хранит значение key, а также ссылки на левого и правого потомка. Класс BinaryTree хранит корень и предоставляет метод traverseTree(), который рекурсивно обходит дерево.

Примечание

В Java нет встроенного класса для деревьев — в отличие от ArrayList или HashMap, дерево нужно описать своим классом.

Совет

Метод traverseTree() в этом примере выполняет именно симметричный (inorder) обход: сначала левое поддерево, потом сам узел, затем правое поддерево.