三种遍历都有递归、栈、循环三种方式，其中，递归最为简单，栈次之，循环最为麻烦。递归的深度如果太大则会导致栈溢出；栈的方式需要额外的辅助空间；循环编程最麻烦。
1、先序遍历
①递归遍历
T（n）=O（n）
/*先序遍历之递归遍历*/
template <typename T,typename VST>
void travPre_R(BinNodePosi(T) x,VST& visit)
{
if(!x) return;
visit(x->data);
travPre_R(x->lc,visit);
travPre_R(x->rc,visit);
}
②迭代遍历
版本1：利用栈
遇到一个根节点，压入栈中；栈非空时，从栈中取数，如果有右孩子，压入栈中，如果有左孩子，压入栈中。
注意先右后左的顺序
/*先序遍历之迭代遍历*/
/*版本1-利用栈*/
template <typename T, typename VST> //元素类型、操作器
void travPre_I1 ( BinNodePosi(T) x, VST& visit )
{
stack <BinNodePosi(T)> s;
if(x) s.push(x);
while(!s.empty())
{
x=s.pop(); visit(x->data);
if(HasRc(*x)) s.push(x->rc);
if(HasLc(*x)) s.push(x->lc);
}
}
版本2：利用左侧链思想
左侧链子程序：从当前节点出发，沿左分支不断深入，直至没有左分支的节点；沿途节点遇到后立即访问，将右孩子放入栈中；
主程序：左侧链；栈为空时，访问结束；不为空，弹出栈中节点迭代进行该节点的左侧链遍历以及右孩子入栈
/*先序遍历之迭代遍历*/
/*版本2-利用左侧链*/
template <typename T, typename VST> //元素类型、操作器
void VisitAlongLeft( BinNodePosi(T) x, VST& visit,stack <BinNodePosi(T)> &s)
{
while(x)
{
visit(x->data);
s.push(x->rc);
x=x->lc;
}
}
template <typename T, typename VST> //元素类型、操作器
void travPre_I2 ( BinNodePosi(T) x, VST& visit)
{
stack <BinNodePosi(T)> s;
while(true)
{
VisitAlongLeft(x,visit,s);
if(s.empty()) break;
x=s.pop();
}
}
2、中序遍历
①递归遍历
/*中序遍历之递归遍历*/
template <typename T,typename VST>
void travIn_R(BinNodePosi(T) x,VST& visit)
{
if(!x) return;
travIn_R(x->lc,visit);
visit(x->data);
travIn_R(x->rc,visit);
}
②迭代遍历
左侧链：
从当前节点出发，沿左分支不断深入，直至没有左分支的节点；当前节点入栈后随即向左侧分支深入，迭代直到无左孩子（先序遍历是访问并压右孩子入栈）
主程序：左侧链；栈为空时，访问结束；从栈中弹出元素并访问之；转向节点右子树；
/*中序遍历之迭代遍历*/
/*版本0-左侧链思想*/
template <typename T>
static void goAlongVine ( BinNodePosi(T) x, Stack<BinNodePosi(T)>& s )
{
while(x)
{
s.push(x);
x=x->lc;
}
}
template <typename T>
static void TravIn_I ( BinNodePosi(T) x, VST& visit )
{
Stack<BinNodePosi(T)> s;
while(true)
{
goAlongVine(x,s);
if(s.empty()) break;
x=s.pop();
visit(x->data);
x=x->rc;
}
}
3、后序遍历
①递归遍历
/*后序遍历之递归遍历*/
template <typename T,typename VST>
void travPost_R(BinNodePosi(T) x,VST& visit)
{
if(!x) return;
travPost_R(x->lc,visit);
travPost_R(x->rc,visit);
visit(x->data);
}
②迭代遍历
使用栈来实现：从根结点开始，将所有最左结点全部压栈，每当一个结点出栈时，都先扫描该结点的右子树，只有当一个结点的左孩子和右孩子结点均被访问过了，才能访问结点自身。
看不懂。。。。。。
template <typename T> //在以S栈顶节点为根的子树中，找到最高左侧可见叶节点
static void gotoHLVFL ( Stack<BinNodePosi(T)>& S ) { //沿途所遇节点依次入栈
while ( BinNodePosi(T) x = S.top() ) //自顶而下，反复检查当前节点（即栈顶）
if ( HasLChild ( *x ) ) { //尽可能向左
if ( HasRChild ( *x ) ) S.push ( x->rc ); //若有右孩子，优先入栈
S.push ( x->lc ); //然后才转至左孩子
} else //实不得已
S.push ( x->rc ); //才向右,(叶节点无左孩也无右孩，可能将空节点放于栈顶）
S.pop(); //返回之前，弹出栈顶的空节点
}
template <typename T, typename VST>
void travPost_I ( BinNodePosi(T) x, VST& visit ) { //二叉树的后序遍历（迭代版）
Stack<BinNodePosi(T)> S; //辅助栈
if ( x ) S.push ( x ); //根节点入栈
while ( !S.empty() ) {
if ( S.top() != x->parent ) //若栈顶非当前节点之父（则必为其右兄），此时需
gotoHLVFL ( S ); //在以其右兄为根之子树中，找到HLVFL（相当于递归深入其中）
x = S.pop(); visit ( x->data ); //弹出栈顶（即前一节点之后继），并访问之
}
}
另一种思路是：如果当前结点左右子树均为空，则可以访问当前结点，或者左右子树不均为空，但是前一个访问的结点是当前结点的左孩子或者右孩子，则也可以访问当前结点，如果前面两种情况均不满足（即，当前结点的左右孩子不均为空，并且前一个访问的结点不是当前结点左右孩子中的任意一个），则若当前结点的右孩子不为空，将右孩子入栈，若当前结点的左孩子不为空，将左孩子入栈。
该算法的特性：就是当访问某个结点时，栈中所保存的元素正好是这个结点的所有祖先。那么知道了这个特性，我们就很容易解决下面如下问题：
(1).当给定一个叶子结点，要求输出该叶子结点的所有祖先
(2).输出根结点到所有叶子结点的路径
(3).如果二叉树结点的值是数值，那么求每条路径上值之和，也可以利用二叉树后序遍历的非递归算法这个特性
除了以上，还有层次遍历（自上往下，先坐后右遍历）利用队列实现。
template <typename T>
static void T( VST& visit )
{
queue <BinNodePosi(T)> q;
q.enqueue(this);
while(!q.empty())
{
BinNodePosi(T) x= q.dequeue();
visit(x->data);
if(HasLc(*x)) q.enqueue(x->lc);
if(HasRc(*x)) q.enqueue(x->rc);
}
}
网友评论