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层的第M个节点

（1）非递归算法

借助队列实现

首先将给定根节点pRoot入队：

第一步：如果队列未空，获取当前队列的长度，即当前层的节点总数；

第二步：记录当前遍历的层数，判断是否超出指定层数，如果超出则退出；如果小于指定层数，则对当前层的所有左右节点入队操作；如果等于指定 层数，则进行第三步；

第三步：获取当前队列中节点总数，如果当前节点总数小于指定节点数，则退出；如果节点总数大于指定节点数，则进行第四步；

第四步：遍历当前层节点，如果节点数等于指定节点数，则放回此节点。

第三步：循环结束后，如果没有符合条件的节点就返回NULL。

BTreeNode_t? * GetKthLevelMthNode( BTreeNode_t *pRoot, int KthLevel, int MthNode){
? ? if( pRoot == NULL || KthLevel <= 0 || MthNode <= 0 )
? ? ? ? return NULL;

? ? queue que;
? ? que.push( pRoot );//首先将根节点入队

? ? int level = 0;? ? ? //当前层计数器
? ? int cntNode = 0;? //当前层节点数计数器
? ? int curLevelNodesTotal = 0;//当前层节点总数

? ? while( !que.empty() ){

? ? ? ? ++level;
? ? ? ? if( level > KthLevel)//如果层数已大于指定层数，则退出
? ? ? ? ? ? break;
? ? ? ?
? ? ? ?
? ? ? ? cntNode = 0; //当前层节点数计数器归0

? ? ? ? curLevelNodesTotal = que.size();//当前层的节点总数

? ? ? ? while( cntNode < curLevelNodesTotal ){

? ? ? ? ? ? ++cntNode;//记录当前层的节点数
? ? ? ? ? ? pRoot = que.front();
? ? ? ? ? ? que.pop();
? ? ? ?
? ? ? ? ? ? if( level == KthLevel? && cntNode == MthNode ){? //看当前节点的层数和在当前层中的节点次序是否符合要求
? ? ? ? ? ?
? ? ? ? ? ? ? ? break;
? ? ? ? ? ? }

? ? ? ? ? ? //将当前层节点的左右结点均入队，即将下一层节点入队
? ? ? ? ? ? if( pRoot->m_pLeft )
? ? ? ? ? ? ? ? que.push( pRoot->m_pLeft);
? ? ? ? ? ? if( pRoot->m_pRight)
? ? ? ? ? ? ? ? que.push( pRoot->m_Right);
? ? ? ? }
? ? ? ?
? ? ? ? if( level == KthLevel? && cntNode == MthNode ){? //看当前节点的层数和在当前层中的节点次序是否符合要求
? ? ? ? ? ?
? ? ? ? ? ? break;
? ? ? ? }

? ? }?
? ? while( !que.empty()){//清空栈
? ? ? ? que.pop();
? ? }

? ? if( level == KthLevel? && cntNode == MthNode ){? //看当前节点的层数和在当前层中的节点次序是否符合要求
? ? ? ? ? ?
? ? ? ? return pRoot;
? ? }

? ? return NULL;
}

?