首页
学习
活动
专区
圈层
工具
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

如何在不使用递归的情况下在C中找到二叉树的高度?

在不使用递归的情况下,可以使用迭代的方式来找到二叉树的高度。具体的实现方法是使用层序遍历算法,通过队列来遍历二叉树的每一层节点,并记录层数,直到遍历完所有节点。

以下是实现的代码示例:

代码语言:txt
复制
#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

typedef struct QueueNode {
    TreeNode* node;
    struct QueueNode* next;
} QueueNode;

typedef struct Queue {
    QueueNode* front;
    QueueNode* rear;
} Queue;

Queue* createQueue() {
    Queue* queue = (Queue*)malloc(sizeof(Queue));
    queue->front = NULL;
    queue->rear = NULL;
    return queue;
}

void enqueue(Queue* queue, TreeNode* node) {
    QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
    newNode->node = node;
    newNode->next = NULL;
    
    if (queue->rear == NULL) {
        queue->front = newNode;
        queue->rear = newNode;
    } else {
        queue->rear->next = newNode;
        queue->rear = newNode;
    }
}

TreeNode* dequeue(Queue* queue) {
    if (queue->front == NULL) {
        return NULL;
    }
    
    TreeNode* node = queue->front->node;
    QueueNode* temp = queue->front;
    queue->front = queue->front->next;
    
    if (queue->front == NULL) {
        queue->rear = NULL;
    }
    
    free(temp);
    return node;
}

int getBinaryTreeHeight(TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    
    Queue* queue = createQueue();
    enqueue(queue, root);
    int height = 0;
    
    while (1) {
        int levelSize = queue->rear - queue->front + 1;
        if (levelSize == 0) {
            break;
        }
        
        while (levelSize > 0) {
            TreeNode* node = dequeue(queue);
            
            if (node->left != NULL) {
                enqueue(queue, node->left);
            }
            
            if (node->right != NULL) {
                enqueue(queue, node->right);
            }
            
            levelSize--;
        }
        
        height++;
    }
    
    return height;
}

int main() {
    // 构造二叉树
    TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
    root->val = 1;
    
    root->left = (TreeNode*)malloc(sizeof(TreeNode));
    root->left->val = 2;
    
    root->right = (TreeNode*)malloc(sizeof(TreeNode));
    root->right->val = 3;
    
    root->left->left = (TreeNode*)malloc(sizeof(TreeNode));
    root->left->left->val = 4;
    
    root->left->right = (TreeNode*)malloc(sizeof(TreeNode));
    root->left->right->val = 5;
    
    root->right->left = (TreeNode*)malloc(sizeof(TreeNode));
    root->right->left->val = 6;
    
    root->right->right = (TreeNode*)malloc(sizeof(TreeNode));
    root->right->right->val = 7;
    
    // 计算二叉树的高度
    int height = getBinaryTreeHeight(root);
    printf("二叉树的高度为:%d\n", height);
    
    // 释放内存
    free(root->right->right);
    free(root->right->left);
    free(root->left->right);
    free(root->left->left);
    free(root->right);
    free(root->left);
    free(root);
    
    return 0;
}

在上述代码中,我们定义了一个队列结构和一个二叉树结构,使用队列进行层序遍历。首先创建一个队列,并将根节点入队。然后进行循环,当队列非空时,先获取当前层的节点数,依次出队并将它们的左右子节点入队。在每一层处理完之后,层数加1,直到队列为空。最后返回层数作为二叉树的高度。

这里没有提及具体的腾讯云相关产品,因为找二叉树高度是一般计算问题,与云计算平台的关系不大,因此不需要特定的云计算产品来解决。

页面内容是否对你有帮助?
有帮助
没帮助

相关·内容

判断是不是平衡二叉树

在这里,我们只需要考虑其平衡性,不需要考虑其是不是排序二叉树 平衡二叉树(Balanced Binary Tree),具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树...解答 平衡树意味着我们需要对比任何在同一个根下的左右子树的高度差,还记得之前我们计算树的高度么,使用递归方式来解决,其实这道题与算高度差不多,只是两边高度需要算出一个差值。...算法的主要思想: 不断对比每两个节点的左右子树的最大高度差,注意取差的绝对值,需要小于等于1 对比完左右子树之后,需要递归左子树以及右子树进行分别判断,都满足才是平衡树 Java 代码如下: public...但是判断每个节点最大高度需要递归左右子树,需要占用 O(log2n),所以总共占用O(Nlog2n) 空间复杂度O(n):最差情况下,也就是树退化为链表时,递归需要使用 O(n) 的栈空间,严格意义上递归栈也需要空间...-1 : 1 + max(left, right); } }; 时间复杂度O(n):每个节点计算一次 空间复杂度O(n):递归需要使用额外堆栈空间 【作者简介】 秦怀,技术之路不在一时,山高水长

