Kaedah berulang untuk mencari ketinggian pokok binari

Pokok binari ialah struktur data. Setiap nod pokok binari mengandungi 0, 1, atau 2 nod. Oleh itu, pokok binari boleh mengandungi pelbagai peringkat.

Di sini kita perlu menulis kod lelaran menggunakan gelung untuk mencari ketinggian pokok binari. Jumlah bilangan aras pokok binari mewakili ketinggian pokok binari. Sebagai alternatif, kita boleh mengatakan bahawa kedalaman maksimum pokok binari dari nod akar ialah ketinggian pokok binari.

Pernyataan Masalah - Kami diberi pokok binari. Kita perlu menggunakan kaedah berulang untuk mencari ketinggian pokok binari yang diberikan.

Kaedah 1

Seperti yang kami katakan di atas, ketinggian pokok binari adalah sama dengan jumlah bilangan peringkat pokok binari. Kami akan menggunakan struktur data baris gilir untuk lelaran melalui setiap nod setiap peringkat dan mencari kedalaman maksimum pokok.

Algoritma

Langkah 1 - Takrifkan kelas "treeNode" dan tambahkan pembolehubah integer "val". Juga, tentukan penunjuk "kiri" dan "kanan" dalam kelas.

Langkah 2- Takrifkan fungsi createNode() untuk mencipta nod baharu untuk pepohon. Ia mencipta treeNode baharu, memulakan "val" dengan nilai parameter, dan memulakan penunjuk kiri dan kanan dengan nilai nol. Akhirnya kembalikan nod yang baru dibuat.

Langkah 3 - Fungsi findHeight() digunakan untuk mencari ketinggian pokok binari.

Langkah 4 - Tentukan baris gilir "levelqueue" untuk menyimpan semua nod tahap semasa, pembolehubah "treeHeight", "n_cnt" dan nod "temp".

Langkah 5− Jika nod kepala adalah Nol, kembalikan 0.

Langkah 6- Tolak nod kepala ke "levelQueue".

Langkah 7- Gunakan gelung "while" untuk mengulang sehingga "levelQueue" menjadi kosong.

Langkah 8- Tingkatkan "treeHeight" sebanyak 1 dan mulakan "n_cnt" dengan saiz baris gilir, mewakili jumlah bilangan nod pada tahap semasa.

Langkah 9- Ulangi semua elemen baris gilir.

Langkah 9.1 - Pop elemen pertama baris gilir.

Langkah 9.2 − Jika nod semasa mempunyai nod anak kiri, masukkannya ke dalam baris gilir.

Langkah 9.3 − Jika nod semasa mempunyai nod anak yang betul, masukkannya ke dalam baris gilir.

Langkah 9.4 - Keluarkan nod pertama daripada baris gilir.

Langkah 10- Kembalikan nilai pembolehubah "treeHeight".

Contoh

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

Output

The given binary tree's treeHeight is 4.

Kerumitan masa - O(N) untuk merentasi setiap nod.

Kerumitan ruang - O(N) untuk menyimpan nod dalam baris gilir.

Kaedah berulang sentiasa lebih cepat daripada kaedah rekursif apabila menyelesaikan sebarang masalah. Di sini kami menggunakan gelung dan baris gilir untuk mencari secara berulang kedalaman atau ketinggian maksimum pokok binari. Walau bagaimanapun, seorang pengaturcara mungkin cuba mengodkan kaedah rekursif untuk mencari ketinggian pokok binari.

Atas ialah kandungan terperinci Kaedah berulang untuk mencari ketinggian pokok binari. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!