1 #include <iostream>  2 #include <stack>  3 using namespace std;  4   5 struct TreeNode {  6     int val;  7     TreeNode *left;  8     TreeNode *right;  9     TreeNode(int x): val(x), left(NULL), right(NULL) {} 10 }; 11 // 先序遍历 12 void preOrder(TreeNode *root) { 13     if (!root) { 14         return; 15     } 16  17     cout << root->val << ‘ ‘;     18     preOrder(root->left); 19     preOrder(root->right); 20     return; 21 } 22  23 void preOrder2(TreeNode *root) { 24     if (!root) { 25         return; 26     } 27  28     stack<TreeNode *> s; 29     s.push(root); 30     while(!s.empty()) { 31         TreeNode *p = s.top(); s.pop(); 32         cout << p->val << ‘ ‘; 33  34         if (p->right) { 35             s.push(p->right); 36         } 37         if (p->left) { 38             s.push(p->left); 39         } 40     } 41     return; 42 } 43 //中序遍历 44 void inOrder(TreeNode *root) { 45     if (!root) { 46         return; 47     } 48  49     inOrder(root->left); 50     cout << root->val << ‘ ‘; 51     inOrder(root->right); 52     return; 53 } 54  55 void inOrder2(TreeNode *root) { 56     if (!root) { 57         return; 58     } 59     int UNUSED = 0; 60     int USED = 1; 61     int isUsed; 62  63     TreeNode *p; 64     stack<pair<TreeNode *, int> > s;         65     s.push(make_pair(root, UNUSED)); 66     while (!s.empty()) { 67         p = s.top().first; 68         isUsed = s.top().second;     69         s.pop();     70  71         if (!isUsed) { 72             if (p->right) { 73                 s.push(make_pair(p->right, UNUSED)); 74             }             75             s.push(make_pair(p, USED)); 76             if (p->left) { 77                 s.push(make_pair(p->left, UNUSED)); 78             } 79         } else { 80             cout << p->val << ‘ ‘; 81         } 82     }  83     return; 84 } 85 //后充遍历 86 void postOrder(TreeNode *root) { 87     if (!root) { 88         return; 89     } 90  91     postOrder(root->left); 92     postOrder(root->right); 93     cout << root->val << ‘ ‘; 94     return; 95 } 96  97 void postOrder2(TreeNode *root) { 98     if (!root) { 99         return;100     }101 102     int UNUSED = 0;103     int USED = 1;104     int isUsed;105 106     stack<pair<TreeNode *, int> > s;107     TreeNode *p;108 109     s.push(make_pair(root, UNUSED));110     while (!s.empty()) {111         p = s.top().first;112         isUsed = s.top().second;113         s.pop();114         if (!isUsed) {115             s.push(make_pair(p, USED));116             if (p->right) {117                 s.push(make_pair(p->right, UNUSED));118             }119             if (p->left) {120                 s.push(make_pair(p->left, UNUSED));121             }122         } else {123             cout << p->val << ‘ ‘;124         }125     }126     return;127 }128 129 int main(int argc, char *argv[]) {130     TreeNode *p = new TreeNode(8);131     p->left = new TreeNode(9);132     p->right = new TreeNode(5);133     // 1. preorder traversal134     preOrder(p);135 136     // 2. preorder traversal 137     preOrder2(p);138 139     // 3. inorder traversal140     inOrder(p);141 142     // 4. inorder traversal143     inOrder2(p);144 145     // 5. postorder traversal146     postOrder(p);147 148     // 6. postorder traversal149     postOrder2(p);150     return 0;151 }