Problem：

　　实现二叉树的先序、中序、后序遍历，包括递归方式和非递归方式

Solution：

　　切记递归规则：

　　先遍历根节点，然后是左孩子，右孩子，

　　根据不同的打印位置来确定中序、前序、后续遍历。

 

Code:

　　

1 #pragma once  2 #include 
     
        3 #include 
      
         4 #include 
       
          5 #include 
        
           6 #include 
         
            7 #include 
          
            8 9 10 using namespace std; 11 12 13 struct Node 14 { 15 int val; 16 Node* lchild; 17 Node* rchild; 18 Node(int a = -1) :val(a), lchild(NULL), rchild(NULL) {} 19 }; 20 21 void Create1(Node*& root, vector
           
            num, int i)//前序构造树 22 { 23 if (num[i] < 0) 24 root = NULL; 25 else if (i < num.size()) 26 { 27 root = new Node(num[i]); 28 Create1(root->lchild, num, i + 1); 29 Create1(root->rchild, num, i + 1); 30 } 31 } 32 33 void Create2(Node*& root, vector
            
             num)//层序构造树 34 { 35 queue
             
              q; 36 root = new Node(num[0]); 37 q.push(root); 38 int i = 1; 39 while (i < num.size() && !q.empty()) 40 { 41 Node* p = q.front(); 42 q.pop(); 43 if (!p)//空节点p 44 break; 45 if(num[i]>0) 46 p->lchild = new Node (num[i++]); 47 if(num[i]>0) 48 p->rchild = new Node (num[i++]); 49 q.push(p->lchild); 50 q.push(p->rchild); 51 } 52 } 53 54 void PreTravel(Node* root)//前序遍历 55 { 56 if (!root) 57 return; 58 cout << root->val << " "; 59 PreTravel(root->lchild); 60 PreTravel(root->rchild); 61 } 62 63 void NotPreTravel(Node* root)//非递归前序遍历 64 { 65 stack
              
               s; 66 if (root) 67 { 68 s.push(root); 69 while (!s.empty()) 70 { 71 root = s.top(); 72 cout << root->val << " "; 73 s.pop(); 74 if (root->rchild) 75 s.push(root->rchild); 76 if (root->lchild) 77 s.push(root->lchild); 78 } 79 } 80 } 81 82 void MidTravel(Node* root)//中序遍历 83 { 84 if (!root) 85 return; 86 87 MidTravel(root->lchild); 88 cout << root->val << " "; 89 MidTravel(root->rchild); 90 } 91 92 void NotMidTravel(Node* root)//非递归中序遍历 93 { 94 stack
               
                s; 95 if (root) 96 { 97 while (!s.empty() || root) 98 { 99 if (root)100 {101 s.push(root);102 root = root->lchild;103 }104 else105 {106 root = s.top();107 s.pop();108 cout << root->val << " ";109 root = root->rchild;110 }111 }112 }113 }114 115 116 117 void LastTravel(Node* root)//后序遍历118 {119 if (!root)120 return; 121 LastTravel(root->lchild);122 LastTravel(root->rchild);123 cout << root->val << " ";124 }125 126 void NotLastTravel(Node* root)//非递归后序遍历127 {128 stack
                
                 s1;129 stack
                 
                  s2;130 if (root)131 {132 s1.push(root);133 while (!s1.empty())134 {135 root = s1.top();136 s1.pop();137 s2.push(root);138 if (root->lchild) 139 s1.push(root->lchild);140 if(root->rchild)141 s1.push(root->rchild);142 }143 while (!s2.empty())144 {145 root = s2.top();146 s2.pop();147 cout << root->val << " ";148 }149 }150 }151 152 void NotLastTravel2(Node* root)//非递归后序遍历,使用一个栈153 {154 stack
                  
                   s;155 if (root)156 {157 s.push(root);158 Node* p;159 while (!s.empty())160 {161 p = s.top();162 if (p->lchild && root != p->lchild && root != p->rchild)163 s.push(p->lchild);164 else if (p->rchild && root != p->rchild )165 s.push(p->rchild);166 else167 {168 cout << p->val << " ";169 s.pop();170 root = p;171 }172 }173 174 }175 }176 177 178 179 180 string getSpace(int num)181 {182 string space = " ";183 for (int i = 0; i < num; ++i)184 space.append(" ");185 return space;186 }187 188 void PrintShape(Node* root, int h, string c, int len)189 {190 if (root)191 {192 PrintShape(root->rchild, h + 1, "v", len);193 string val;194 stringstream ss;195 ss << root->val;196 ss >> val;197 val = c + val + c;198 int lenM = val.length();199 int lenL = (len - lenM) / 2;200 int lenR = len - lenM - lenL;201 val = getSpace(lenL) + val + getSpace(lenR);202 cout << getSpace(h*len) + val << endl;203 PrintShape(root->lchild, h + 1, "^", len);204 }205 206 }207 208 //直观地打印一颗树，即打印一横向的树，每个节点的左上角节点为其父节点209 void PrintTree(Node* root)210 {211 cout << "The shape of tree is: " << endl;212 cout << "===============================================" << endl;213 PrintShape(root, 0, "H", 17);214 cout << "===============================================" << endl;215 }216 217 218 219 void Test()220 {221 //我们使用多种方法来构造一颗树：222 // 1223 // 2 3224 // 4 5 6 7225 // 8 9 10 11 12 N N NULL226 // 使用层序遍历来打印树227 228 Node* root1 = NULL;229 vector
                   
                    num1 = { 1,2,4,8,9,5,10,11,3,6,12,-1,7,-1,-1 };230 Create1(root1, num1, 0);//前序构造树231 232 Node* root2 = NULL;233 vector
                    
                     num2 = { 1,2,3,4,5,6,7,8,9,10,11,12,-1,-1,-1};234 Create2(root2, num2);//层序构造树235 236 237 cout << endl << "==============前序遍历============" << endl;238 PreTravel(root2);//前序遍历239 240 cout << endl << "===============中序遍历=============" << endl;241 MidTravel(root2);//中序遍历242 243 cout << endl << "===============后序遍历============" << endl;244 LastTravel(root2);//后序遍历245 246 cout << endl << "===============非递归前序遍历============" << endl;247 NotPreTravel(root2);//非递归前序遍历248 249 cout << endl << "===============非递归中序遍历============" << endl;250 NotMidTravel(root2);//非递归中序遍历251 252 cout << endl << "===============非递归后序遍历============" << endl;253 NotLastTravel2(root2);//非递归后序遍历254 255 cout << endl << "===============打印树============" << endl;256 PrintTree(root2);257 258 int a = 1;259 260 261 262 }