二叉树的非递归遍历（c/c++）

由于递归算法相对于非递归算法来说效率通常都会更低，递归算法会有更多的资源需要压栈和出栈操作（不仅仅是参数，还有函数地址等）由于编译器对附加的一些栈保护机制会导致递归执行的更加低效，使用循环代替递归算法，通常可以获得更好的执行效率和空间效率，在二叉树层次较深的情况下，采用非递归方式遍历能够有效的提升遍历的性能。

二叉树的非递归遍历分为三种：先序非递归遍历，中序非递归遍历和后续非递归遍历。这和递归遍历的结果是一样的，区别只是在于采用了循环结构。

先序非递归遍历

采用辅助数据结构栈来实现，先序遍历是按照先根，后左子树，再右子树的顺序进行递归访问的。由于栈是先入后出的，所以入栈顺序为先右孩子后左孩子。
非递归的算法是先将根结点入栈，栈不为空时：根结点出栈并访问，然后将右孩子入栈，再将左孩子入栈；左孩子出栈并访问，它的孩子也是按照先右后左顺序分别入栈，如此往复直至栈为空结束。代码如下：

void preorderNoRecursion(btNode* p) {if (p != NULL){int top = -1;btNode* stack[50];//建立大小为50个结点的栈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才退出{while (temp!=NULL)//先将左分支入栈。{stack[++top] = temp;temp = temp->lc;}if (top!=-1)//出栈时temp指向出栈结点的右孩子，进行下一轮循环{temp = stack[top--];std::cout << temp->data << ' ';temp = temp->rc;}}}

中序非递归遍历根结点先不入栈，循环判定条件有两个。

后序非递归遍历

这里列出一种比较好理解的后续非递归遍历，它的思路可以看下面的例子

对上图中的A，B，C三个结点来讲：
先序遍历为：A，B，C
后序遍历为：B，C，A
二者之间的联系在于，如果将先序遍历顺序的根-左-右改为根-右-左，即交换访问次序，遍历结果为A，C，B，然后将其结果逆序，得B，C，A。这刚好是后序遍历的结果。

对上图中的所有结点来讲：
先序遍历为：A，B，D，E，C，F
交换次序后的结果为：A，C，F，B，E，D
再逆序：D，E，B，F，C，A
而后序遍历的结果也为：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)//修改先序非递归遍历进行交换{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 << ' ';//访问栈2中的数据} }

完整示例

关于二叉树非递归遍历的完整代码如下：

#include<iostream> typedef struct btNode {char data;//结点中的信息struct btNode* lc;//左孩子结点struct btNode* rc;//右孩子结点 }btNode;btNode* initial(char* ele, int num);//用数组初始化一棵树 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)//将所有结点的左右子树置为空{temp[i].lc = NULL;temp[i].rc = NULL;++i;}i = 0;while (i < num/2)//通过完全二叉树的顺序存储来创建树的结构{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++)//对树中的每个结点赋值temp[i].data = ele[i];return temp; } void preorderNoRecursion(btNode* p) {if (p != NULL){int top = -1;btNode* stack[50];//建立大小为50个结点的栈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指向出栈结点的右孩子，进行下一轮循环{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按照后续递归的顺序进行访问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;}}} }

输出结果为：

总结

以上是生活随笔为你收集整理的二叉树的非递归遍历（c/c++）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。