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;
}
二叉樹的常見問題及其解決程序 http://www.linuxidc.com/Linux/2013-04/83661.htm
【遞歸】二叉樹的先序建立及遍歷 http://www.linuxidc.com/Linux/2012-12/75608.htm
在JAVA中實現的二叉樹結構 http://www.linuxidc.com/Linux/2008-12/17690.htm
【非遞歸】二叉樹的建立及遍歷 http://www.linuxidc.com/Linux/2012-12/75607.htm
二叉樹遞歸實現與二重指針 http://www.linuxidc.com/Linux/2013-07/87373.htm
二叉樹先序中序非遞歸算法 http://www.linuxidc.com/Linux/2014-06/102935.htm
輕松搞定面試中的二叉樹題目 http://www.linuxidc.com/linux/2014-07/104857.htm