二叉樹的前序，中序，後序，層序周遊（遞歸，非遞歸雙版本）

二叉樹結點的表示：

采用連結清單的存儲方式，設有資料域和左右孩子指針

代碼實作：

typedef struct BiNode{
  ElemType data;
  struct BiNode *lchild,*rchild;    //左孩子，右孩子
}BiNode,*BiTree;
           

 二叉樹的建立：

前序周遊輸入結點

代碼實作：

//建立二叉樹
void CreateTree(BiTree &T){
  ElemType c;
  scanf("%c",&c);
  if(c=='#'){
    T=NULL;
    return;
  }
  else{
    T=(BiTree)malloc(sizeof(BiNode));    //開辟動态空間
    T->data=c;
    CreateTree(T->lchild);
    CreateTree(T->rchild);
  }
}
           

 前序周遊：

先輸出根結點，依次周遊左子樹和右子樹

遞歸版本容易了解，在非遞歸版本中借用棧的特性來實作，思路是從根結點開始有左孩子就讓左孩子進棧，之後跳出循環

如果棧不空輸出棧頂元素，緊接着目前節點指向其右孩子，在傳回循環讓所有左孩子進棧

代碼實作：

//先根遞歸周遊
void PreOrder(BiTree T){
  if(T){
    printf("%c ",T->data);
    PreOrder(T->lchild);
    PreOrder(T->rchild);
  }
}
//先根非遞歸周遊
void FPreOrder(BiTree T){
  stack<BiTree> s;
  BiTree cur=T;
  while(cur||!s.empty()){      //樹不空或棧不空
    while(cur){                //從根節點一直往下周遊目前結點的左孩子，沒有時跳出
      cout<<cur->data<<" ";    //輸出根節點
      s.push(cur);             //同時入棧
      cur=cur->lchild;         //指向目前結點的左孩子
    }
    if(!s.empty()){            
      cur=s.top();             //目前結點指向棧頂元素
      s.pop();                 //出棧
      cur=cur->rchild;         //尋找其右孩子
    }
  }
}
           

 中序周遊：

先遍左子樹，再根結點，最後右子樹

在非遞歸版本中思想同先序周遊的相同，隻是注意結點資料的輸出位置不同，其他的都一樣

代碼實作：

void InOrder(BiTree T){
  if(T){
    InOrder(T->lchild);
    printf("%c ",T->data);
    InOrder(T->rchild);
  }
}
void FInOrder(BiTree T){
  stack<BiTree> s;
  BiTree cur=T;
  while(cur||!s.empty()){    
    while(cur){              //從根節點一直往下周遊目前節點的左孩子，沒有時跳出  
      s.push(cur);             
      cur=cur->lchild;     
    }
    if(!s.empty()){          
      cur=s.top();
      cout<<cur->data<<" ";  
      s.pop();
      cur=cur->rchild;
    }
  }
}
           

 後序周遊：

先左子樹，再右子樹，最後根節點

在非遞歸版本中，剛開始從根節點開始有左孩子就讓左孩子進棧，否則右孩子進棧，然後令目前結點指向棧頂元素，輸出對應的資料後出棧，若目前結點是此時棧頂元素的左孩子，則讓目前結點指向其右孩子，實作左右中的周遊順序，若不是，證明目前結點是此時棧頂元素的右孩子，使目前節點為NULL，在下一次循環中直接輸出雙親的資料

代碼實作：

void PostOrder(BiTree T){
  if(T){
    PostOrder(T->lchild);
    PostOrder(T->rchild);
    printf("%c ",T->data);
  }
}
void FPostOrder(BiTree T){
  stack<BiTree> s;
  BiTree cur=T;
  while(cur||!s.empty()){
    while(cur){
      s.push(cur);
      cur=cur->lchild?cur->lchild:cur->rchild;  //左孩子先進，右孩子後進
    }
    cur=s.top();
    cout<<cur->data<<" ";
    s.pop();
    if(!s.empty()&&cur==(s.top())->lchild)      
      cur=(s.top())->rchild;
    else
      cur=NULL;
  }
}
           

 層序周遊：

即從上到下，從左到右依次輸出元素值

很明顯将二叉樹中的元素按照對應順序放入隊列，然後輸出隊列裡的值就行

代碼實作：

