首页 > 代码库 > 二叉树(8)----求二叉树第K层的节点数和二叉树第K层的叶子节点数,递归方式
二叉树(8)----求二叉树第K层的节点数和二叉树第K层的叶子节点数,递归方式
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、求二叉树第K层的节点数
(1)递归方式
给定根节点pRoot:
如果pRoot为空,或者层数KthLevel <= 0,则为空树或者不合要求,则返回0;
如果pRoot不为空,且此时层数KthLevel==1,则此时pRoot为第K层节点之一,则返回1;
如果pRoot不为空,且此时层数KthLevel > 1,则此时需要求pRoot左子树(KthLevel - 1 )层节点数和pRoot右子树(KthLevel-1)层节点数;
int GetBTreeKthLevelNodesTotal( BTreeNode_t *pRoot, int KthLevel){ if( pRoot == NULL || KthLevel <= 0 ) return 0; if( pRoot != NULL && KthLevel == 1 ) return 1; return (GetBTreeKthLevelNodesTotal( pRoot->m_pLeft, KthLevel-1) + GetBTreeKthLevelNodesTotal( pRoot->m_pRight, KthLevel - 1 ) ); }
3、求二叉树第K层叶子节点数
(1)递归方式
给定节点pRoot:
如果pRoot为空,或者层数KthLevel <= 0, 则为空树或者是层数非法,则返回0;
如果pRoot不为空,且此时层数KthLevel==1时,需要判断是否为叶子节点:
如果pRoot左右子树均为空,则pRoot为第K层叶子节点之一,则返回1;
如果pRoot左右子树之一存在,则pRoot不是叶子节点,则返回0;
如果pRoot不为空,且此时层数KthLevel > 1,需要返回 KthLevel-1层的左子树和右子树结点数。
int GetBTreeKthLevelLeafNodesTotal( BTreeNode_t *pRoot, int KthLevel){ if( pRoot == NULL || KthLevel <= 0 ) return 0; if( pRoot != NULL && KthLevel == 1 ){ if( pRoot->m_pLeft == NULL && pRoot->m_pRight == NULL ) return 1; else return 0; } return ( GetBTreeKthLevelLeafNodesTotal( pRoot->m_pLeft, KthLevel - 1) + GetBTreeKthLevelLeafNodesTotal( pRoot->m_pRight, KthLevel -1) ); }
二叉树(8)----求二叉树第K层的节点数和二叉树第K层的叶子节点数,递归方式
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。