二叉树是一种数据结构。二叉树的每个节点包含 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 #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;}
输出
The given binary tree's treeHeight is 4.
时间复杂度 – O(N) 遍历每个节点。
空间复杂度 – O(N) 在队列中存储节点。
解决任何问题时，迭代方法总是比递归方法更快。在这里，我们使用循环和队列来迭代地找到二叉树的最大深度或高度。然而，程序员可能会尝试编写递归方法的代码来查找二叉树的高度。
以上就是迭代方法寻找二叉树的高度的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1444479.html
微信扫一扫 
支付宝扫一扫 
