迭代方法尋找二元樹的高度

二元樹是一種資料結構。二元樹的每個節點包含 0、1 或 2 個節點。因此，二元樹可以包含多個層級。

在這裡，我們需要使用循環編寫迭代程式碼來尋找二元樹的高度。二元樹的總層數代表二元樹的高度。或者，我們可以說二元樹從根節點開始的最大深度就是二元樹的高度。

問題陳述 - 我們給了一個二元樹。我們需要使用迭代的方法來求出給定二元樹的高度。

方法 1

如我們上面所說，二元樹的高度等於二元樹的總層數。我們將使用佇列資料結構來遍歷每一層的每個節點並找到樹的最大深度。

演算法

第 1 步 - 定義「treeNode」類，並新增「val」整數變數。另外，在類別中定義“左”和“右”指標。

步驟 2- 定義 createNode() 函數來為樹建立一個新節點。它建立一個新的treeNode，用參數值初始化“val”，用空值初始化左指標和右指標。最後返回新建立的節點。

步驟 3 - findHeight() 函數用來找出二元樹的高度。

第 4 步 - 定義「levelqueue」佇列來儲存目前層級的所有節點、「treeHeight」、「n_cnt」變數和「temp」節點。

第 5 步− 如果頭節點為 Null，則傳回 0。

第 6 步- 將頭節點推送到「levelQueue」。

第 7 步- 使用「while」循環進行迭代，直到「levelQueue」變空。

第 8 步- 將“treeHeight”增加 1，並以佇列的大小初始化“n_cnt”，代表目前層級的總節點數。

第 9 步- 遍歷佇列的所有元素。

步驟 9.1 - 彈出佇列的第一個元素。

步驟 9.2 − 如果目前節點存在左子節點，則將其插入佇列。

步驟 9.3 − 如果目前節點存在右子節點，則將其插入佇列。

步驟 9.4 - 從佇列中刪除第一個節點。

第 10 步- 傳回「treeHeight」變數的值。

範例

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

輸出

The given binary tree's treeHeight is 4.

時間複雜度 - O(N) 遍歷每個節點。

空間複雜度 - O(N) 在佇列中儲存節點。

解決任何問題時，迭代方法總是比遞歸方法更快。在這裡，我們使用循環和隊列來迭代地找到二元樹的最大深度或高度。然而，程式設計師可能會嘗試編寫遞歸方法的程式碼來尋找二元樹的高度。

以上是迭代方法尋找二元樹的高度的詳細內容。更多資訊請關注PHP中文網其他相關文章！