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

《后序遍历二叉树的非递归算法.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1．请根据用户输入的“扩展的先序遍历序列”(用小圆点表示空子树)，建立以二叉链表方式存储的二叉树，然后写出后序遍历该二叉树的非递归算法。方法一：#include#include#defineMAX_TREE_SIZE100typedefstructBiTNode{chardata;structBiTNode*lchild;structBiTNode*rchild;}BiTNode,*BiTree;//函数声明voidPrint(BiTree*root);voidSelection(intsel,B

2、iTree*root);voidReadExPreOrder(BiTree*root);voidPrintExPreOrder(BiTreeroot);voidPostOrderTraverse(BiTreeT);//主函数voidmain(){BiTreeroot=NULL;//初始化根结点Print(&root);while(true){printf("Pressentertocontinue.........");getchar();getchar();system("cls");Print(&root);}}voidPri

3、nt(BiTree*root){//提示intsel;printf("使用说明:本程序可实现二叉链表方式存储的二叉树，输入为扩展先序遍历序列.");printf("---------------------");printf("1.输入扩展先序遍历序列并建立对应的二叉树.");printf("2.打印当前的二叉树的扩展先序遍历序列.");printf("3.后序遍历当前的二叉树并打印遍历序列.");printf("4.按其它任意键退出.");printf("---------------------");p

4、rintf("请选择你要的操作:");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(B

5、iTree*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!=N

6、ULL){ch=root->data;printf("%c",ch);PrintExPreOrder(root->lchild);PrintExPreOrder(root->rchild);}elseprintf(".");}voidPostOrderTraverse(BiTreeT){BiTreestack[MAX_TREE_SIZE],p;inttag[MAX_TREE_SIZE],top=0;p=T;while(p

7、

8、top!=0){while(p){top++;stack[top]=p;tag[top]=0;p=p->lchi

9、ld;//从根开始，左结点依次入栈}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}//end

10、ofwhile}方法二（顺序栈）：#includeusingnamespacestd;typedefstructnode{charch;structnode*lchild;structnode*rch