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

如何在C中无递归的情况下计算二叉树的叶子个数?

在C语言中,可以使用迭代的方式来计算二叉树的叶子节点个数,而不使用递归。以下是一个实现的示例代码:

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

// 定义二叉树节点结构
typedef struct TreeNode {
    int data;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

// 创建二叉树节点
TreeNode* createNode(int data) {
    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
    if (newNode == NULL) {
        printf("内存分配失败\n");
        exit(1);
    }
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// 计算二叉树叶子节点个数的函数
int countLeaves(TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    
    int count = 0;
    TreeNode* stack[100];  // 使用栈来辅助迭代
    int top = -1;
    TreeNode* current = root;
    
    while (current != NULL || top != -1) {
        while (current != NULL) {
            stack[++top] = current;
            current = current->left;
        }
        
        current = stack[top--];
        
        if (current->left == NULL && current->right == NULL) {
            count++;
        }
        
        current = current->right;
    }
    
    return count;
}

int main() {
    // 创建二叉树
    TreeNode* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    root->right->left = createNode(6);
    root->right->right = createNode(7);
    
    // 计算叶子节点个数
    int leaves = countLeaves(root);
    printf("二叉树的叶子节点个数为:%d\n", leaves);
    
    return 0;
}

上述代码中,首先定义了二叉树节点的结构体,并实现了创建节点的函数createNode。然后,使用迭代的方式计算二叉树的叶子节点个数的函数countLeaves。该函数使用了一个栈来辅助迭代,通过遍历二叉树的所有节点,判断是否为叶子节点,从而计算叶子节点的个数。最后,在main函数中创建了一个二叉树,并调用countLeaves函数来计算叶子节点个数,并输出结果。

这是一个简单的无递归计算二叉树叶子节点个数的实现,可以在C语言中使用。

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

相关·内容

  • C语言练习之计算个数每位之和(递归实现)

    前言 写一个递归函数DigitSum(n),输入一个非负整数,返回组成它数字之和 例如,调用DigitSum(1729),则应该返回1 + 7 + 2 + 9,它和是19 输入:1729,输出:...19 一、思路 1729可以递归分解为172和9; 172可以递归分解为17和2; 17可以递归分解为1和7; 直到只剩下一位数字,即1再进行返回。...二、源代码以及运行截图 为了方便大家交流和学习,我将程序源代码和运行截图放置在下方。...,本文简单介绍了用C语言递归计算个数每位之和思路,还进一步展示了代码运行结果验证了作者思路。...本文作者也只是一个正在学习C语言等编程知识萌新,若这篇文章中有哪些不正确内容,请在评论区向作者指出(也可以私信作者),欢迎大佬们指点,也欢迎其他正在学习C语言萌新和作者进行交流,谢谢大家!

    41120

    C++】二叉树前序序后序非递归实现

    二叉树前序遍历 前序遍历顺序是根、左、右。任何一颗树都可以认为分为左路节点,左路节点右子树。先访问左路节点,再来访问左路节点右子树。...把访问左路节点右子树看成一个子问题,就可以完整递归访问了。 先定义栈st存放节点、v存放值,TreeNode* cur,cur初始化为root。...当cur不为空或者栈不为空时候(一开始栈是空,cur不为空),循环继续:先把左路节点存放进栈,同时把值存入v,一直循环,直到此时左路节点为空,访问结束。...cur = top->right;//转化成子问题访问右子树 } return v; } }; ---- 二叉树序遍历...、序遍历、后序遍历递归遍历三种方法都是类似的,差别在于访问栈顶元素时机不同,访问控制不同。

    22210

    数据结构从入门到精通——二叉树实现

    计算二叉树节点个数可以通过遍历树所有节点来实现,例如使用前序遍历、序遍历或后序遍历等方法。在遍历过程,每访问一个节点,就将计数器加1,最终计数器值就是二叉树节点个数。...如果根节点为空,返回0;如果根节点是叶子节点(即没有左右子节点),返回1;否则,递归计算左子树和右子树叶子节点数量并返回它们和。 二叉树叶子节点是指没有子节点节点。...要计算二叉树叶子节点个数,可以采用递归或迭代方法。递归方法基本思路是,对于每个节点,如果它是叶子节点,则计数加1;否则,递归计算其左右子树叶子节点个数并相加。...迭代方法则可以利用队列或栈等数据结构,层次遍历或深度优先遍历二叉树,统计叶子节点个数。无论采用哪种方法,最终得到叶子节点个数即为二叉树叶子节点总数。...二叉树第k层节点个数可以通过递归或迭代方法计算。在递归方法,对于给定二叉树,我们首先检查根节点是否为空。如果为空,则树为空,返回0。

    14010

    【数据结构】关于二叉树你不得不会操作--实现链式二叉树超详解

    )层序遍历 5)遍历测试 5、判断是否为完全二叉树 6、二叉树销毁 7、二叉树节点个数 8、二叉树叶子结点个数 9、二叉树第K层节点个数 10、二叉树查找值为x节点 11、二叉树深度 四、测试 一、...*root); *root = NULL;//释放并且置空 } 递归展开图: 注:画递归图是一个理解递归操作很好方式 7、二叉树节点个数 注意: 为空树不计数 不为空树则计数1,并且递归获取左右子树节点个数...} 8、二叉树叶子结点个数 注意: 叶子结点特点是左右子树都为空树 如果当前节点为空树则计数0 如果当前节点左右子树都为空树则计数1 不为叶子结点则继续递归计数 抽象化思想: 叶子结点个数=...=左右子树叶子结点个数(当前节点不为叶子结点的话) 参考代码: // 二叉树叶子节点个数 int BinaryTreeLeafSize(BTNode* root) { if (root == NULL...对于如何控制递归深度,这里我们使用k来控制递归层数 首先判断k合理性 抽象化思想: 第k层节点==左右子树第k层结点个数(当前节点不为第k层的话) 参考代码: // 二叉树第k层节点个数 int

    40030

    C语言计算整数二进制位1个数

    前言 在计算存储数据/信息/代码,是以二进制方式存储,所以我们为了更加了解计算运行方式,需要去了解一下关于计算二进制位1和0个数方法。...本文是关于C语言中计算整数二进制位1个数三个方法。 一、关于一个整数二进制表示方法 整数包括:正整数、负整数、零。...二、计算二进制1方法 1.取余法 注意:本方法只能争对非负整数 将一个非负整数进行转变为计算存储二进制,本质上就是对该非负整数,不断地对2整除和取余....2.移位法 在C语言中,右移运算符(按二进制形式把所有的数字向右移动对应位数,低位移出(舍弃),高位空位补符号位,即正数补零,负数补1)可以帮助我们完成计算二进制1个数。...3.高级计算法 例:将11二进制1个数求出: 代码: #include int main() { int a = 11; int count = 0; while (

    63240

    树和二叉树

    术语 节点度:一个节点含有的子树个数称为该节点度; 树度:一棵树,最大节点度称为树度; 叶子节点或终端节点:度为零节点; 非终端节点或分支节点:度不为零节点; 父节点:若一个节点含有子节点...在任意一棵二叉树,若终端结点个数为 n0,度为 2 结点数为 n2,则 n0=n2+1。 满二叉树 除了叶子节点之外,每个节点都有左右两个子节点,这种二叉树就叫作满二叉树。...完全二叉树 叶子节点都在最底下两层,最后一层叶子节点都靠左排列,并且除了最后一层,其他层节点个数都要达到最大,这种二叉树叫作完全二叉树。...通过这种方式,我们只要知道根节点存储位置(一般情况下,为了方便计算子节点,根节点会存储在下标为 1 位置),这样就可以通过下标计算,把整棵树都串起来。...二叉查找树要求,在树任意一个节点,其左子树每个节点值,都要小于这个节点值,而右子树节点值都大于这个节点值。 二叉查找树查找 首先,我们看如何在二叉查找树查找一个节点。

    80020

    前端进阶必备二叉树知识

    若一棵度为4树中度为2丶3丶4结点个数分别为3丶2丶2,则该树叶子结点个数是多少? 答案: 在树,结点有几个分叉,度就是几。 树结点数 = 总分叉树 + 1。...❞ ❝ 深度为h二叉树最多有2^h - 1个节点 ❞ ❝ n0: 指度(分叉)为0结点 n1:指度(分叉)为1结点 n2:指度(分叉)为2结点 ❞ ❝ 二叉树叶子节点个数等于度为2节点个数...假设二叉树每个结点值为单个字符,采用二叉树链存储结构存储。设计一个算法计算给定二叉树b所有单分支结点个数。...答案: 计算一棵二叉树所有单分支结点个数递归模型f(b)如下: f(b) = 0 若b = NULL; f(b) = f(b -> lchild) + f(b -> rchild) + 1;...若b不为空,当前结点层次为K,并且b为叶子结点,则num增1,递归递归调用num1 = LevelkCount(b -> child, k, h+1)求出左子树第K层结点个数num1, 递归调用

    1.1K00

    算法和编程面试题精选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/09/how-to-print-all-leaf-nodes-of-binary-tree-in-java.html ▌9.如何计算一个给定二叉树叶子节点数目

    4.4K30

    【数据结构】C语言实现链式二叉树(附完整运行代码)

    二叉树判空 二叉树先序遍历 二叉树序遍历 二叉树后序遍历 二叉树层序遍历 二叉树叶子结点数 二叉树左孩子节点数 二叉树右孩子节点数 二叉树结点数 二叉树高度 查询二叉树某层结点个数...= NULL) { QueuePush(&q, front->right); } } QueueDestroy(&q); } 10.实现链式二叉树叶子节点数计算 叶子结点计算上我们采用递归分治思想...(root->left) + BinaryTreeLeafSize(root->right);//返回每颗子树左右叶子节点数 } 11.实现链式二叉树左孩子节点数计算 左孩子结点计算上我们同样采用递归分治思想...该函数递归展开和叶子节点计算类似,这里就不赘述了,代码实现如下: //树结点个数 int TreeSize(BTNode* root) { if (root == NULL) return 0...leftHeight + 1 : rightHeight + 1 ; //返回左子树和右子树高那个并加上自己那份 } 15.实现链式二叉树查询某层结点个数 某层结点计算我们同样采用递归分治思想

    13310

    二叉树基本操作(如何计算二叉树结点个数,二叉树高度)

    个人主页: :✨✨✨初阶牛✨✨✨ 推荐专栏1: C语言初阶 推荐专栏2: C语言进阶 个人信条: 知行合一 本篇简介:>:讲解二叉树如何计算二叉树结点个数,叶子结点个数,二叉树高度,第k...层结点个数,以及在二叉树如何查找查找目标值....方法二:如果是全局变量,可以实现在每次递归过程累加效果,但是进行第二次计算时,全局变量需要清零重新计算,否则会继续累加.全局变量终究是不妥当安全....return left + right + 1;//左子树结点个数+右子树结点个数+自己本身 } 二、计算二叉树叶子结点个数....提示: 二叉树 经常使用递归算法,不理解时可以画代码递归展开图,一层层分析.更加方便理解 叶子结点:度为0节点称为叶节点 当一个结点 左子树和 右子树都是NULL时,该结点便是叶子结点.

    1.8K31

    数据结构与算法 -- 二叉树链式详解((非)递归遍历,叶子个数,深度计算

    二叉树不是树一种特殊情形,主要差别: 树结点最大度数没有限制,而二叉树结点最大度数为2; 树结点左、右之分,而二叉树结点有左、右之分。...二叉树类型 (1)完全二叉树 ——若设二叉树高度为h,除第 h 层外,其它各层 (1~h-1) 结点数都达到最大个数,第h层有叶子结点,并且叶子结点都是从左到右依次排布,这就是完全二叉树。...(2)满二叉树 ——除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层二叉树。...当我们在键盘上敲了一行char类型数据,可以按照一定结构储存在计算机上,就要写一个算法,二叉树分左右孩子,所以,如果没有左(右)孩子就输入一个空格或者#,代表空。...递归思想就是把一个大问题分成多个类似的小问题解决。 4:叶子个数 方法:查找一个结点没有左右孩子,就是叶子结点。

    61150

    【数据结构】二叉树链式结构实现

    遍历是二叉树上最重要运算之一,也是二叉树上进行其它运算基础 按照规则,二叉树遍历有: 前序 / 序 / 后序递归结构遍历 : 1....我们再回归到这个题,我们可以用先序遍历创建二叉树,我们现将数组首地址以及下标地址传进函数,如果数组里值为‘#’此处创建空节点,若不是,开辟一个二叉树结构体空间,左右孩子子树也是这么创建,子问题思路相同符合先序遍历递归...,代码在上面打过了 2.二叉树节点个数 二叉树遍历与构建都清楚了,那我们如何用代码统计二叉树节点个数,我们想想如果二叉树节点为空,那么个数就返回0,若不为空,就是自身节点算一个,左孩子节点个数加右孩子节点个数加...3.二叉树叶子结点个数 叶子节点他左孩子与右孩子都为空节点,我们计算二叉树叶子结点个数,跟计算节点个数类似,只不过此刻不需要加自身,只需要计算每个节点左孩子叶子节点个数加右孩子叶子节点个数就行了...,不返回最后一行叶子结点个数,返回任意一行节点个数 假如我返回第三行节点个数,那在我们遍历过程,我们如何确定节点是否是第三行那,我们有图可以过一行K减一,只要向下递归一行K减一,到目标行第三行K就是

    8110

    二叉树详解(深度优先遍历、前序,序,后序、广度优先遍历、二叉树所有节点个数、叶节点个数)

    ,实际树有很多种表示方式,:双亲表示法,孩子表示法、孩子兄弟表示法等等。...某二叉树共有 399 个结点,其中有 199 个度为 2 结点,则该二叉树叶子结点数为( ) A 不存在这样二叉树 B 200 C 198 D 199 2.在具有 2n 个结点完全二叉树...,叶子结点个数为( ) A n B n+1 C n-1 D n/2 3.一棵完全二叉树节点数位为531个,那么这棵树高度为( ) A 11 B 10 C 8 D 12 四、...); // 递归遍历右子树 PostOrder(root->right); // 访问当前节点数据 printf("%c ", root->data); } 4.4二叉树所有节点个数...= NULL) return 1; // 递归计算左子树和右子树叶子节点数量,并返回它们和 return TreeSize(root->left) +

    2.3K10

    二叉树链式结构实现(二叉树遍历以及各种常用功能函数实现)

    二叉树遍历递归思想可以很自然地应用,因为遍历左子树和右子树本质上就是对规模更小子树进行遍历 二叉树遍历(Traversal)是指按照一定规则,依次访问二叉树所有节点,每个节点只被访问一次...二叉树遍历有:前序/序/后序递归结构遍历和层序遍历 前序遍历(Preorder Traversal):先访问根节点,再访问左子树,最后访问右子树(根>左>右) 序遍历(Inorder Traversal...3.1二叉树节点个数 同样是递归 计算二叉树节点个数问题就是计算左子树节点个数计算右子树节点个数两个子问题 对于当前节点,我们需要计算以当前节点为根子树节点个数。...如果当前节点左右子树均为空,即 root->left == NULL && root->right == NULL,则表示当前节点为叶子节点,返回 1 不是叶子节点,则需要计算以当前节点为根子树叶子节点个数...这个节点本身不是叶子节点,所以我们将问题拆分为计算左子树叶子节点个数计算右子树叶子节点个数两个子问题,然后将左右子树叶子节点个数相加,即 TreeLeafSize(root->left) + TreeLeafSize

    10110

    Leetcode No.129 求根节点到叶节点数字之和

    一、题目描述 给你一个二叉树根节点 root ,树每个节点都存放有一个 0 到 9 之间数字。...<= 9 树深度不超过 10 二、解题思路 这道题中,二叉树每条从根节点到叶子节点路径都代表一个数字。...只要计算出每个叶子节点对应数字,然后计算所有叶子节点对应数字之和,即可得到结果。可以通过深度优先搜索实现。 深度优先搜索是很直观做法。...从根节点开始,遍历每个节点,如果遇到叶子节点,则将叶子节点对应数字加到数字之和。如果当前节点不是叶子节点,则计算其子节点对应数字,然后对子节点递归遍历。...空间复杂度:O(n),其中 n 是二叉树节点个数。空间复杂度主要取决于递归调用栈空间,递归深度等于二叉树高度,最坏情况下二叉树高度等于节点个数,空间复杂度为 O(n)。

    19710
    领券