Нахождение высоты узла в двоичном дереве

В этой статье объясняется, как найти высоту узла в заданном бинарном дереве. Определение высоты узла является важным фактором при построении самобалансирующегося дерева или дерева AVL. Высота узла играет важную роль в повороте дерева при построении деревьев AVL. Как мы знаем, высота пустого дерева (без узлов) равна -1, а высота дерева только с одним узлом (корневым узлом) равна 0. Мы применяем ту же концепцию при вычислении высоты данного узла в дереве. Чтобы проиллюстрировать концепцию, мы строим бинарное дерево поиска, как показано ниже:

Обратите внимание, что приведенное выше дерево не сбалансировано.

Нам нужно найти высоту узла 25. Итак, мы начинаем с корневого узла дерева, который равен 5. Мы предпочитаем сначала посещать левое поддерево, а затем правое поддерево. После посещения каждого поддерева слева и справа мы проверяем, имеет ли текущий узел те же данные, что и узел, для которого нам нужно найти высоту. Чтобы узнать высоту узла, мы пишем лаконичный код с рекурсией. Ниже приведен код для определения высоты заданного узла.

public class HeightBSTNode {
  Node root;
  Node add (Node node, int data) {
     if (null == node) return new Node (data);
     else if (data < node.data) node.left = add (node.left, data);
     else if (data > node.data) node.right = add (node.right, data);
     return node;
  }
  static int findHeight (Node Node, int data, int height, Value V) {
     if (Node == null) return height;
     // Go to left subtree
     int level = findHeight (Node.left, data, height+1, V);
     if (Node.data == data) V.v = level;
     
     // Go to right subtree
     level = findHeight (Node.right, data, height+1, V);
     if (Node.data == data) V.v = level;
     return height;
  }
  public static void main (String[] args) {
     HeightBSTNode a = new HeightBSTNode();
     Value V = new Value();
     
     // create a tree.
     a.root = add (a.root, 5);
     a.root = add (a.root, 3);
     a.root = add (a.root, 2);
     a.root = add (a.root, 10);
     a.root = add (a.root, 15);
     a.root = add (a.root, 12);
     a.root = add (a.root, 25);
     a.root = add (a.root, 35);
    findHeight (a.root, 25, -1, V);
    System.out.println ("Height of node "+25+" is "+V.v);
  }
}
class Node {
  int data;
  Node left, right;  
  
  Node (int data) {
    this.data=data;
  }
}
class Value {
  int v;
}

Функция main() начинает вызывать findHeight()сroot, data, -1, V. В нашем случае данные, для которых нам нужно найти высоту, — это node с значение 25, начальная высота, которую мы принимаем равной -1, и V используется для хранения высоты узла, на который мы можем ссылаться, когда вызов возвращается к main(). Уровень используется для хранения высоты левого поддерева и правого поддерева. При выполнении каждого рекурсивного вызова мы увеличиваем высоту на 1. Когда возвращаются вызовы как левого, так и правого поддерева, мы возвращаем высоту в стеке вызовов. Это важно, когда мы переходим от левого поддерева к корню и от правого поддерева к корню. Временная сложность findHeight() составляет O(N).

После запуска программа печатает:

Height of node 25 is 3
Similarly the height of nodes 35 and 2 is as below
Height of node 35 is 4
Height of node 2 is 2

Вывод

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