关于二叉树的遍历梳理（递归、非递归、线索二叉树）
二叉树作为的基本数据结构，应用广泛，在生活中处处可见，而遍历二叉树在二叉树应用中十分常见。与线性存储结构不同，二叉树每个节点都有可能有两棵子树，从二叉树的存储结构可知：
1 template <typename T>
2 typedef struct BiTNode
3 {
4 T data;
5 struct BiTNode *lchild, *rchild;
6 }BiTree;
根节点、左子树、右子树——二叉树的基本组成单位。那么，根据的递归的思想（数据结构严蔚敏版）：当一个复杂的问题可以分解成若干子问题来处理时，其中某些子问题与原问题有相同的特征属性，则可利用和原问题相同的分析处理方法；反之，这些子问题解决了，原问题也就迎刃而解了。递归遍历就是将原二叉树分解为若干子树。
1 template <typename T>
2 int PreOrderTraverse(BiTree & Tree, int (*Visit)(T & e))
3 {
4 //Visit函数理解为打印e，若成功返回1，否则返回0。
5 if (Tree) //判断树是否为空树
6 {
7 if (Visit(Tree.data)) //打印节点数据
8 if (PreOrderTraverse(Tree.lchild, Visit) //向左遍历
9 if (PreOrderTraverse(Tree.rchild, Visit) return 1; //左遍历退出遍历右侧
10 return 0;
11 }
12 else return 1;
13 }
从递归工作过程可以看出，第i层栈顶，左子树返回i-1层进行右子树遍历，而右子树返回则直接删除栈顶返回（这取决于遍历的方式：先序遍历，中序遍历，后序遍历）。
由此，可以模仿递归算法写出非递归算法的遍历函数。
1 template <typename T>
2 void PreOrderTraverse(BiTNode & Tree, int (*Visit(T e))
3 {
4 InitStack(S); //初始化栈S
5 BiTree p;
6 Push(S, Tree); //根节点入栈
7 while (!StackEmpty(S))
8 {
9 while (GetTop(S, p) && p)
10 {
11 Visit(p.data);
12 Push(S,(p.lchild); //左子树压栈
13 } //while
14 Pop(S, *p); //空指针出栈，用p返回其节点---------1
15 if (!StackEmpty(S))
16 {
17 Pop(S, p); //-------------------------------2
18 Push(S,p.rchild);
19 } //if
20 } //while
21 }
使用栈来管理遍历的过程，由于是先序遍历，所以每向左压一次栈时便Visit一次节点，到达最左端时（依次从根节点Visit了左子树各子树的根节点）向右压栈，到达右叶子节点时回退，由于第17行的退栈，会使得栈顶变为上上层的根节点。也就是遍历右子树时不需要保存当前层的根指针，可直接修改栈顶的指针。说的有些不清楚，但这和递归算法思路一致，不过是自己管理栈的进出。
注意，粗略一看可能会产生疑惑：Pop退栈p多退了一层。这里第一个Pop函数退出空指针，p是其返回值也为空，经过第二个Pop函数p才为有效栈顶。就比如，小红组装某个物件将步骤列了个清单，她将要着手去做这一步骤时，将该步骤从清单划去，划去的这一时刻是上一件事产生的影响。
这两种遍历是对非线性结构进行线性化操作，引用双向链表的前驱后继的思想，修改二叉树的现有数据结构，新增两个标志域——LTag和RTag。
1 template <typename T>
2 typedef struct BiThrNide
3 {
4 T data;
5 int LTag,RTag;
6 BiThrTree *lchild, *rchild;
7 }BiThrTree;
8
9 void InOrderTraverse(BiThrTree & Tree, int (*Visit(T e)))
10 {
11 //Tree的lchild指向树的根节点
12 //标志符LTag、RTag为0则指针域指向孩子节点，为1指向前驱或后继
13 BiThrTree p;
14 while (p != Tree)
15 {
16 while (p.LTag == 0) p = p.lchild; //向左遍历
17 if (!Visit(p.data)) exit(ERROR);
18 while (p.RTag == 1 && p.rchild != Tree) //没有右子树，指向后继，且后继不为头结点
19 {
20 P = P.rchild; //向后继遍历
21 Visit(p.data);
22 }
23 p = p.rchild;
24 }
25 }
由于线索二叉树存储结构较普通二叉树丰满，所以遍历过程也更为好理解，此处不做赘述。