Hauteur d'une structure de données d'arbre

Dans ce tutoriel, nous allons discuter des arbres binaires. Nous verrons comment calculer la hauteur d'une structure de données en arbre de manière récursive ainsi qu'itérative.

Arbres binaires

Les arbres binaires sont une structure de données dans laquelle les données sont stockées de manière hiérarchique plutôt que linéaire (comme cela se fait dans les listes chaînées et les tableaux). Une structure de données d'arbre binaire est composée de nœuds. Chaque nœud contient les données ainsi que la référence aux pointeurs des enfants (gauche et droite). La racine de l'arbre binaire est le nœud le plus haut. (Donc l'opposé d'un arbre vivant réel). Voici une illustration d'un arbre avec quelques nœuds.

• Méthode récursive
• Méthode itérative

Hauteur d'un arbre - Récursivement

La récursion implique de calculer les résultats des sous-problèmes et de les renvoyer au problème parent.

Étapes impliquées :

1. Pour calculer la hauteur de l'arbre de manière récursive, nous devons trouver la hauteur de son sous-arbre gauche et de son sous-arbre droit de manière récursive et leur ajouter 1 (hauteur entre le nœud le plus haut et ses enfants).
2. Chacun de ces sous-arbres pourrait avoir eux-mêmes un sous-arbre gauche et un sous-arbre droit, donc la récursion s'appliquerait jusqu'à ce que les sous-arbres soient NULL. La hauteur d'un nœud d'arbre nul est de -1.
3. Enfin, nous comparerons les hauteurs du sous-arbre gauche et du sous-arbre droit et retournerons celui qui est le plus grand.

L'illustration suivante montre le nombre de permutations pour calculer la hauteur de l'arbre binaire.

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;
		}
	}
}

Voyons le code pour trouver la hauteur de l'arbre en utilisant la récursion.

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;
	}
}

Donc, dans le code ci-dessus, une fois que nous atteignons le nœud enfant le plus bas, nous ajoutons un à la hauteur de l'arbre et renvoyons le résultat à l'appel précédent. Résultat : La hauteur de l'arbre est de 2 Faisons maintenant la même chose sans utiliser la récursivité.

Hauteur de l'arbre - de manière itérative

Pour calculer la hauteur de l'arbre de manière itérative, nous devons simplement calculer le nombre de niveaux dans l'arbre.

Étapes impliquées

1. Créez une file d'attente et ajoutez-y la racine de l'arbre.
2. Sortez le nœud de la file d'attente et parcourez la file en ajoutant les nœuds enfants à la file d'attente.
3. À chaque itération, dépilez le dernier élément ajouté à la file et ajoutez les éléments du niveau suivant (de cet élément) à la file.
4. Faites cela jusqu'à ce que la taille de la file d'attente devienne zéro. Cela signifierait que le niveau suivant a zéro élément.
5. Pour chaque niveau parcouru, ajoutez 1.

Ce qui suit est le programme itératif pour calculer la hauteur de l'arbre.

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;
}

Le code ci-dessus continue à s'exécuter jusqu'à ce que la file d'attente ne soit pas vide. Et en plus, il continue à ajouter tous les éléments du niveau suivant tout en supprimant les éléments du niveau actuel de la file d'attente.

La complexité temporelle est O(n). La complexité spatiale est O(1).

Vous pouvez consulter le code complet et plus d'exemples de structures de données et d'algorithmes sur notre dépôt GitHub.