首页 > 代码库 > 二叉树(7)----求二叉树叶子节点个数,递归和非递归
二叉树(7)----求二叉树叶子节点个数,递归和非递归
1、二叉树定义:
typedef struct BTreeNodeElement_t_ { void *data; } BTreeNodeElement_t; typedef struct BTreeNode_t_ { BTreeNodeElement_t *m_pElemt; struct BTreeNode_t_ *m_pLeft; struct BTreeNode_t_ *m_pRight; } BTreeNode_t;
2、求二叉树叶子节点数
叶子节点:即没有左右子树的结点
(1)递归方式
如果给定节点pRoot为NULL,则是空树,叶子节点为0,返回0;
如果给定节点pRoot左右子树均为NULL,则是叶子节点,且叶子节点数为1,返回1;
如果给定节点pRoot左右子树不都为NULL,则不是叶子节点,以pRoot为根节点的子树叶子节点数=pRoot左子树叶子节点数+pRoot右子树叶子节点数
int GetBTreeLeafNodesTotal( BTreeNode_t *pRoot) { if( pRoot == NULL ) return 0; if( pRoot->m_pLeft == NULL && pRoot->m_pRight == NULL ) return 1; return ( GetBTreeLeafNodesTotal( pRoot->m_pLeft) + GetBTreeLeafNodesTotal( pRoot->m_pRight) ); }
(2)非递归方式
在遍历二叉树时,判断当前访问的节点是不是叶子节点,然后对叶子节点求和即可。
前序、中序、后序、按层遍历均可。
二叉树(7)----求二叉树叶子节点个数,递归和非递归
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。