【囤】二叉树遍历的非递归实现
a.先序遍历的非递归算法
思路
假设：T指向要遍历的二叉树的根，若T !=NULL 对于非递归算法，引入栈模拟递归工作栈，初始栈为空。
问题：如何用栈来保存信息，使得在先序遍历过左子树后，能利用栈顶信息获取T的右子树的根指针？
方法：访问T->data后，将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，再先序遍历T的右子树。
问题：如何用栈来保存信息，使得在先序遍历过左子树后，能利用栈顶信息获取T的右子树的根指针？
方法：访问T->data后，将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，再先序遍历T的右子树。
代码实现
void Preorder_I(BiTree T, void (*visit)(TelemType &e)){
Stack *S;
initStack(S);
t=T;
while(!(t == NULL && StackEmpty(S)) {
while(t){
visit(t->data);
push(S,t);
t=t->lchild;
}
if (StackEmpty(S))
return; // 栈空时结束
else {
t = Pop(S);
t=t->rchild；
}
} // while
}// Preorder_I b.中序遍历的非递归算法
思路
假设：T是指向要遍历的二叉树的根，中序遍历要求在遍历完左子树后，访问根，再遍历右子树。问题：如何用栈来保存信息，使得在中序遍历过左子树后，利用栈顶信息获取T指针？
方法：先将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，访问T->data，再中序遍历T的右子树。
代码实现
void Inorder_I(BiTree T, void (*visit)(TelemType &e)){
Stack* S;
t = T;
while (!(t == NULL && StackEmpty(S)) {
while (t) {
push(S, t);
t = t->lchild;
}
if (StackEmpty(S)) return; // 栈空时结束
else {
t = Pop(S);
visit(t->data);
t = t->rchild;
}
} // while
}// Inorder_I c.后续遍历的非递归算法
思路
假设：T指向要遍历的二叉树的根，后序遍历要求在遍历完左右子树后，再访问根。
问题：需要判断根结点的左右子树是否均遍历过。
方法：可采用标记法，结点入栈时，配一个标志tag一同入栈（0：遍历左子树前的现场保护，1：遍历右子树前的现场保护）。
首先将T和tag（为0）入栈，遍历左子树；返回后，修改栈顶tag（为1），遍历右子树；最后访问根结点。
代码实现
void Postorder_I(BiTree T, void (*visit)(TelemType &e)){
Stack* S;
t = T;
while (!(t == NULL && StackEmpty(S))){
if (t) {
push(S, (t, 1));
t = t->lchild;
}
else {
t = top(s).link;
sign = top(s).tag;
pop(s);
if (sign == 1) {
push(S, (t, 2));
t = t->rchild;
}
else {
Visit(t->data);
t = NULL;
}
}
} // while
}// Postorder_I 
查看9道真题和解析