首页 > 代码库 > 二叉树(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个节点,非递归算法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。