树的非递归遍历算法.doc

例3：设一棵二叉树以二叉链表为存储结构，写一个把二叉树左右子树交换的算法。void exchange(BiTree T) /交换二叉树的左右子树 if (!T)b=NULL; /二叉树为空else b=(BiTNode *)malloc(sizeof(BiTNode); /复制一个根结点 b-data=T-data; b1=exchange(b-lchild); b2=exchange(b-rchild); b-lchild=b2; b-rchild=b1;return(b); Void swap(BiTree t) if (t) if( t-lchild!=NULL| t-rchild!=NULL) t-lchildt-rchild; if(t-lchild) swap(t-lchild); if(t-rchild) swap(t-rchild); 四、非递归法遍历二叉树有的算法语言中是不允许过程的递归调用的，因此有必要讨论以下三种遍历的非递归算法。非递归的过程需要借助于栈来保存遍历中经过的路径，才能访问到二叉树的所有结点。中序一：Status InorderTraverse(BiTree T,Status(*Visit)(TElemType e)InitStack(S); Push(S,T); /根指针进栈while (!StackEmpty(S)while (GetTop(S,p)&p) Push(S, p-lchild); /向左走到尽头Pop(S,p); /空指针退栈if (!StackEmpty(S) /访问结点，向右一步Pop(S,p);if(!Visit(p-data) return ERROR;Push(S,p-rchild);return OK;中序二：Status InorderTraverse(BiTree T,Status(*Visit)(TElemType e)InitStack(S); p=T; while(p|!StackEmpty(S)if(p)Push(S,p); p=p-lchild;/根指针进栈，遍历左子树else /根指针退栈，访问根节点，遍历右子树Pop(S,p); if(!Visit(p-data) return ERROR;p=p-rchild);/else/whilereturn OK;/InOrderTravserse补充：1. 对二叉树进行先序遍历的非递归算法思路：采用栈，先让根结点入栈，然后退栈，如有左右孩子，则先让右孩子入栈，然后左孩子入栈，如此反复实现前序遍历。Status preorder(BiTree T, Status(*Visit)(TelemType e) /对以二叉链表为存储结构的二叉树，进行先序遍历的非递归算法 InitStack(s)； Push(s,T); /根结点入栈while( !StackEmpty(s) ) /栈非空GetTop(s,p) Visit( p-data); Pop(s,p); if (p-rchild) Push(s,p-rchild); if(p-lchild) Push(s, p-lchild ); /while return OK;/ preorder2. 对二叉树进行后序遍历的非递归算法Typedef struct Bittree ptr;Int tag;stacknode; Typedef struct stacknod Elemmaxsize;Int top;SeStack;Void postorder(Bitree t) SqStack s; Stacknode x; InitStack(s)； p=t; do while (p) x.ptr=p; x.tag=0; Push(S,x); p=p-lchild; While(!StackEmpty(s) & s.Elems.top=1) pop(s,x); p=x.ptr; Visit( p-data); If ( !S