由于遞歸算法相對于非遞歸算法來說效率通常都會更低，遞歸算法會有更多的資源需要壓棧和出棧操作（不僅僅是參數(shù)，還有函數(shù)地址等）由于編譯器對附加的一些棧保護(hù)機制會導(dǎo)致遞歸執(zhí)行的更加低效，使用循環(huán)代替遞歸算法，通常可以獲得更好的執(zhí)行效率和空間效率，在二叉樹層次較深的情況下，采用非遞歸方式遍歷能夠有效的提升遍歷的性能。

二叉樹的非遞歸遍歷分為三種：先序非遞歸遍歷，中序非遞歸遍歷和后續(xù)非遞歸遍歷。這和遞歸遍歷的結(jié)果是一樣的，區(qū)別只是在于采用了循環(huán)結(jié)構(gòu)。

先序非遞歸遍歷

采用輔助數(shù)據(jù)結(jié)構(gòu)棧來實現(xiàn)，先序遍歷是按照先根，后左子樹，再右子樹的順序進(jìn)行遞歸訪問的。由于棧是先入后出的，所以入棧順序為先右孩子后左孩子。
非遞歸的算法是先將根結(jié)點入棧，棧不為空時：根結(jié)點出棧并訪問，然后將右孩子入棧，再將左孩子入棧；左孩子出棧并訪問，它的孩子也是按照先右后左順序分別入棧，如此往復(fù)直至棧為空結(jié)束。代碼如下：

