树-三大遍历

三种遍历都有递归、栈、循环三种方式，其中，递归最为简单，栈次之，循环最为麻烦。递归的深度如果太大则会导致栈溢出；栈的方式需要额外的辅助空间；循环编程最麻烦。
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);
    }
}