二叉树前序、中序、后序、层次遍历-白红宇

二叉树前序、中序、后序、层次遍历

阅读量：6573 次

发布时间：2019-06-24

本文共 7003 字，大约阅读时间需要 23 分钟。

 转自：http://blog.csdn.net/that163/article/details/8040009
 分别用了三种不同的方法实现了二叉树的前序遍历。

 1 #include
      
        2  #include
       
         3  using namespace std; 4  struct BTreeNode{ 5      //二叉树 6      int data; 7      BTreeNode *lchild; 8      BTreeNode *rchild; 9      BTreeNode *parent;10  };11  /*12  void PreOrder(BTreeNode *t){13      //递归方法14      if(t == NULL)return ;15      cout<
        
         data<<' ';16      PreOrder(t->lchild);17      PreOrder(t->rchild);18  }19  */20  /*21  void PreOrder(BTreeNode *t){22      //用栈，采取先放右子树再放左子树的方法，达到输出时先左后右23      stack
         
           s;24      BTreeNode *temp;25      if(t == NULL)return ;26      s.push(t);27      while(!s.empty()){28          temp = s.top();29          s.pop();30          cout<
          
           data<<' ';31          if(temp->rchild != NULL)s.push(temp->rchild);32          if(temp->lchild != NULL)s.push(temp->lchild);33      }34  }35  */36  void PreOrder(BTreeNode *t){37      //不断往左走并访问，直到无法走后，回溯到先一个结点的右边，再重复38      stack
           
             s;39 BTreeNode *temp;40 while(t != NULL || !s.empty()){41 while(t != NULL){42 cout<
            
             data<<" ";43 s.push(t);44 t = t->lchild;45 }46 if(!s.empty()){47 t = s.top();48 s.pop();49 t = t->rchild;50 }51 }52 }53 int main(){54 return 0;55 }56 View Code

分别用了三种不同的方法实现了二叉树的中序遍历。

