Высота древовидной структуры данных

В этом уроке мы обсудим бинарные деревья. Мы увидим, как вычислить высоту древовидной структуры данных рекурсивно, а также итеративно.

Бинарные деревья

• Рекурсивный способ
• Итеративный способ

Высота дерева - рекурсивно

Рекурсия включает в себя вычисление результатов подзадач и возврат их к родительской проблеме.

Шаги:

1. Чтобы рекурсивно вычислить высоту дерева, нам нужно рекурсивно найти высоту его левого и правого поддеревьев и добавить к ним 1 (высота между самым верхним узлом и его дочерними элементами).
2. Каждое из этих поддеревьев может иметь левое и правое поддеревья, поэтому рекурсия будет применяться до тех пор, пока поддеревья не станут NULL. Высота пустого узла дерева равна -1.
3. Наконец, мы сравним высоту левого и правого поддеревьев и вернем то, которое больше.

package com.journaldev.tree.height;

public class BinaryTree {

	TreeNode root;

	public static class TreeNode {

		TreeNode left;
		TreeNode right;
		Object data;

		TreeNode(Object data) {
			this.data = data;
			left = right = null;
		}
	}
}

Давайте посмотрим код для нахождения высоты дерева с помощью рекурсии.

package com.journaldev.tree.height;

import com.journaldev.tree.height.BinaryTree.TreeNode;

public class HeightOfTree {

	public static void main(String[] args) {

		BinaryTree binaryTree = new BinaryTree();

		/**
		 * Binary Tree in our example, height = 2
		 * 		1		(Root)
		 * 	  2	  3		(Level 1)
		 *  4    	 5		(Level 2)
		 */
		binaryTree.root = new TreeNode(1);
		binaryTree.root.left = new TreeNode(2);
		binaryTree.root.right = new TreeNode(3);
		binaryTree.root.left.left = new TreeNode(4);
		binaryTree.root.right.left = new TreeNode(5);

		int heightOfTree = height(binaryTree.root);
		System.out.printf("Height of tree is %d", heightOfTree);
	}
	
	public static int height(TreeNode root) {

		if (root == null)
			return -1;

		int leftHeight = height(root.left);
		int rightHeight = height(root.right);

		return Math.max(leftHeight, rightHeight) + 1;
	}
}

Итак, в приведенном выше коде, как только мы достигаем самого нижнего дочернего узла, мы добавляем единицу к высоте дерева и возвращаем результат предыдущему вызову. Вывод: высота дерева равна 2. Теперь сделаем то же самое нерекурсивно.

Высота дерева - итеративно

Чтобы вычислить высоту дерева итеративно, нам просто нужно вычислить количество уровней в дереве.

Затраченные шаги

1. Создайте очередь и добавьте в нее корень дерева.
2. Извлеките узел из очереди и пройдите вниз по очереди, добавляя дочерние узлы в очередь.
3. В каждой итерации всплывает последний элемент, добавляемый в очередь, и добавляются элементы следующего уровня (этого элемента) в очередь.
4. Делайте это до тех пор, пока размер очереди не станет равным нулю. Это будет означать, что на следующем уровне нет элементов.
5. За каждый пройденный уровень прибавляйте 1.

Ниже приведена итеративная программа для вычисления высоты дерева.

public static int heightIteratively(TreeNode root) {

    if (root == null)
        return -1;

    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    int height = -1;

    while (!queue.isEmpty()) {
        int size = queue.size();

        height++;

        while (size > 0) {
            TreeNode treeNode = queue.remove();

            if (treeNode.left != null)
                queue.add(treeNode.left);

            if (treeNode.right != null)
                queue.add(treeNode.right);
            
            size--;
        }
    }
    return height;
}

Временная сложность — O(n). Космическая сложность O (1).

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