void preorderNoRecursion(btNode* p) {if (p != NULL){int top = -1;btNode* stack[50];//建立大小為50個結(jié)點的棧btNode* temp;stack[++top] = p;while (top != -1){temp = stack[top--];std::cout << temp->data << ' ';if (temp->rc != NULL)stack[++top] = temp->rc;//先讓右孩子入棧if (temp->lc != NULL)stack[++top] = temp->lc;//再讓左孩子入棧}} }

先序非遞歸根結(jié)點先入棧，然后以棧不為空為循環(huán)判定條件。

中序非遞歸遍歷

輔助數(shù)據(jù)結(jié)構(gòu)仍采用棧，為實現(xiàn)左-根-右的訪問順序，中序遍歷的第一個結(jié)點為最左邊的那個結(jié)點，據(jù)此，可以先從根結(jié)點開始入棧，沿著最左邊的那條分支依次入棧，這樣棧頂元素就是中序遍歷中的第一個結(jié)點了。
接下來需要做的是當(dāng)棧中元素出棧并被訪問后，若該結(jié)點有右孩子怎么辦？這時，從該結(jié)點的右孩子開始，按照最左邊分支將結(jié)點依次入棧，出棧時進(jìn)行訪問。由此往復(fù)，直至結(jié)束。代碼如下：

void inorderNoRecursion(btNode* p) {if (p == NULL)return;btNode* stack[50];int top = -1;btNode* temp = p;while (temp!=NULL||top!=-1)//只有temp等于null且top等于-1才退出{while (temp!=NULL)//先將左分支入棧。{stack[++top] = temp;temp = temp->lc;}if (top!=-1)//出棧時temp指向出棧結(jié)點的右孩子，進(jìn)行下一輪循環(huán){temp = stack[top--];std::cout << temp->data << ' ';temp = temp->rc;}}}

中序非遞歸遍歷根結(jié)點先不入棧，循環(huán)判定條件有兩個。

后序非遞歸遍歷

這里列出一種比較好理解的后續(xù)非遞歸遍歷，它的思路可以看下面的例子

對上圖中的A，B，C三個結(jié)點來講：
先序遍歷為：A，B，C
后序遍歷為：B，C，A
二者之間的聯(lián)系在于，如果將先序遍歷順序的根-左-右改為根-右-左，即交換訪問次序，遍歷結(jié)果為A，C，B，然后將其結(jié)果逆序，得B，C，A。這剛好是后序遍歷的結(jié)果。

對上圖中的所有結(jié)點來講：
先序遍歷為：A，B，D，E，C，F
交換次序后的結(jié)果為：A，C，F，B，E，D
再逆序：D，E，B，F，C，A
而后序遍歷的結(jié)果也為：D，E，B，F，C，A
由此可得：
先序+交換+逆序=后序

void postorderNoRecursion(btNode* p) {if (p != NULL){btNode* stack1[50];//棧1為輔助棧btNode* stack2[50];//棧2為訪問棧int top1 = -1, top2 = -1;btNode* temp;stack1[++top1] = p;while (top1 != -1)//修改先序非遞歸遍歷進(jìn)行交換{temp = stack1[top1--];stack2[++top2] = temp;if (temp->lc != NULL)stack1[++top1] = temp->lc;//先入左孩子結(jié)點if (temp->rc != NULL)stack1[++top1] = temp->rc;//后入右孩子結(jié)點}while (top2 != -1)//再逆序std::cout << stack2[top2--]->data << ' ';//訪問棧2中的數(shù)據(jù)} }

完整示例

關(guān)于二叉樹非遞歸遍歷的完整代碼如下：

#include<iostream> typedef struct btNode {char data;//結(jié)點中的信息struct btNode* lc;//左孩子結(jié)點struct btNode* rc;//右孩子結(jié)點 }btNode;btNode* initial(char* ele, int num);//用數(shù)組初始化一棵樹 void level(btNode* p);//層序遍歷 void preorderNoRecursion(btNode* p);//先序非遞歸遍歷 void inorderNoRecursion(btNode* p);//中序非遞歸遍歷 void postorderNoRecursion(btNode* p);//后序非遞歸遍歷 int main() {using namespace std;char data[6] = { 'a', 'b', 'c', 'd', 'e', 'f' };btNode* p = initial(data, 6);cout << "先序非遞歸遍歷： ";preorderNoRecursion(p);cout << endl;cout << "中序非遞歸遍歷： ";inorderNoRecursion(p);cout << endl;cout << "后序非遞歸遍歷： ";postorderNoRecursion(p);cout << endl;cout << "層序遍歷： ";level(p);cout << endl;return 0; } btNode* initial(char* ele, int num) {if (num<1)return NULL;btNode* temp = new btNode[num];int i = 0;while (i < num)//將所有結(jié)點的左右子樹置為空{temp[i].lc = NULL;temp[i].rc = NULL;++i;}i = 0;while (i < num/2)//通過完全二叉樹的順序存儲來創(chuàng)建樹的結(jié)構(gòu){if (2*i+1<num)temp[i].lc = temp + 2 * i + 1;if (2*i+2<num)temp[i].rc = temp + 2 * i + 2;++i;}for (i = 0; i < num; i++)//對樹中的每個結(jié)點賦值temp[i].data = ele[i];return temp; } void preorderNoRecursion(btNode* p) {if (p != NULL){int top = -1;btNode* stack[50];//建立大小為50個結(jié)點的棧btNode* temp;stack[++top] = p;while (top != -1){temp = stack[top--];std::cout << temp->data << ' ';if (temp->rc != NULL)stack[++top] = temp->rc;if (temp->lc != NULL)stack[++top] = temp->lc;}} } void inorderNoRecursion(btNode* p) {if (p == NULL)return;btNode* stack[50];int top = -1;btNode* temp = p;while (temp!=NULL||top!=-1)//只有temp等于null且top等于-1才退出（a交b=a逆或b逆）{while (temp!=NULL)//先將左分支入棧。{stack[++top] = temp;temp = temp->lc;}if (top!=-1)//出棧時temp指向出棧結(jié)點的右孩子，進(jìn)行下一輪循環(huán){temp = stack[top--];std::cout << temp->data << ' ';temp = temp->rc;}}} void postorderNoRecursion(btNode* p) {if (p != NULL){btNode* stack1[50];//棧1為輔助棧btNode* stack2[50];//棧2按照后續(xù)遞歸的順序進(jìn)行訪問int top1 = -1, top2 = -1;btNode* temp;stack1[++top1] = p;while (top1 != -1){temp = stack1[top1--];stack2[++top2] = temp;if (temp->lc != NULL)stack1[++top1] = temp->lc;if (temp->rc != NULL)stack1[++top1] = temp->rc;}while (top2 != -1)std::cout << stack2[top2--]->data << ' ';} } void level(btNode* p) {int front, rear;front = rear = 0;btNode* que[10];if (p != NULL){rear = (rear + 1) % 10;que[rear] = p;while (rear != front){front = (front + 1) % 10;std::cout << que[front]->data << ' ';if (que[front]->lc != NULL){rear = (rear + 1) % 10;que[rear] = que[front]->lc;}if (que[front]->rc != NULL){rear = (rear + 1) % 10;que[rear] = que[front]->rc;}}} }

輸出結(jié)果為：

總結(jié)

以上是生活随笔為你收集整理的二叉树的非递归遍历（c/c++）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。