Méthode itérative pour trouver la hauteur de l'arbre binaire

L'arbre binaire est une structure de données. Chaque nœud d'un arbre binaire contient 0, 1 ou 2 nœuds. Par conséquent, un arbre binaire peut contenir plusieurs niveaux.

Ici, nous devons écrire du code itératif en utilisant une boucle pour trouver la hauteur de l'arbre binaire. Le nombre total de niveaux d'un arbre binaire représente la hauteur de l'arbre binaire. Alternativement, nous pouvons dire que la profondeur maximale d’un arbre binaire à partir du nœud racine est la hauteur de l’arbre binaire.

Énoncé du problème - On nous donne un arbre binaire. Nous devons utiliser une méthode itérative pour trouver la hauteur d’un arbre binaire donné.

Méthode 1

Comme nous l'avons dit plus haut, la hauteur d'un arbre binaire est égale au nombre total de niveaux de l'arbre binaire. Nous utiliserons une structure de données de file d'attente pour parcourir chaque nœud de chaque niveau et trouver la profondeur maximale de l'arborescence.

Algorithme

Étape 1 - Définissez la classe "treeNode" et ajoutez la variable entière "val". Définissez également les pointeurs « gauche » et « droite » dans la classe.

Étape 2- Définissez la fonction createNode() pour créer un nouveau nœud pour l'arborescence. Il crée un nouveau treeNode, initialise « val » avec la valeur du paramètre et initialise les pointeurs gauche et droit avec des valeurs nulles. Renvoyez enfin le nœud nouvellement créé.

Étape 3 - La fonction findHeight() est utilisée pour trouver la hauteur de l'arbre binaire.

Étape 4 - Définissez la file d'attente "levelqueue" pour stocker tous les nœuds du niveau actuel, la variable "treeHeight", "n_cnt" et le nœud "temp".

Étape 5− Si le nœud principal est nul, renvoyez 0.

Étape 6- Poussez le nœud principal vers "levelQueue".

Étape 7- Utilisez une boucle "while" pour itérer jusqu'à ce que "levelQueue" devienne vide.

Étape 8- Augmentez "treeHeight" de 1 et initialisez "n_cnt" avec la taille de la file d'attente, représentant le nombre total de nœuds au niveau actuel.

Étape 9- Parcourez tous les éléments de la file d'attente.

Étape 9.1 - Pop le premier élément de la file d'attente.

Étape 9.2 − Si le nœud actuel a un nœud enfant gauche, insérez-le dans la file d'attente.

Étape 9.3 − Si le nœud actuel a un nœud enfant droit, insérez-le dans la file d'attente.

Étape 9.4 - Supprimez le premier nœud de la file d'attente.

Étape 10- Renvoyez la valeur de la variable "treeHeight".

Exemple

#include <iostream>
#include <queue>

using namespace std;
class treeNode {
public:
    int val;
    treeNode *left;
    treeNode *right;
};
treeNode *createNode(int val) {
    //Create a new node
    treeNode *temp = new treeNode();
    temp->val = val;
    temp->left = NULL;
    temp->right = NULL;
    return temp;
}
int fidHeight(treeNode *head) {
    queue<treeNode *> levelQueue;
    int treeHeight = 0; // To store the tree height of the current binary tree
    int n_cnt = 0;      // To store the total number of current level nodes.
    treeNode *temp;     // Pointer to store the address of a node in the current level.
    // For empty binary tree
    if (head == NULL) {
        return 0;
    }
    // Add root node to queue
    levelQueue.push(head);
    // Traverse level of binary tree
    while (!levelQueue.empty()) {
        // For each level increment, the treeHeight of the three
        treeHeight++;
        n_cnt = levelQueue.size();
        // Add child nodes of all nodes at the current level
        while (n_cnt--) {
            temp = levelQueue.front();
            // Insert the left child node of the current node
            if (temp->left != NULL) {
                levelQueue.push(temp->left);
            }
            // Insert the right child node of the current node
            if (temp->right != NULL) {
                levelQueue.push(temp->right);
            }
            // remove the current node
            levelQueue.pop();
        }
    }
    return treeHeight;
}
int main() {
    treeNode *head = NULL;
    // Adding nodes to binary tree.
    head = createNode(45);
    head->right = createNode(32);
    head->right->left = createNode(48);
    head->left = createNode(90);
    head->left->left = createNode(5);
    head->left->left->left = createNode(50);
    cout << "The given binary tree's treeHeight is " << fidHeight(head) << ".";
    return 0;
}

Sortie

The given binary tree's treeHeight is 4.

Complexité temporelle - O(N) pour parcourir chaque nœud.

Complexité spatiale - O(N) pour stocker les nœuds dans la file d'attente.

Les méthodes itératives sont toujours plus rapides que les méthodes récursives pour résoudre un problème. Ici, nous utilisons des boucles et des files d'attente pour trouver de manière itérative la profondeur ou la hauteur maximale d'un arbre binaire. Cependant, un programmeur pourrait essayer de coder une méthode récursive pour trouver la hauteur d'un arbre binaire.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!