首页 > 代码库 > 二叉树(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;
    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;
}









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