二叉树遍历分为三种：
先序遍历：先访问根结点，其次左节点，最后右节点
中序遍历：先访问左结点，其次跟节点，最后右节点
后序遍历：先访问左结点，其次右节点，最后根节点
三种遍历的递归算法实现形式类似，仅仅是访问顺序不同，非常简洁。如下：
//节点定义typedef struct node {int val;struct node *left;struct node *right;}*pnode, node;
//后序遍历递归算法void postOrderRecursive(pnode root){if (root){//访问左子树postOrderRecursive (root->left);//访问右子树postOrderRecursive (root->right);//访问根结点printf("%d ", root->val);}return ;}//中序遍历递归算法void inOrderRecursive(pnode root){if (root){//访问左子树inOrderRecursive (root->left);//访问根结点printf("%d ", root->val);//访问右子树inOrderRecursive (root->right);}return ;}//先序遍历递归算法void preOrderRecursive(pnode root){if (root){printf("%d ", root->val);//访问左子树preOrderRecursive (root->left);//访问右子树preOrderRecursive (root->right);}return ;}
递归算法属于必知必会的基础，面试如果问到此类问题，一般都会让给出非递归实现。话说，递归算法一般都可以转换成循环和栈的非递归实现。
对于先序遍历来说，先将根结点入栈，进入循环，取栈顶，先将节点右孩子和左孩子依次进栈，访问该节点，按照此节奏，循环处理，直到栈空。即，每次取出栈顶元素，将其右左孩子节点依次进栈，访问即可。
//先序遍历非递归void preOrderNonRec(pnode root){pnode stack[1000], curr, prev;int top, end;if (root == NULL)return ;top = end = 0;//根结点入栈stack[top++] = root;while (top > 0){//取栈顶curr = stack[--top];//右子树入栈if (curr->right)stack[top++] = curr->right;//左子树入栈if (curr->left)stack[top++] = curr->left;//访问节点printf ("%d ", curr->val);}printf("\n");return ;}
对于中序遍历的非递归算法，依然是栈加循环的方式，处理上和上一步略微有点区别。
先将根结点入栈，当前节点指向左孩子，只要当前节点的左孩子存在，则继续循环处理，即父节点进栈，节点指向左孩子，直到节点为空，这时，从栈中取出栈顶，对于栈中取出的元素，总是先访问，然后指向右孩子，继续第一步处理，即父节点进栈，节点指向左孩子。这里需要注意的有两点：1. 从栈中取出来的元素访问后无需再进栈。2. 对于栈中取出的元素，总是先访问，然后指向右孩子。
//中序遍历，非递归void inorderNonRec(pnode root){pnode stack[1000], curr;int top, end;if (root == NULL)return ;top = end = 0;//根结点进栈stack[top++] = root;//当前节点指向左孩子curr = root->left;while (curr || top > 0){//节点存在，则父节点进栈，指向左孩子if (curr){if (curr->left){stack[top++] = curr;curr = curr->left;continue;}}else{curr = stack[--top];}//取栈顶，访问后，指向右孩子printf("%d ", curr->val);curr = curr->right;}printf("\n");return ;}
后序遍历的非递归实现依然是循环加栈处理。和中序遍历一样，不过处理上略微有点不同。相当之处仍然是父节点先进栈，指向左孩子。不同的地方在于，从栈中取出元素时，此时不访问，而是如果存在右孩子，则父节点继续进栈，节点指向其右孩子。如果右孩子不存在，则访问该节点，同时记录当前访问的节点。继续出栈，同上步，如果存在右孩子，父节点继续进栈，节点指向其右孩子，此时，为防止死循环，需要将右孩子和之前访问的节点比较，如果相同，则无需进栈，此时直接访问即可。不理解的同学请画一颗二叉树辅助思考。
//后序遍历，非递归void postOrderNonRec(pnode root){pnode stack[1000], curr, prev;int top, end;if (root == NULL)return ;top = end = 0;//根结点入栈stack[top++] = root;//指向左孩子curr = root->left;while (curr || top > 0){//只要存在孩子节点，则父节点进栈，指向其孩子节点。if (curr){if (curr->left || curr->right){stack[top++] = curr;if (curr->left)curr = curr->left;elsecurr = curr->right; continue;}}else{//取栈顶，如果存在右孩子且和上一个访问节点不一样，则父节点//继续进栈，指向右孩子。curr = stack[--top];if (curr->right && curr->right != prev){stack[top++] = curr;curr = curr->right;continue;}}//访问节点同时保存访问的位置。printf("%d ", curr->val);prev = curr;curr = NULL;}printf("\n");return ;}
=============================================================================================
Linux应用程序、内核、驱动、后台开发交流讨论群(745510310)，感兴趣的同学可以加群讨论、交流、资料查找等，前进的道路上，你不是一个人奥^_^。