1.1K20
  • 我的思念像满二叉树般疯长,每个空指针都指向你的方向——全程动画可视化数据结构算法之二叉树

    本篇技术博文摘要 本文系统梳理了树形数据结构及其衍生技术的核心内容,从基础概念到高阶算法完整覆盖:以树与二叉树为起点,详解存储结构(顺序/链式)与遍历算法(递归/非递归),结合代码实现(如先序递归遍历...​ (6):高度最小的情况:所有结点都有m个孩子 ​ 二叉树的定义和基本术语 定义: 二叉树是n(n≥0)个结点的有限集合 或者为空二叉树,即n = 0。...平均查找长度=O(n) 最好情况:n个结点的二叉树最小高度为(log2n)+ 1。...平均查找长度= O(log2n) 平衡二叉树(AVL) 定义: 平衡二叉树(Balanced Binary Tree),简称平衡树(AVL树)——树上任一结点的左子树和右子树的高度之差不超过1...C结点向左上旋转提升到A结点的位置 查找效率分析: 若树高为h,则最坏情况下,查找一个关键字最多需要对比h次,即查找操作的时间复杂度不可能超过O(h) 平衡二叉树——树上任一结点的左子树和右子树的高度之差不超过

    6800

    程序员必备的50道数据结构和算法面试题

    编码面试主要包括数据结构和基于算法的问题,以及一些诸如如何在不使用临时变量的情况下交换两个整数这样的逻辑问题? 我认为将编程面试问题划分到不同的主题区域是很有帮助的。...我在面试中经常看到的主题区域是数组、链表、字符串、二叉树,以及源于算法的问题(例如字符串算法,排序算法,如 quicksort 或基数排序,以及其他杂项),这就是你能在这篇文章中找到主要内容。...解决数组问题的关键是,你要对数组这种数据结构有一个深刻的认识,同时还要了解基本的程序流程如循环、递归以及基本的操作符。...下面是一些经常问到的基于二叉树的面试题,你可以拿来练习: 1、二叉搜索树是如何实现的? 2、如何在给定二叉树上实现前序遍历? 3、不使用递归如何按照前序遍历给定二叉树?...4、如何在给定二叉树上实现中序遍历? 5、不使用递归情况下如何使用中序遍历输出给定二叉树所有节点? 6、如何实现后序遍历算法? 7、如何不使用递归实现二叉树的后续遍历?

    3.2K11

    程序员必备的50道数据结构和算法面试题

    编码面试主要包括数据结构和基于算法的问题,以及一些诸如如何在不使用临时变量的情况下交换两个整数这样的逻辑问题? 我认为将编程面试问题划分到不同的主题区域是很有帮助的。...我在面试中经常看到的主题区域是数组、链表、字符串、二叉树,以及源于算法的问题(例如字符串算法,排序算法,如 quicksort 或基数排序,以及其他杂项),这就是你能在这篇文章中找到主要内容。...解决数组问题的关键是,你要对数组这种数据结构有一个深刻的认识,同时还要了解基本的程序流程如循环、递归以及基本的操作符。...下面是一些经常问到的基于二叉树的面试题,你可以拿来练习: 1、二叉搜索树是如何实现的? 2、如何在给定二叉树上实现前序遍历? 3、不使用递归如何按照前序遍历给定二叉树?...4、如何在给定二叉树上实现中序遍历? 5、不使用递归情况下如何使用中序遍历输出给定二叉树所有节点? 6、如何实现后序遍历算法? 7、如何不使用递归实现二叉树的后续遍历?

    4.3K20

    【数据结构——树】二叉树的基本运算(头歌实践教学平台习题)【合集】

    销毁二叉树 为了避免内存泄漏,在不再使用二叉树时,需要释放二叉树占用的内存空间,通过递归遍历二叉树,先释放子节点的内存,再释放根节点内存。...接着比较根节点的值与目标值,如果相等则返回根节点指针。 如果根节点值不等于目标值,就先递归地在左子树中查找,若在左子树中找到了(返回的指针不为 NULL),则直接返回找到的节点指针。...求二叉树的高度 二叉树的高度定义为根节点到叶节点最长路径上的节点数,可以通过递归计算左子树高度和右子树高度,取较大值再加 1(根节点这一层)来得到整棵树的高度。...然后递归地计算左子树的高度和右子树的高度,通过 std::max 函数取两者中的较大值,再加上 1(代表根节点所在的这一层),得到整棵二叉树的高度并返回。...,先递归遍历左子树,然后输出当前节点的值,最后递归遍历右子树,这样就按照中序遍历的顺序输出了二叉树的各个节点值,一定程度上展示了二叉树的结构情况。

    6410

    算法和编程面试题精选TOP50!(附代码+解题思路+答案)

    下面是关于链表的一些最常见、热门的面试问题,大家可以着重练习: ▌1.如何在一次递归后找到单链表的中间元素?...解决方法和代码: http://www.java67.com/2016/07/how-to-reverse-singly-linked-list-in-java-example.html ▌4.如何在没有递归的情况下反转单链表...因此,你会发现很多问题基于它们的问题,如计算节点数,如何进行遍历,计算深度,判断它们是否平衡。 解决二叉树问题的关键是要有扎实的知识理论,如什么是二叉树的大小或深度,什么是叶,以及什么是节点。...解决方法与代码: http://www.java67.com/2016/08/binary-tree-inorder-traversal-in-java.html ▌5.在不使用递归的情况下,如何使用中序遍历输出给定二叉树的所有节点...解决方法与代码: http://www.java67.com/2016/10/binary-tree-post-order-traversal-in.html ▌7.在不使用递归的情况下,如何对二叉树进行后序遍历

    4.6K30

    二叉树构建,先序,中序,后序遍历(以及非递归实现),广度优先遍历

    二叉树简介 二叉树的相关概念,如,树高度,节点层数,节点度数,路径,叶节点,分支节点,根节点,父节点,左节点,右节点,兄弟节点,祖先节点,子孙节点,左子树,右子树等基本概念,不再赘述,可参见百度百科:二叉树...一维数组可以作为完全二叉树的存储结构,堆排序使用的数据结构就是完全二叉树。...如下如所示,一棵普通二叉树及其扩充二叉树: image.png (4)平衡二叉树 是一棵空树或它的任意节点的左右两个子树的高度差的绝对值不超过1。...这样子我们就在前序序列和中序序列中找到了左右子书对应的子序列,然后再递归处理即可。...如果P不存在左孩子和右孩子,则可以直接访问它并出栈; (b)如果R存在左孩子或者右孩子,但是其左孩子和右孩子都已被访问过了,则同样可以直接访问该结点并出栈; (c)若非上述两种情况,则将R的右孩子和左孩子依次入栈

    20.2K56

    二叉树的基本操作

    前面我们了解了 二叉树的基本概念,以及二叉树的三种遍历方式,今天我们来学习二叉树的基本操作 1....:" + num); } } 1.4 获取二叉树的高度 实现方法: 判断根节点是否为空(如果根节点为空则这棵树为空树),返回0 如果不为空,则计算根节点的左子树和右子树的高度 返回子树的最高层+...1 getHeight方法: /** * 获取二叉树的高度 * @param root * @return */ public int getHeight...int height = binaryTree.getHeight(root); System.out.println("二叉树的高度:" + height);...递归在左子树中查找值,如果在左子树中找到了值,则返回找到的节点; 如果没在左子树找到值,则递归在右子树中查找值,如果在右子树中找到了值,则返回找到的节点; 如果左右子树都没有找到值,则返回null find

    10410

    【初阶数据结构】节点层级的逻辑乐章:二叉树

    本章节是树结构的最后一篇——二叉树,这里我们只实现最简单的二叉树结构,在C++语法部分将学习更高阶的AVL树、红黑树巩固 1.二叉树的结构 typedef int BTDataType; typedef...的 if 条件句既是为了表示空树的情况,也是为了结束向下递归的过程 测试结果: 2.4 二叉树的中序遍历 void InOrder(BTNode* root) { if (root == NULL)...TreeHeight(root->left) + 1 : TreeHeight(root->right) + 1; } 二叉树高度获取的思想和二叉树结点个数是一致的,高度取决于左子树和右子树路径较长的那条...,直接比较然后递归取值即可 但是这段代码有个问题,比较时需要递归一次,比较完并没有保存每个节点高度的结果,获取结果的时候又要再递归一次,导致代码效率减慢 ⌨️优化代码: int TreeHeight(BTNode...再次递归调用时传入 k - 1 即 1,此时满足 k == 1 的条件,返回 1 表示找到了一个第 3 层的节点 通过不断地递归调用并使用 k - 1 作为新的层数参数,最终可以准确计算出二叉树中第

    3600

    平衡二叉树(java)

    本题中,一棵高度​​平衡二叉树​​定义为:一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1 。...:如果二叉树的每个节点的左右子​​树的高度​​差的绝对值不超过 1,则是平衡二叉树。...根据题目定义,解题思路如涌泉般喷发,老规矩,递归破题(若一棵二叉树是平衡二叉树,必须满足其所有子树也都是平衡二叉树才行),且递归的顺序可以是自顶向下或者自底向上,如上两种递归顺序我都给大家讲解一下。...方法一:自顶向下的递归        自顶向下顺序,这做法就类似于二叉树的前序遍历,即对于当前遍历到的节点: 首先计算左右子树的高度,如果左右子树的高度差是否不超过1, 再分别递归地遍历左右子节点,并判断左子树和右子树是否平衡...使用自底向上的递归,每个节点的计算高度和判断是否平衡都只需要处理一次,最坏情况下需要遍历二叉树中的所有节点,因此时间复杂度是 O(n)。 空间复杂度:O(n),其中n是二叉树中的节点个数。

    20630

    数据结构_二叉树和堆(未完

    树不能为空,即树至少有一个结点;二叉树可以为空,因为二叉树是一种为了存储数据而创造出来的结构 从上图可以看出: 结点的度最大为2 二叉树的子树有次序之分,左子树和右子树不能颠倒 任何的二叉树都是由以下几种情况构成的...而完全二叉树的数组存储方式,其实就是堆的基本结构。在现实中使用中,也只有堆会用数组来存储。...二叉树的链式存储又分为二叉链和三叉链,当前使用的主要是二叉链,以后的红黑树等就会用到三叉链。...由于非完全二叉树会造成空间存储上的不连续,因此一般**只有完全二叉树才使用顺序存储** 物理存储上说数组,逻辑存储上是把数组想形成完全二叉树 如何在数组中找到某个结点的父结点或子结点呢 根据二叉树的性质...为了降低学习成本,先在这里手动构建一个不标准的二叉树,方便学习的理解 ```c typeof int BTDataType; typeof struct BinaryTreeNode { BTDataType

    26030

    LeetCode算法-树的遍历

    空间复杂度:O(height):height为二叉树的最大深度。在平均情况下,二叉树的高度与节点个数为对数关系,即 O(logN)。而在最坏情况下,树形成链状,空间复杂度为 O(N)。...翻转二叉树思路:方法一使用广度优先遍历,在遍历树的过程中,交换当前层级下的左右子树方法二使用递归解决,递归最重要的是定义子问题。...空间复杂度:O(height):height为二叉树的最大深度。在平均情况下,二叉树的高度与节点个数为对数关系,即 O(logN)。而在最坏情况下,树形成链状,空间复杂度为 O(N)。...;复杂度分析:时间复杂度:O(n):n为二叉树节点数。空间复杂度:O(n):n为二叉树节点数。递归调用的栈深度取决于二叉树的高度,二叉树最坏情况下为一条链,此时高度为 N,因此空间复杂度为 O(N)。...空间复杂度:O(n):最差情况下,空间复杂度为O(n)。二叉树的所有路径思路:本题考虑使用深度优先遍历。如果当前节点有左子树或右子树,就递归调用函数,直到左右子树都不存在,此时就是我们要找的的路径。

    66530

    二叉树的详解与实现「建议收藏」

    简介 二叉树的相关概念,如,树高度,节点层数,节点度数,路径,叶节点,分支节点,根节点,父节点,左节点,右节点,兄弟节点,祖先节点,子孙节点,左子树,右子树等基本概念,不再赘述。...一维数组可以作为完全二叉树的存储结构,堆排序使用的数据结构就是完全二叉树。...4、平衡二叉树 是一棵空树或它的任意节点的左右两个子树的高度差的绝对值不超过1 二叉树的应用场景 普通的二叉树,很难构成现实的应用场景,但因其简单,常用于学习研究,平衡二叉树则是实际应用比较多的。...2、红黑树: 平衡二叉树,广泛用在C++的STL中。如map和set都是用红黑树实现的。还有Linux文件管理。 3、B/B+树: 用在磁盘文件组织 数据索引和数据库索引。...参考链接 二叉树的重建,只能在提供前序+中序,或者后序+中序的情况下,才可以正常的重构。

    32720

    JavaScript刷LeetCode拿offer-树的遍历

    空间复杂度:O(height):height为二叉树的最大深度。在平均情况下,二叉树的高度与节点个数为对数关系,即 O(logN)。而在最坏情况下,树形成链状,空间复杂度为 O(N)。...翻转二叉树思路:方法一使用广度优先遍历,在遍历树的过程中,交换当前层级下的左右子树方法二使用递归解决,递归最重要的是定义子问题。...空间复杂度:O(height):height为二叉树的最大深度。在平均情况下,二叉树的高度与节点个数为对数关系,即 O(logN)。而在最坏情况下,树形成链状,空间复杂度为 O(N)。...;复杂度分析:时间复杂度:O(n):n为二叉树节点数。空间复杂度:O(n):n为二叉树节点数。递归调用的栈深度取决于二叉树的高度,二叉树最坏情况下为一条链,此时高度为 N,因此空间复杂度为 O(N)。...空间复杂度:O(n):最差情况下,空间复杂度为O(n)。二叉树的所有路径思路:本题考虑使用深度优先遍历。如果当前节点有左子树或右子树,就递归调用函数,直到左右子树都不存在,此时就是我们要找的的路径。

    45420

    JavaScript刷LeetCode拿offer-树的遍历

    空间复杂度:O(height):height为二叉树的最大深度。在平均情况下,二叉树的高度与节点个数为对数关系,即 O(logN)。而在最坏情况下,树形成链状,空间复杂度为 O(N)。...翻转二叉树思路:方法一使用广度优先遍历,在遍历树的过程中,交换当前层级下的左右子树方法二使用递归解决,递归最重要的是定义子问题。...空间复杂度:O(height):height为二叉树的最大深度。在平均情况下,二叉树的高度与节点个数为对数关系,即 O(logN)。而在最坏情况下,树形成链状,空间复杂度为 O(N)。...;复杂度分析:时间复杂度:O(n):n为二叉树节点数。空间复杂度:O(n):n为二叉树节点数。递归调用的栈深度取决于二叉树的高度,二叉树最坏情况下为一条链,此时高度为 N,因此空间复杂度为 O(N)。...空间复杂度:O(n):最差情况下,空间复杂度为O(n)。二叉树的所有路径思路:本题考虑使用深度优先遍历。如果当前节点有左子树或右子树,就递归调用函数,直到左右子树都不存在,此时就是我们要找的的路径。

    40220

    数据结构 之 二叉树

    在我之前的文章栈中讲到,栈可以将递归转化成循环,故二叉树的很多递归实现的操作,都可以依靠栈来转换成循环,并且写法并不困难,但在该篇文章中,我并没用用非递归的方法实现这些方法,如果有兴趣的朋友,可以自己尝试以下非递归的写法...如上图所示,层序遍历的结果应该是 A B C D E F G 如果要使用层序遍历遍历二叉树的节点,那么就需要使用到之前我们学习的数据结构,也就是队列: 以上图为例: 我们要想按每一层的从左到右的顺序来打印二叉树...,我们就需要将二叉树的每一层的节点从左到右存在某一种结构中,再这种情况下,我们使用栈来存放二叉树的节点; 首先我们先创建一个队列,我们先将A节点存入队列中 我们将队列中的队头元素,也就是A节点弹出来并进行打印...,根节点,右子树,那么,只要我们在中序遍历中找到二叉树的根节点,他的左边的元素都是他的左树,右边的元素都是他的右树; 如图: 依然用之前的二叉树的图 该树的前序遍历的结果为: A B D E C...(tree.getKNodeCount(root, 3)); } } 获取二叉树的高度: 二叉树的高度是左右子树中最高的一颗树决定的,所以二叉树的高度就为左右子树的高度的最大值:

    10610

    数据结构+算法(第12篇)玩平衡二叉树就像跷跷板一样简单!

    平衡二叉树是什么鬼? 满足如下两个条件的二叉树称为“平衡二叉树”: 首先它得是二分查找树 然后它的左右子树的高度相差不超过1 ? 图1 平衡二叉树 ?...对于问题2,取决于问题1采用哪种方式——如果采用递归式算法,那么在递归的时候,也顺便把高度递归计算了;如果采用非递归式,那么就在自底向上归并的时候,动态计算高度。 问题3才是真正的新鲜问题。...这样变换之后,A、A的左子树下降,B、B的右子树上升,高度差变小。 因为任意非叶子节点A,它的值都比其左孩子C的值大,所以它可以变成C的右孩子。...此时H(A)≥H(B.Right)+2,这意味着“旋转”后,B节点的左子树高度与右子树高度相差超过1! 貌似“旋转”对这种情况不凑效了,怎么办呢? 先来分析一下不凑效的根因到底是什么。...二分查找树》中的节点删除算法; 但是平衡二叉树还是特殊的二分查找树,它还要满足左右子树高度相差不超过1的要求。当按照上面的算法删除节点之后,可能会不满足这个要求,因此要进行调整。

    86530
    领券