歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
Linux教程網 >> Linux編程 >> Linux編程 >> 打印二叉樹中第K層的第M個節點,非遞歸算法

打印二叉樹中第K層的第M個節點,非遞歸算法

日期:2017/3/1 9:34:54   编辑:Linux編程

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

Copyright © Linux教程網 All Rights Reserved