前序遍历：根->左->右中序遍历：左->根->右后序遍历：左->右->根假设树节点的定义如下：struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {}};递归版//前序遍历void preorderTraversalRecursion(TreeNode *node){ if(!node) return; cout << node->val << " ";//操作当前节点 preorderTraversalRecursion(node->left); preorderTraversalRecursion(node->right);}//中序遍历void inorderTraversalRecursion(TreeNode *node){ if(!node) return; inorderTraversalRecursion(node->left); cout << node->val << " ";//操作当前节点 inorderTraversalRecursion(node->right);}//后序遍历void postorderTraversalRecursion(TreeNode *node){ if(!node) return; postorderTraversalRecursion(node->left); postorderTraversalRecursion(node->right); cout << node->val << " ";//操作当前节点}迭代版需要使用一个栈作为辅助空间//前序遍历void preorderTraversalIteration(TreeNode *root){ stack<TreeNode*> st; if(root) st.push(root); while(!st.empty()){ TreeNode *nd = st.top(); st.pop(); cout << nd->val << " ";//操作当前节点 if(nd->right) st.push(nd->right); if(nd->left) st.push(nd->left); }}//中序遍历：void inorderTraversalIteration(TreeNode *root){ stack<TreeNode*> st; TreeNode *curr = root; while(curr || !st.empty()){ if(curr){ st.push(curr); curr = curr->left; } else{ curr = st.top(); st.pop(); cout << curr->val << " ";//操作当前节点 curr = curr->right; } }}//后序遍历void postorderTraversalIteration(TreeNode *root){ stack<TreeNode*> st; TreeNode *pre; if(root) st.push(root); while(!st.empty()){ TreeNode *nd = st.top(); /* * 出栈条件： * 对于叶子节点：直接弹出 * 对于非叶子节点：如果已经遍历过其左子节点或右子节点，则弹出 */ if((!nd->left && !nd->right) || (pre && (nd->left == pre || nd->right == pre))){ st.pop(); cout << nd->val <<" ";//操作当前节点 pre = nd; } else{//说明是一个非叶子节点，并且还未访问其左右孩子 if(nd->right) st.push(nd->right); if(nd->left) st.push(nd->left); } }}对于后序遍历，由于其访问序列为：左->右->根。因此还有一种方法，可以按类似前序遍历的方式：根->右->左，然后对得到的结果反序