A-A+
二叉树的非递归遍历
二叉树遍历有以下几种情况：
- 先序遍历：先遍历根节点，再左子数，再右子树
- 中序遍历：先遍历左子树，再根节点，再右子树
- 后续遍历：先遍历左子树，再右子树，再根节点
要使用非递归的方法，使用栈来模拟递归遍历
非递归的先序遍历二叉树
访问根节点后，循环遍历左子树，此时根，左节点都已经被处理了，只要右子树压入栈即可；当左子树遍历完后，从栈中取出右子树；并对该子树重复上述过程。
void preOrder(BiTree T){ Stack S = initStack(); while(T != NULL||!isEmpty(S)){ while(T != NULL){ visit(T); T = T->leftChild; S.push(T->rightChild); } if(!isEmpty(S)){ T = S.pop(); } } } |
非递归的中序遍历二叉树
在非递归中，需要从根节点-》左子树-》根节点-》右子树
循环遍历左子树的根并压入栈；无左子树时从栈中取出，此时第二次遇到根节点，已经可以处理根了；然后对该节点右子树重复上述过程。
void inOrder(BiTree T){ Stack S = initStack(); while(T != NULL || !isEmpty(S)){ while(T != NULL){ S.push(T); T = T->leftChild; } if(!isEmpty(S)){ T = S.pop(); visit(T); T = T->rightChild; } } } |
非递归的后序序遍历二叉树
后序遍历需要左右子树均遍历后再处理根节点，在非递归中，需要从根节点-》左子树-》根节点-》右子树-》根节点（此时处理）-》上一级。第一次遇到根节点时，压入栈，打个标记位0；第二次遇到时，此时从标记位0得知右子树还未遍历，设标记位为1，再去处理右子树；第三次遇到，从标记位1得知，左右子树均已经遍历，次数处理根节点，从栈中弹出。
struct node{T, tag};
void postOrder(BiTree T){ Stack S = initStack(); while(T != NULL || !S.empty()){ while(T != NULL){ S.push(T, 0); T = T->leftChild; } if(!S.empty() && S.topHitted() == 1){ T = S.pop(); visit(T); } if(!S.empty()){ T = S.top(); T.setHitted(1); T = T->rightChild; }else break; } } |