1 /*  2 input:  3 2  4 10 5 4 -1 -1 -1 20 19 -1 -1 40 -1 -1  5 30 10 8 20 -1 -1 -1 -1 50 40 -1 45 -1 -1 -1  6 output:  7 4 5 10 19 20 40  8 20 8 10 30 40 45 50  9 */ 10 #include
     
       11 #include
      
        12 using namespace std; 13 struct BTreeNode{ 14     //二叉树 15     int data; 16     BTreeNode *lchild; 17     BTreeNode *rchild; 18 }; 19 struct snode{ 20     //设置访问标识 21     BTreeNode *node; 22     bool flag; 23 }; 24 /* 25 void InOrder(BTreeNode *t){ 26     //递归方法 27     if(t == NULL)return ; 28     InOrder(t->lchild); 29     cout<
       
        data<<' '; 30     InOrder(t->rchild); 31 } 32 */ 33 /* 34 void InOrder(BTreeNode *t){ 35     //不断访问其左子树，然后输出其根，然后访问其接着的右子树，重复过程 36     stack
        
          s; 37     while(!s.empty() || t != NULL){ 38         while(t != NULL){ 39             s.push(t); 40             t = t->lchild; 41         } 42         if(!s.empty()){ 43             t = s.top(); 44             s.pop(); 45             cout<
         
          data<<' '; 46             t = t->rchild; 47         } 48     } 49 } 50 */ 51 void InOrder(BTreeNode *t){ 52     //按右根左的存放方式存入栈，根据栈的特性输出中序遍历。注意第一次放入的是根，第二次放入才调整其位置。 53     stack
          
            s; 54 snode temp,ltemp,rtemp; 55 temp.flag = false; 56 temp.node = t; 57 s.push(temp); 58 while(!s.empty()){ 59 temp = s.top(); 60 s.pop(); 61 if(temp.flag)cout<
           
            data<<' '; 62 else{ 63 if(temp.node->rchild != NULL){ 64 rtemp.flag = false; 65 rtemp.node = temp.node->rchild; 66 s.push(rtemp); 67 } 68 temp.flag = true; 69 s.push(temp); 70 if(temp.node->lchild != NULL){ 71 ltemp.flag = false; 72 ltemp.node = temp.node->lchild; 73 s.push(ltemp); 74 } 75 } 76 } 77 } 78 void Create(BTreeNode *&t){ 79 //（测试用）以先序遍历构建二叉树 80 int x; 81 cin>>x; 82 if(x == -1) 83 t = NULL; 84 else 85 { 86 t = new BTreeNode; 87 t->data = x; 88 Create(t->lchild); 89 Create(t->rchild); 90 } 91 } 92 int main(){ 93 BTreeNode *root = NULL; 94 int t; 95 cin>>t; 96 while(t--) 97 { 98 Create(root); 99 InOrder(root);100 cout<

分别用了三种不同的方法实现了二叉树的后序遍历。

1 /*  2 input:  3 2  4 10 5 4 -1 -1 -1 20 19 -1 -1 40 -1 -1  5 30 10 8 20 -1 -1 -1 -1 50 40 -1 45 -1 -1 -1  6 output:  7 4 5 19 40 20 10  8 20 8 10 45 40 50 30  9 */ 10 #include
     
       11 #include
      
        12 using namespace std; 13 struct BTreeNode{ 14     //二叉树 15     int data; 16     BTreeNode *lchild; 17     BTreeNode *rchild; 18     BTreeNode *parent; 19 }; 20 struct snode{ 21     //设置访问标识 22     BTreeNode *node; 23     bool flag; 24 }; 25 /* 26 void PostOrder(BTreeNode *t){ 27     //递归方法 28     if(t == NULL)return ; 29     PostOrder(t->lchild); 30     PostOrder(t->rchild); 31     cout<
       
        data<<' '; 32 } 33 */ 34 /* 35 void PostOrder(BTreeNode *t){ 36     //设置访问标识，第一次为访问完左子树，第二次为访问完右子树。二次访问即刻输出结点。 37     stack
        
          s; 38     snode temp; 39     while(!s.empty() || t != NULL){ 40         while(t != NULL){ 41             temp.node = t; 42             temp.flag = false; 43             s.push(temp); 44             t = t->lchild; 45         } 46         if(!s.empty()){ 47             temp = s.top(); 48             s.pop(); 49             t = temp.node; 50             if(temp.flag){ 51                 cout<
         
          data<<' '; 52                 t = NULL; 53             } 54             else{ 55                 temp.flag = true; 56                 s.push(temp); 57                 t = t->rchild; 58             } 59         } 60     } 61 } 62 */ 63 void PostOrder(BTreeNode *t){ 64     //采取根右左的存放方式，用栈实现后序遍历。设置访问标识，注意第一次放入栈，放入的是根，第二次调整其顺序。 65     stack
          
            s; 66 snode temp,ltemp,rtemp; 67 temp.node = t; 68 temp.flag = false; 69 s.push(temp); 70 while(!s.empty()){ 71 temp = s.top(); 72 s.pop(); 73 if(temp.flag)cout<
           
            data<<' '; 74 else{ 75 temp.flag = true; 76 s.push(temp); 77 if(temp.node->rchild != NULL){ 78 rtemp.flag = false; 79 rtemp.node = temp.node->rchild; 80 s.push(rtemp); 81 } 82 if(temp.node->lchild != NULL){ 83 ltemp.flag = false; 84 ltemp.node = temp.node->lchild; 85 s.push(ltemp); 86 } 87 88 } 89 } 90 } 91 void Create(BTreeNode *&t){ 92 //（测试用）以先序遍历构建二叉树 93 int x; 94 cin>>x; 95 if(x == -1) 96 t = NULL; 97 else 98 { 99 t = new BTreeNode;100 t->data = x;101 Create(t->lchild);102 Create(t->rchild);103 }104 }105 int main(){106 BTreeNode *root = NULL;107 int t;108 cin>>t;109 while(t--)110 {111 Create(root);112 PostOrder(root);113 cout<

1 /* 2 二叉树的层次遍历 3 input: 4 2 5 10 5 4 -1 -1 -1 20 19 -1 -1 40 -1 -1 6 30 10 8 20 -1 -1 -1 -1 50 40 -1 45 -1 -1 -1 7 output: 8 10 5 20 4 19 40 9 30 10 50 8 40 20 4510 */11 #include
     
      12 #include
      
       13 using namespace std;14 struct BTreeNode{15     //二叉树16     int data;17     BTreeNode *lchild;18     BTreeNode *rchild;19 };20 void LayerOrder(BTreeNode *t){21     //利用队列实现层次遍历，每次访问根结点，然后一次放入左结点和右结点（如果有的话）。22     if(t == NULL)return ;23     queue
       
         q;24     BTreeNode *temp;25     q.push(t);26     while(!q.empty()){27         temp = q.front();28         q.pop();29         cout<
        
         data<<' ';30         if(temp->lchild != NULL)q.push(temp->lchild);31         if(temp->rchild != NULL)q.push(temp->rchild);32     }33 }34 void Create(BTreeNode *&t){35     //（测试用）以先序遍历构建二叉树36     int x;37     cin>>x;38     if(x == -1)39         t = NULL;40     else41     {42         t = new BTreeNode;43         t->data = x;44         Create(t->lchild);45         Create(t->rchild);46     }47 }48 int main(){49     BTreeNode *root = NULL;50     int t;51     cin>>t;52     while(t--)53     {54         Create(root);55         LayerOrder(root);56         cout<