1. 非递归遍历二叉树算法 (使用stack)
以非递归方式对二叉树进行遍历的算法需要借助一个栈来存放访问过得节点。
(1) 前序遍历
从整棵树的根节点开始，对于任意节点V，访问节点V并将节点V入栈，并判断节点V的左子节点L是否为空。若L不为空，则将L置为当前节点V；若L为空，则取出栈顶节点，并将栈顶结点的右子节点置为当前节点V。重复上述操作，直到当前节点V为空并且栈为空，遍历结束。
(2) 中序遍历
从整棵树的根节点开始，对于任意节点V，判断其左子节点L是否为空。若L不为空，则将V入栈并将L置为当前节点V；若L为空，则取出栈顶节点并访问该栈顶节点，然后将其右子节点置为当前节点V。重复上述操作，直到当前节点V为空节点且栈为空，遍历结束。
(3) 后序遍历
首先将整颗二叉树的根节点入栈。取栈顶节点V，若V不存在左子节点和右子节点，或V存在左子节点或右子节点但其左子节点和右子节点都被访问过了，则访问节点V，并将V从栈中弹出。若非上述两种情况，则将V的右子节点和左子节点(注意先右后左，这样出栈时才能先左后右)依次入栈。重复上述操作，直到栈为空，遍历结束。
2. 二叉树递归与非递归遍历代码
1 #include "stdafx.h" 2 #include3 #include 4 #include 5 6 7 #define Stack_increment 20 8 #define Stack_Size 100 9 10 11 typedef struct Tree 12 { 13 char data; 14 struct Tree *lchild; 15 struct Tree *rchild; 16 }Node; 17 18 Node* createBinaryTree() 19 { 20 Node *root; 21 char ch; 22 scanf("%c", &ch); 23 24 if (ch == '#') 25 { 26 root = NULL; 27 } 28 else 29 { 30 root = (Node *)malloc(sizeof(Node)); 31 root -> data = ch; 32 root -> lchild = createBinaryTree(); 33 root -> rchild = createBinaryTree(); 34 } 35 36 return root; 37 } 38 39 typedef struct 40 { 41 int top; 42 Node* arr[Stack_Size]; 43 }Stacktree; 44 45 void InitStack(Stacktree *S) 46 { 47 S->top = 0; 48 } 49 50 void Push(Stacktree* S, Node* x) 51 { 52 int top1 = S -> top; 53 if (x -> data == '#') 54 { 55 return; 56 } 57 else 58 { 59 S -> arr[top1++] = x; 60 S -> top++; 61 } 62 } 63 64 int Pop(Stacktree *S) 65 { 66 int top = S -> top; 67 if (S->top == 0) 68 { 69 return 0; 70 } 71 else 72 { 73 --(S->top); 74 return 1; 75 } 76 } 77 78 Node* GetTop(Stacktree *S) 79 { 80 int top1 = S -> top; 81 Node*p; 82 p = S -> arr[top1--]; 83 return p; 84 } 85 86 Node* GetTop1(Stacktree *S) 87 { 88 int top1 = S -> top; 89 Node*p; 90 top1--; 91 p = S -> arr[top1]; 92 return p; 93 } 94 95 int IsEmpty(Stacktree *S) 96 { 97 return(S->top == 0 ? 1 : 0); 98 } 99 100 void preorderRecursive(Node *p )101 {102 if (p != NULL)103 {104 printf("%c ", p -> data);105 preorderRecursive(p -> lchild);106 preorderRecursive(p -> rchild);107 }108 }109 110 void inorderRecursive(Node *p )111 {112 if (p != NULL)113 {114 inorderRecursive(p -> lchild);115 printf("%c ", p -> data);116 inorderRecursive(p -> rchild);117 }118 }119 120 void postorderRecursive(Node *p )121 {122 if (p != NULL)123 {124 postorderRecursive(p -> lchild);125 postorderRecursive(p -> rchild);126 printf("%c ", p -> data);127 }128 }129 130 void preordernotRecursive(Node *p)131 {132 if(p)133 {134 Stacktree stree ;135 InitStack(&stree);136 Node *root = p;137 while(root != NULL || !IsEmpty(&stree))138 {139 while(root != NULL)140 {141 printf("%c ", root->data);142 Push(&stree, root);143 root = root -> lchild;144 }145 146 if(!IsEmpty(&stree))147 {148 Pop(&stree);149 root = GetTop(&stree);150 root = root -> rchild;151 }152 }153 }154 }155 156 void inordernotRecursive(Node *p)157 {158 if(p)159 {160 Stacktree stree;161 InitStack(&stree);162 Node *root = p;163 while(root != NULL || !IsEmpty(&stree))164 {165 while(root != NULL)166 {167 Push(&stree, root);168 root = root -> lchild;169 }170 171 if(!IsEmpty(&stree))172 {173 Pop(&stree);174 root = GetTop(&stree);175 printf("%c ", root -> data);176 root = root -> rchild;177 }178 }179 }180 }181 182 void postordernotRecursive(Node *p)183 {184 Stacktree stree;185 InitStack(&stree);186 187 Node *root; 188 Node *pre = NULL; 189 190 Push(&stree, p);191 192 while (!IsEmpty(&stree))193 {194 root = GetTop1(&stree);195 196 if ((root -> lchild == NULL && root -> rchild == NULL) || (pre != NULL && (pre == root -> lchild || pre == root -> rchild)))197 {198 printf("%c ", root -> data);199 Pop(&stree);200 pre = root;201 }202 203 else204 {205 if (root -> rchild != NULL)206 {207 Push(&stree, root -> rchild);208 }209 210 if (root -> lchild != NULL)211 {212 Push(&stree, root -> lchild);213 }214 }215 216 }217 }218 219 void main()220 {221 222 printf("请输入二叉树，'#'为空\n"); 223 Node *root = createBinaryTree();224 225 printf("\n递归先序遍历:\n");226 preorderRecursive(root);227 228 printf("\n递归中序遍历:\n");229 inorderRecursive(root);230 231 printf("\n递归后序遍历:\n");232 postorderRecursive(root);233 234 printf("\n非递归先序遍历\n");235 preordernotRecursive(root);236 237 printf("\n非递归中序遍历\n");238 inordernotRecursive(root);239 240 printf("\n非递归后序遍历\n");241 postordernotRecursive(root);242 243 getchar();244 getchar();245 }
(代码中的top是栈顶元素的上一位的index，不是栈顶元素的index～)
input:
ABC##D##E##
output:
递归先序遍历:
A B C D E
递归中序遍历:
C B D A E
递归后序遍历:
C D B E A
非递归先序遍历:
A B C D E
非递归中序遍历:
C B D A E
非递归后序遍历:
C D B E A
3. Morris Traversal (遍历二叉树无需stack)
Morris Traversal 是一种非递归无需栈仅在常量空间复杂度的条件下即可实现二叉树遍历的一种很巧妙的方法。该方法的实现需要构造一种新型的树结构，Threaded Binary Tree.
3.1 Threaded Binary Tree 定义
Threaded binary tree: A binary tree is threaded by making all right child pointers that would normally be null point to the inorder successor of the node (if it exists), and all left child pointers that would normally be null point to the inorder predecessor of the node. ~WIkipedia
Threaded binary tree 的构造相当于将所有原本为空的右子节点指向了中序遍历的该点的后续节点，把所有原本为空的左子节点都指向了中序遍历的该点前序节点。如图1所示。
那么通过这种方式，对于当前节点cur, 若其右子树为空，(cur -> right = NULL)，那么通过沿着其pre指针，即可返回其根节点继续遍历。
比如对于图1中的节点A，其右孩子为空，则说明以A为根节点的子树遍历完成，沿着其pre指针可以回到A的根节点B，继续遍历。这里的pre指针相当于保存了当前节点的回溯的位置信息。
图1. Threaded binary tree 图2. Threaded tree构造及遍历算法图示
3.2 Threaded Binary Tree 算法实现
3.2.1 算法描述
1. 初始化指针cur = root
2. while (cur != NULL)
2.1 if cur -> left == NULL
a) print(cur -> val)
b) cur = cur -> right
2.2 else if cur -> left != NULL
将pre 指向cur 的左子树中的 最右子节点 (并保证不指回cur)
2.2.1 if pre -> right == NULL
a) pre -> right = cur
b) cur = cur -> left
2.2.2 else if pre -> right != NULL (说明pre -> right是用于指回cur节点的指针)
a) 将pre -> right 置空
b) print(cur -> val)
c) cur = cur -> right
3.2.2 代码实现 (中序)
1 # include2 using namespace std; 3 4 struct TreeNode 5 { 6 int val; 7 struct TreeNode *right; 8 struct TreeNode *left; 9 TreeNode(int x): val(x), left(NULL), right(NULL) {}10 };11 12 vector inorderTraversal(TreeNode *root)13 {14 vector res;15 if(!root) return res;16 TreeNode *cur, *pre;17 cur = root;18 19 while(cur)20 {21 if(cur -> left == NULL)22 {23 res.push_back(cur -> val);24 cur = cur -> right;25 }26 27 else if(cur -> left != NULL)28 {29 pre = cur -> left;30 while(pre -> right && pre -> right != cur) pre = pre -> right;31 if(pre -> right == NULL)32 {33 pre -> right = cur;34 cur = cur -> left;35 }36 else if(pre -> right != NULL)37 {38 pre -> right = NULL;39 res.push_back(cur -> val);40 cur = cur -> right;41 }42 }43 }44 return res;45 }46 47 int main()48 {49 vector res;50 TreeNode *node1 = new TreeNode(1);51 TreeNode *node2 = new TreeNode(2);52 TreeNode *node3 = new TreeNode(3);53 TreeNode *node4 = new TreeNode(4);54 node1 -> left = node2;55 node2 -> left = node3;56 node3 -> right = node4;57 inorderTraversal(node1);58 res = inorderTraversal(node1);59 vector ::iterator it;60 for(it = res.begin(); it != res.end(); ++it)61 {62 cout << *it << " ";63 }64 cout << endl;65 delete node1; delete node2;66 delete node3; delete node4;67 return 0;68 }69 70 // 3 4 2 1
参考：
1. 以先序、中序、后序的方式递归非递归遍历二叉树：
2. Morris Traversal: [LeetCode] Binary Tree Inorder Traversal 二叉树的中序遍历:
3. [LeetCode] Recover Binary Search Tree 复原二叉搜索树:
4. Wikipedia: Threaded binary tree: