本文共 2191 字，大约阅读时间需要 7 分钟。
2017-07-09 20:42:55
遍历二叉树的主流方法有三种，分别是前序遍历，中序遍历，后序遍历。
通常使用递归的算法进行遍历，这种遍历的代码编写简单，容易实现。不过，函数递归使用的函数栈，所以，一般这样的问题都可以用自定义的栈来替代递归函数。
1、前序遍历
前序遍历是指中间节点优先于左右两个子节点输出，所以使用递归的算法为：
void preorder(Bintree* root){ if (root==NULL) return ; else { cout<<(char)root->data<<" "; preorder(root->left); preorder(root->right); }} 如果使用非递归方法，则需要申请一个栈来保存数据。
首先，先将中间节点压入栈中，后将右节点和左节点压入栈中。这一步是保证左节点先于右节点输出。
每次弹出栈的顶部数据，将该数据输出，同时将该节点的右节点和左节点压入栈中。
循环处理，直到栈为空。
void preorder2(Bintree* root){ stack s; if(root) s.push(root); while(!s.empty()) { Bintree* cur=s.top(); s.pop(); if(cur->right) s.push(cur->right); if(cur->left) s.push(cur->left); cout<<(char)cur->data<<" "; }} 2、中序遍历
中序遍历是指先将左边的节点输出后再输出自身，最后输出右节点。使用递归的方法来实现的代码如下：
void inorder(Bintree* root){ if(root) { inorder(root->left); cout< data<<" "; inorder(root->right); }} 如果采用非递归的话，则有点麻烦。首先，中序的要求是需要将左边输出完毕后再输出自身，所以需要一直向左寻找，直到左边的节点为空，则输出当前的栈顶元素。
具体算法过程如下：
首先申请一个栈s,将当前的cur设置为root，如果栈非空或者cur非NULL，则一直循环操作。
如果cur非空，将cur压入栈中，同时，cur更新为cur的left值，
如果cur为空，将栈顶元素弹出并输出，将栈顶元素的右值赋值给cur,继续下次的循环。
void inorder2(Bintree* root){ Bintree* cur=root; stack s; while(!s.empty()||cur) { if(cur) { s.push(cur); cur=cur->left; } else { Bintree* temp=s.top(); s.pop(); cur=temp->right; cout< data<<" "; } }} 3、后序遍历
显然，后序遍历的意思就是指，中间的节点在最后输出，用递归可以很形象的表现出来。
void postorder(Bintree* root){ if(root) { postorder(root->left); postorder(root->right); cout< data<<" "; }} 倘若使用非递归，则会有点麻烦。我们可以使用两个栈来完成这项工作。
首先，将root压入s1中，当栈1非空的时候，一直循环。
将栈顶的元素出栈，将其左右节点入栈，同时所有从s1中弹出的元素都将压入s2中。
最后将s2中的元素全部输出即可。
void postorder2(Bintree* root){ stack s1; stack s2; s1.push(root); while(!s1.empty()) { Bintree* cur=s1.top(); s1.pop(); s2.push(cur); if(cur->left) s1.push(cur->left); if(cur->right) s1.push(cur->right); } while(!s2.empty()) { cout< data<<" "; s2.pop(); }}
转载地址：https://www.cnblogs.com/hyserendipity/p/7143195.html 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！
发表评论
最新留言
关于作者
