首页 > 代码库 > 二叉树(9)----打印二叉树中第K层的第M个节点,非递归算法

二叉树(9)----打印二叉树中第K层的第M个节点,非递归算法

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 <BTreeNode_t *> que;
    int level = 1;
    int cntNode = 0;
    int curLevelTotal = 0;
    que.push( pRoot );
    while( !que.empty() ){
        curLevelTotal = que.size();
        while( cntNode < curLevelTotal ){
            ++cntNode;
            pRoot = que.front();
            que.pop();
        
            if( level == KthLevel  && cntNode == MthNode )
                return pRoot;

            if( pRoot->m_pLeft )
                que.push( pRoot->m_pLeft);
            if( pRoot->m_pRight)
                que.push( pRoot->m_Right);
        }
        cntNode = 0;
        ++level;
    }

    return NULL;
}



二叉树(9)----打印二叉树中第K层的第M个节点,非递归算法