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 ) );
}（2）非递归方式
借助队列实现：
int GetKthLevelNodesTotal( BTreeNode_t *pRoot, unsigned int KthLevel ){
if( pRoot == NULL )
return 0;
queue <BTreeNode_t *> que;
que.push( pRoot );
int curLevelNodesTotal = 0;
int curLevel = 0;
while( !que.empty() ){
++curLevel;//当前层数
curLevelNodesTotal = que.size();
if( curLevel == KthLevel )//假设层数等于给定层数
break;
int cntNode = 0;
while( cntNode < curLevelNodesTotal){//将下一层节点入队
++cntNode;
pRoot = que.front();
que.pop();
if( pRoot->m_pLeft != NULL )
que.push(pRoot->m_pLeft);
if( pRoot->m_pRight != NULL )
que.push( pRoot->m_pRight);
}
}
while ( !que.empty() )
que.pop();
if( curLevel == KthLevel )
return curLevelNodesTotal;
return 0; //假设KthLevel大于树的深度
}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) );
}（2）非递归方式
借助队列实现
int GetKthLevelNodesTotal( BTreeNode_t *pRoot, unsigned int KthLevel ){
if( pRoot == NULL )
return 0;
queue <BTreeNode_t *> que;
que.push( pRoot );
int curLevelNodesTotal = 0;
int curLevel = 0;
while( !que.empty() ){
++curLevel;//当前层数
curLevelNodesTotal = que.size();
if( curLevel == KthLevel )//假设层数等于给定层数
break;
int cntNode = 0;
while( cntNode < curLevelNodesTotal){//将下一层节点入队
++cntNode;
pRoot = que.front();
que.pop();
if( pRoot->m_pLeft != NULL )
que.push(pRoot->m_pLeft);
if( pRoot->m_pRight != NULL )
que.push( pRoot->m_pRight);
}
}
if( curLevel == KthLevel ){
int cntNode = 0;
int leafNodes = 0;
while( cntNode < curLevelNodesTotal ){
++cntNode;
pRoot = que.front();
que.pop();
if( pRoot->m_pLeft == NULL && pRoot->m_pRight == NULL )
leafNodes++;
}
return leafNodes; //返回叶子节点数
}
return 0; //假设KthLevel比树的深度大于
}版权声明：本文博客原创文章，博客，未经同意，不得转载。