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  #include  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 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!