Iterative Methode zum Ermitteln der Höhe des Binärbaums

Binärbaum ist eine Datenstruktur. Jeder Knoten eines Binärbaums enthält 0, 1 oder 2 Knoten. Daher kann ein Binärbaum mehrere Ebenen enthalten.

Hier müssen wir mithilfe einer Schleife iterativen Code schreiben, um die Höhe des Binärbaums zu ermitteln. Die Gesamtzahl der Ebenen eines Binärbaums stellt die Höhe des Binärbaums dar. Alternativ können wir sagen, dass die maximale Tiefe eines Binärbaums vom Wurzelknoten aus die Höhe des Binärbaums ist.

Problemstellung – Wir erhalten einen Binärbaum. Wir müssen eine iterative Methode verwenden, um die Höhe eines bestimmten Binärbaums zu ermitteln.

Methode 1

Wie oben erwähnt, entspricht die Höhe eines Binärbaums der Gesamtzahl der Ebenen des Binärbaums. Wir werden eine Warteschlangendatenstruktur verwenden, um jeden Knoten jeder Ebene zu durchlaufen und die maximale Tiefe des Baums zu ermitteln.

Algorithmus

Schritt 1 – Definieren Sie die Klasse „treeNode“ und fügen Sie die Ganzzahlvariable „val“ hinzu. Definieren Sie außerdem „linke“ und „rechte“ Zeiger in der Klasse.

Schritt 2 – Definieren Sie die Funktion createNode(), um einen neuen Knoten für den Baum zu erstellen. Es erstellt einen neuen TreeNode, initialisiert „val“ mit dem Parameterwert und initialisiert den linken und rechten Zeiger mit Nullwerten. Geben Sie schließlich den neu erstellten Knoten zurück.

Schritt 3 – Die Funktion findHeight() wird verwendet, um die Höhe des Binärbaums zu ermitteln.

Schritt 4 - Definieren Sie die Warteschlange „levelqueue“, um alle Knoten der aktuellen Ebene, die Variable „treeHeight“, die Variable „n_cnt“ und den Knoten „temp“ zu speichern.

Schritt 5− Wenn der Kopfknoten Null ist, geben Sie 0 zurück.

Schritt 6- Schieben Sie den Hauptknoten in die „levelQueue“.

Schritt 7 – Verwenden Sie eine „while“-Schleife, um zu iterieren, bis die „levelQueue“ leer wird.

Schritt 8- Erhöhen Sie „treeHeight“ um 1 und initialisieren Sie „n_cnt“ mit der Größe der Warteschlange, die die Gesamtzahl der Knoten auf der aktuellen Ebene darstellt.

Schritt 9 – Alle Elemente der Warteschlange durchlaufen.

Schritt 9.1 - Öffnen Sie das erste Element der Warteschlange.

Schritt 9.2 − Wenn der aktuelle Knoten einen linken untergeordneten Knoten hat, fügen Sie ihn in die Warteschlange ein.

Schritt 9.3 − Wenn der aktuelle Knoten einen rechten untergeordneten Knoten hat, fügen Sie ihn in die Warteschlange ein.

Schritt 9.4 - Entfernen Sie den ersten Knoten aus der Warteschlange.

Schritt 10- Geben Sie den Wert der Variablen „treeHeight“ zurück.

Beispiel

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

Ausgabe

The given binary tree's treeHeight is 4.

Zeitkomplexität – O(N) zum Durchlaufen jedes Knotens.

Raumkomplexität – O(N) zum Speichern von Knoten in der Warteschlange.

Iterative Methoden sind bei der Lösung eines Problems immer schneller als rekursive Methoden. Hier verwenden wir Schleifen und Warteschlangen, um iterativ die maximale Tiefe oder Höhe eines Binärbaums zu ermitteln. Ein Programmierer könnte jedoch versuchen, eine rekursive Methode zu programmieren, um die Höhe eines Binärbaums zu ermitteln.

Das obige ist der detaillierte Inhalt vonIterative Methode zum Ermitteln der Höhe des Binärbaums. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!