编写的方法：根据树中结点的遍历规律及顺序直接写出其非递归算法。先序非递归算法【思路】假设：T是要遍历树的根指针，若T != NULL对于非递归算法，引入栈模拟递归工作栈，初始时栈为空。问题：如何用栈来保存信息，使得在先序遍历过左子树后，能利用栈顶信息获取T的右子树的根指针？方法1：访问T->data后，将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，再先序遍历T的右子树。方法2：访问T->data后，将T->rchild入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T->rchild，出栈，遍历以该指针为根的子树。【算法1】void PreOrder(BiTree T, Status ( *Visit ) (ElemType e)){ // 基于方法一，流程图如右，当型循环InitStack(S);while ( T!=NULL || !StackEmpty(S)){while ( T != NULL ){Visit(T->data) ;Push(S,T);T = T->lchild;}if( !StackEmpty(S) ){Pop(S,T);T = T->rchild;}}}【算法2】void PreOrder(BiTree T, Status ( *Visit ) (ElemType e)){ // 基于方法二，流程图如右，当型循环InitStack(S);while ( T!=NULL || !StackEmpty(S) ){while ( T != NULL ){Visit(T->data);Push(S, T->rchild);T = T->lchild;}if ( !StackEmpty(S) ){Pop(S,T);}}}进一步考虑：对于处理流程中的循环体的直到型、当型+直到型的实现。中序非递归算法【思路】T是要遍历树的根指针，中序遍历要求在遍历完左子树后，访问根，再遍历右子树。问题：如何用栈来保存信息，使得在中序遍历过左子树后，能利用栈顶信息获取T指针？方法：先将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，访问T->data，再中序遍历T的右子树。【算法】void InOrder(BiTree T, Status ( *Visit ) (ElemType e)){ // 流程图如右，当型循环InitStack(S);while ( T!=NULL || !StackEmpty(S) ){while ( T != NULL ){Push(S,T);T = T->lchild;}if( !StackEmpty(S) ){Pop(S, T);Visit(T->data);T = T->rchild;}}}进一步考虑：对于处理流程中的循环体的直到型、当型+直到型的实现。后序非递归算法【思路】T是要遍历树的根指针，后序遍历要求在遍历完左右子树后，再访问根。需要判断根结点的左右子树是否均遍历过。可采用标记法，结点入栈时，配一个标志tag一同入栈(0：遍历左子树前的现场保护，1：遍历右子树前的现场保护)。首先将T和tag(为0)入栈，遍历左子树；返回后，修改栈顶tag为1，遍历右子树；最后访问根结点。typedef struct stackElement{Bitree data;char tag;}stackElemType;【算法】void PostOrder(BiTree T, Status ( *Visit ) (ElemType e)){ // 流程图如右，当型循环InitStack(S);while ( T!=NULL || !StackEmpty(S) ){while ( T != NULL ){Push(S,T,0);T = T->lchild;}while ( !StackEmpty(S) && GetTopTag(S)==1){Pop(S, T);Visit(T->data);}if ( !StackEmpty(S) ){SetTopTag(S, 1); // 设置栈顶标记T = GetTopPointer(S); // 取栈顶保存的指针T = T->rchild;}else break;}}
原文地址：http://www.yuanma.org/data/2006/0605/article_652.htm
