后序遍历二叉树的非递归算法.doc

文档介绍：请根据用户输入的“扩展的先序遍历序列”(用小圆点表示空子树),建立以二叉链表方式存储的二叉树,然后写出后序遍历该二叉树的非递归算法。方法一:#include<>#include<>#defineMAX_TREE_SIZE100typedefstructBiTNode{ chardata; structBiTNode*lchild; structBiTNode*rchild;}BiTNode,*BiTree;//函数声明voidPrint(BiTree*root);voidSelection(intsel,BiTree*root);voidReadExPreOrder(BiTree*root);voidPrintExPreOrder(BiTreeroot);voidPostOrderTraverse(BiTreeT);//主函数voidmain() { BiTreeroot=NULL;//初始化根结点 Print(&root); while(true) { printf("\nPressentertocontinue........."); getchar(); getchar(); system("cls"); Print(&root); }}voidPrint(BiTree*root) {//提示 intsel; printf("使用说明:本程序可实现二叉链表方式存储的二叉树,输入为扩展先序遍历序列.\n"); printf("---------------------\n"); printf(".\n"); printf(".\n"); printf(".\n"); printf(".\n"); printf("---------------------\n"); printf("请选择你要的操作:"); scanf("%d",&sel); getchar(); Selection(sel,root);}voidSelection(intsel,BiTree*root) {//根据用户输入决定下一步骤 switch(sel){ case1:ReadExPreOrder(root); break; case2:PrintExPreOrder(*root); break; case3:PostOrderTraverse(*root); break; default:exit(0); }}voidReadExPreOrder(BiTree*root) {//先序遍历二叉树,root为指向二叉树(或某一子树)根结点的指针 charch; ch=getchar(); if(ch=='.') *root=NULL; else{ (*root)=(BiTree)malloc(sizeof(BiTNode)); (*root)->data=ch; ReadExPreOrder(&((*root)->lchild)); ReadExPreOrder(&((*root)->rchild)); }}voidPrintExPreOrder(BiTreeroot) { charch; if(root!=NULL) { ch=root->data; printf("%c",ch); PrintExPreOrder(root->lchild); PrintExPreOrder(root->rchild); } else printf(".");}voidPostOrderTraverse(BiTreeT){ BiTreestack[MAX_TREE_SIZE],p; inttag[MAX_TREE_SIZE],top=0; p=T; while(p||top!=0) { while(p){ top++; stack[top]=p; tag[top]=0; p=p->lchild;//从根开始,左结点依次入栈} if(top>0){ if(tag[top]==1){//表示是从该结点的右子树返回,则访问该结//点 p=stack[top]; printf("%c",p->data); top--; p=NULL;//将p指向NULL,则下次进入while循环时,不做左子//树入栈操作} else{//表明是从该结点左子树返回,应继续访问其右子树 p=stack[top]; if(top>0){ p=p->rchild; tag[top]=1;//表明该结点的右子树已访问} }//endofelse }//endofif }//endofwhile}方法二(顺序栈):#include<ios