三种方法中，递归最为简单，栈次之，循环最为麻烦。递归的深度如果太大则会导致栈溢出；栈的方式需要额外的辅助空间；循环编程最麻烦。
首先是递归：
//递归方法void midPrint_r(TreeNode* root){//中序遍历if(root==NULL)return;if(root->left)midPrint_r(root->left);cout<<root->val<<" ";if(root->right)midPrint_r(root->right);}void prePrint_r(TreeNode* root){//前序遍历if(root==NULL)return;cout<<root->val<<" ";if(root->left)prePrint_r(root->left);if(root->right)prePrint_r(root->right);}void postPrint_r(TreeNode* root){//中序遍历if(root==NULL)return;if(root->left)postPrint_r(root->left);if(root->right)postPrint_r(root->right);cout<<root->val<<" ";} 栈方法：先循环把结点压入到栈中，然后再逐个弹出；//循环堆栈方法void midPrint_l(TreeNode* root){stack<TreeNode*> s;TreeNode *cur = root;while(!s.empty() || cur != NULL){while(cur != NULL){s.push(cur);cur = cur->left;}cur = s.top();s.pop();cout<<cur->val<<" ";cur = cur->right;}}void prePrint_l(TreeNode* root){stack<TreeNode*> s;TreeNode *cur = root;while(!s.empty() || cur != NULL){while(cur != NULL){cout<<cur->var<<" ";s.push(cur);cur = cur->left;}cur = s.top();s.pop();cur = cur->right;}}void postPrint_l(TreeNode* root){//the original method/*We use a prev variable to keep track of the previously-traversed node.Let’s assume curr is the current node that’s on top of the stack. Whenprev is curr‘s parent, we are traversing down the tree. In this case,we try to traverse to curr‘s left child if available (ie, push leftchild to the stack). If it is not available, we look at curr‘s rightchild. If both left and right child do not exist (ie, curr is a leaf node),we print curr‘s value and pop it off the stack.If prev is curr‘s leftchild, we are traversing up the tree from the left. We look at curr‘sright child. If it is available, then traverse down the right child (ie,push right child to the stack), otherwise print curr‘s value and pop itoff the stack.If prev is curr‘s right child, we are traversing up the treefrom the right. In this case, we print curr‘s value and pop it off the stack.*/if(root == NULL){return;}stack<TreeNode*> s;s.push(root);TreeNode *cur = NULL;TreeNode *pre = NULL;while(!s.empty()){cur = s.top();//left down or right downif( pre == NULL || pre->left == cur || pre->right == cur){//有左子树压左子树，有右子树压右子树，//都没有说明是叶子结点，直接打印并弹出if(cur->left != NULL){//先压左子树，若左子树为空则压右子树s.push(cur->left);}else if(cur->right != NULL){s.push(cur->right);}else{//左右子树均为空cout<<cur->var<<" ";s.pop();}}//left upelse if(cur->left == pre){//左边开始返回if(cur->right != NULL){//若右孩子不为空则压入，否则，打印s.push(cur->right);}else{cout<<cur->var<<" ";s.pop();}}//right upelse if(cur->right == pre){//从右边返回,说明右侧已经打印完，，则可以直接打印cout<<cur->var<<" ";s.pop();}pre = cur;}// the easy method/*stack<TreeNode*> s;s.push(root);TreeNode *cur = NULL;TreeNode *pre = NULL;while(!s.empty()){cur = s.top();if(pre == NULL || pre->left == cur || pre->right == cur){if(cur->left != NULL){s.push(cur->left);}else if(cur->right != NULL){s.push(cur->right);}}else if(cur->left == pre){if(cur->right != NULL){s.push(cur->right);}}else{cout<<cur->var<<" ";s.pop();}pre = cur;}*/}循环：利用叶子结点左右指针为空的特点，给叶子结点设置其直接后继，输出完该子结点后，再返回其直接后继；//不用辅助空间的方式void midPrint_m(TreeNode *root){TreeNode *cur = root;TreeNode *pre = NULL;while(cur != NULL){if(cur->left == NULL){//左孩子为空，则直接输出cout<<cur->var<<" ";cur = cur->right;}else{pre = cur->left;while( pre->right != NULL && pre->right != cur ){//找到cur的直接前驱pre = pre->right;}if(pre->right == NULL){//设置后继结点pre->right = cur;cur = cur->left;}else{pre->right = NULL;//重新设置为空cout<<cur->var<<" ";cur = cur->right;}}}}void prePrint_m(TreeNode *root){//基本同于中遍历TreeNode *cur = root;TreeNode *pre = NULL;while(cur != NULL){if(cur->left == NULL){cout<<cur->var<<" ";cur = cur->right;}else{pre = cur->left;while( pre->right != NULL && pre->right != cur ){pre = pre->right;}if(pre->right == NULL){pre->right = cur;cout<<cur->var<<" ";cur = cur->left;}else{pre->right = NULL;cur = cur->right;}}}}//this is the most difficult algorithmvoid reverse_out(TreeNode *from,TreeNode *to){//first reverse from->to//reverseTreeNode *cur = from;TreeNode *post = cur->right;while(cur != to){TreeNode *tmp = post->right;post->right = cur;cur = post;post = tmp;}//already reverse,output listTreeNode *traversal = cur;while( cur != from ){cout<<cur->var<<" ";cur = cur->right;}cout<<cur->var<<" ";//reverse originalcur = to;post = cur->right;while(cur != from){TreeNode *tmp = post->right;post->right = cur;cur = post;post = tmp;}//restore to's rightto->right = NULL;}void postPrint_m(TreeNode *root){TreeNode *newroot = new TreeNode(0);newroot->left = root;newroot->right = NULL;TreeNode *cur = newroot;TreeNode *pre = NULL;while(cur != NULL){if(cur->left == NULL){cur = cur->right;}else{pre = cur->left;while(pre->right != NULL && pre->right != cur){pre = pre->right;}if(pre->right == NULL){pre->right = cur;cur = cur->left;}else{pre->right = NULL;reverse_out(cur->left,pre);cur = cur->right;}}}} 可见，前序、中序编程都比较简单，一量涉及后序就会比较麻烦。
爱人，却不一定能够听懂。他们听见的，多是抱怨不休，心烦意乱。
