這篇文章主要介紹了C++非遞歸隊(duì)列實(shí)現(xiàn)二叉樹的廣度優(yōu)先遍歷,實(shí)例分析了遍歷二叉樹相關(guān)算法技巧,并附帶了兩個(gè)相關(guān)算法實(shí)例,需要的朋友可以參考下

本文實(shí)例講述了C++非遞歸隊(duì)列實(shí)現(xiàn)二叉樹的廣度優(yōu)先遍歷。分享給大家供大家參考。具體如下：

廣度優(yōu)先非遞歸二叉樹遍歷(或者說層次遍歷)：

1. void widthFirstTraverse(TNode* root) { 
2. queue<TNode*> q; // 隊(duì)列 
3. q.enqueue(root); 
4. TNode* p; 
5. while(q.hasElement()) { 
6. p = q.dequeue(); // 隊(duì)首元素出隊(duì)列 
7. visit(p); // 訪問p結(jié)點(diǎn) 
8. if(p->left) 
9. q.enqueue(p->left); 
10. if(p->right) 
11. q.enqueue(p->right); 
12. }  
13. } 

附帶兩個(gè)相關(guān)示例：

1. 遞歸先序遍歷二叉樹

1. void preTraverse(TNode* root) { 
2. if(!root) 
3. return; 
4. visit(root); 
5. preTraverse(root->left); 
6. preTraverse(root->Right); 
7. } 

2. 非遞歸先序遍歷二叉樹

1. void preTraverseNonRecursive(TNode* root) { 
2. stack<TNode> stack; // 棧 
3. stack.push(root); 
4. TNode* p; 
5. while(!stack.isEmpty()) { // 棧非空 
6. p = stack.pop(); 
7. visit(p); 
8. if(p->pRight) 
9. s.push(p->pRight); 
10. if(p->pLeft) 
11. s.push(p->pLeft); 
12. } 
13. } 

希望本文所述對(duì)大家的C++程序設(shè)計(jì)有所幫助。