1、二叉树的遍历

  为什么要有遍历操作：将线性结构-------->非线性结构；

      将递归程序-------->非递归程序；

2、二叉树的三种递归遍历：

  先序遍历：先访问根(父)结点，在访问左分支，最后访问右分支；

  中序遍历：先访问左分支，在根结点，最后右分支；

  后序遍历：先访问左分支，在访问右分支，最后访问根节点；

所有程序皆正确测试过，后面将给完整程序和测试程序，测试结果。

以下就是递归遍历，先序，中序，后序：

下面的都是在类外定义的函数，所以为模板函数：

//先序遍历template
     
      void BinTree
      
       ::prevOrder(BinTreeNode
       
         *t)const{    if(t == NULL){        return;    }else{        cout<
        
         data<<" ";        prevOrder(t->leftChild);        prevOrder(t->rightChild);    }}//中序遍历template
         
          void BinTree
          
           ::inOrder(BinTreeNode
           
             *t)const{    if(t == NULL){        return;    }else{        inOrder(t->leftChild);        cout<
            
             data<<" ";        inOrder(t->rightChild);    }}//后序遍历template
             
              void BinTree
              
               ::endOrder(BinTreeNode
               
                 *t)const{    if(t == NULL){        return;    }else{        endOrder(t->leftChild);        endOrder(t->rightChild);        cout<
                
                 data<<" ";    }}
                
               
              
             
            
           
          
         
        
       
      
     

3、二叉树的4种非递归遍历

  (1)、深度优先用栈

  先序的非递归遍历：栈先入后出，根结点入栈，栈不空，出栈访问，此时将右孩子入栈，在将左孩子入栈，栈不空，出栈访问，就是循环了；

  代码如下：

template
     
      void BinTree
      
       ::prevOrder_1(BinTreeNode
       
        * t)const{    stack
        
         
           *> st;  //栈里面放的是指向节点的指针    BinTreeNode
          
            *tmp;    if(t != NULL){   //根不为空        st.push(t);  //根入栈        while(!st.empty()){  //栈非空            tmp = st.top();  //读栈顶元素            st.pop();        //出栈            cout<
           
            data<<" ";  //访问            if(tmp->rightChild){    //右孩子存在                st.push(tmp->rightChild);  //入栈            }            if(tmp->leftChild){     //左孩子存在                st.push(tmp->leftChild);  //入栈            }        }    }}
           
          
         
        
       
      
     

  中序的非递归遍历：就是先把根及左分支一直压栈，栈不空，出栈访问，再看右孩子，有的话，压栈，结束条件想清楚就行。

  代码如下：

template
     
      void BinTree
      
       ::inOrder_1(BinTreeNode
       
        * t)const{    stack
        
         
           *> st;  //栈里面放的是指向节点的指针    BinTreeNode
          
            *p = t;                     //用的是do while()循环    do{        while(p != NULL){  //将根和左子树一直入栈            st.push(p);            p = p->leftChild;        }        if(!st.empty()){  //栈不空，            p = st.top();  //读栈顶元素            st.pop();      //出栈            cout<
           
            data<<" ";  //访问            p = p->rightChild;   //此时往刚才栈顶元素的右孩子走；        }             //中序遍历时，当root出栈时，此时栈空，没有p!=NULL的话，将出错。    }while(p != NULL || !st.empty()); //为根的时候右边还要入栈。}
           
          
         
        
       
      
     

  后序的非递归遍历：思想就是要有一个标志，当为右边回来的时候才能访问根节点！！！

  代码如下：

typedef enum{L, R}Tag;   //枚举定义新的类型template
     
        //定义一个类，为的是做标志class stkNode{public:    stkNode(BinTreeNode
      
        *p = NULL) : ptr(p), tag(L){}public:                  //数据成员为公有，便于访问    BinTreeNode
       
         *ptr;      Tag                   tag; //L R};template
        
         void BinTree
         
          ::endOrder_1(BinTreeNode
          
           * t)const{    stkNode
           
             n;    stack
            
             
              > st;  //此时栈中存放的是对象！    BinTreeNode
              
                *p = t;        do{        while(p != NULL){  //不为空，一路向左入栈            n.ptr = p;    //将指针给过去            n.tar = L;    //记为左边入栈            st.push(n);            p = p->leftChild;        }        bool isRun = true;  //是否继续的标志        while(isRun && !st.empty()){              n = st.top();  //读栈顶            st.pop();     //出栈            switch(n.tag){  //根据L和R选择            case L:                p = n.ptr;                 n.tag = R;  //更改为R                st.push(n);  //压入栈                p = p->rightChild;  //看有没有右孩子，有的话，结束循环，要入栈的；                isRun = false;  //特别重要，保证了右孩子的入栈！                break;            case R:                cout<
               
                data<<" ";                break;            }        }    }while(!st.empty());//不用p1=NULL,因为当栈空时，最后一个节点刚好被访问完成。}
               
              
             
            
           
          
         
        
       
      
     

画图跟踪后序如下：

  (2)、广度优先用队列

  层次遍历：根结点入队列，队列非空，出队访问，在将左右孩子入队，非空，访问，构成循环；

  代码如下：

template
     
      void BinTree
      
       ::levelOrder(BinTreeNode
       
        * t)const{    queue
        
         
           *> qu;  //队列里面放的是指向节点的指针    BinTreeNode
          
            *p;    if(t != NULL){ //根非空        qu.push(t);  //根入队        while(!qu.empty()){  //队列非空            p = qu.front();  //读队首            qu.pop();        //出队            cout<
           
            data<<" "; //访问            if(p->leftChild){  //左孩子存在                qu.push(p->leftChild); //入队            }            if(p->rightChild){   //右孩子存在                qu.push(p->rightChild);  //入队            }        }    }}