void SeqOrder(BiTree T){
  queue<BiTree> q;
  if(T){
    q.push(T);    //根節點入隊
  }
  while(!q.empty()){
    cout<<q.front()->data<<" ";    //輸出隊頭元素
    if(q.front()->lchild){     
      q.push(q.front()->lchild);   //左孩子入隊
    }
    if(q.front()->rchild){
      q.push(q.front()->rchild);   //右孩子入隊
    }
    q.pop();                       //輸出過的元素對應結點出隊
  }
}
           

 完整代碼：

#include<iostream>
#include<cstdio>
#include<queue>
#include<stack>
#include<cstdlib>
using namespace std;
typedef char ElemType;    //自定義結點資料類型
//建立二叉連結清單
typedef struct BiNode{
  ElemType data;
  struct BiNode *lchild,*rchild;    //左孩子，右孩子
}BiNode,*BiTree;
//建立二叉樹
void CreateTree(BiTree &T){
  ElemType c;
  scanf("%c",&c);
  if(c=='#'){
    T=NULL;
    return;
  }
  else{
    T=(BiTree)malloc(sizeof(BiNode));    //開辟動态空間
    T->data=c;
    CreateTree(T->lchild);
    CreateTree(T->rchild);
  }
}
//先根遞歸周遊
void PreOrder(BiTree T){
  if(T){
    printf("%c ",T->data);
    PreOrder(T->lchild);
    PreOrder(T->rchild);
  }
}
//先根非遞歸周遊
void FPreOrder(BiTree T){
  stack<BiTree> s;
  BiTree cur=T;
  while(cur||!s.empty()){      //樹不空或棧不空
    while(cur){                //從根節點一直往下周遊目前結點的左孩子，沒有時跳出
      cout<<cur->data<<" ";    //輸出根節點
      s.push(cur);             //同時入棧
      cur=cur->lchild;         //指向目前結點的左孩子
    }
    if(!s.empty()){            
      cur=s.top();             //目前結點指向棧頂元素
      s.pop();                 //出棧
      cur=cur->rchild;         //尋找其右孩子
    }
  }
}
void InOrder(BiTree T){
  if(T){
    InOrder(T->lchild);
    printf("%c ",T->data);
    InOrder(T->rchild);
  }
}
void FInOrder(BiTree T){
  stack<BiTree> s;
  BiTree cur=T;
  while(cur||!s.empty()){    
    while(cur){              //從根節點一直往下周遊目前節點的左孩子，沒有時跳出  
      s.push(cur);             
      cur=cur->lchild;     
    }
    if(!s.empty()){          
      cur=s.top();
      cout<<cur->data<<" ";  
      s.pop();
      cur=cur->rchild;
    }
  }
}
void PostOrder(BiTree T){
  if(T){
    PostOrder(T->lchild);
    PostOrder(T->rchild);
    printf("%c ",T->data);
  }
}
void FPostOrder(BiTree T){
  stack<BiTree> s;
  BiTree cur=T;
  while(cur||!s.empty()){
    while(cur){
      s.push(cur);
      cur=cur->lchild?cur->lchild:cur->rchild;  //左孩子先進，右孩子後進
    }
    cur=s.top();
    cout<<cur->data<<" ";
    s.pop();
    if(!s.empty()&&cur==(s.top())->lchild)      
      cur=(s.top())->rchild;
    else
      cur=NULL;
  }
}
void SeqOrder(BiTree T){
  queue<BiTree> q;
  if(T){
    q.push(T);    //根節點入隊
  }
  while(!q.empty()){
    cout<<q.front()->data<<" ";    //輸出隊頭元素
    if(q.front()->lchild){     
      q.push(q.front()->lchild);   //左孩子入隊
    }
    if(q.front()->rchild){
      q.push(q.front()->rchild);   //右孩子入隊
    }
    q.pop();                       //輸出過的元素對應結點出隊
  }
}
int main(){
  BiTree T=NULL;
  //printf("前序周遊輸入結點:\n");
  CreateTree(T);
  //printf("前序周遊:\n");
  PreOrder(T);
  cout<<endl;
  FPreOrder(T);
  cout<<endl;
  //printf("中序周遊:\n");
  InOrder(T);
  cout<<endl;
  FInOrder(T);
  cout<<endl;
  //printf("後序周遊:\n");
  PostOrder(T);
  cout<<endl;
  FPostOrder(T);
  cout<<endl;
  //printf("層序周遊:\n");
  SeqOrder(T);
  cout<<endl;
  return 0;
}
           

運作結果示例：