实验13-full - 二叉树非递归遍历

实用文档实验十三二叉树非递归遍历1.创建一个包含数字元素的完全二叉树，使用switch函数，根据用户的输入，同时具有如下功能：【1】初始化一个二叉树提示：scanf("%d%d",&i,&x);//i是按满二叉树编号，节点应有的序号，x是节点的数据先建立一个新节点，再利用性质5，建立新节点与其双亲的左/右孩子的关系。【2】前序非递归遍历，打印出各节点的数据【3】中序非递归遍历，打印出各节点的数据【4】后序非递归遍历，打印出各节点的数据【5】结束程序运行#include<stdio.h>#include<stdlib.h>structnode{ intdata; structnode*lc,*rc;};structnode*root;intm=0;main(){ intcord; structnode*creat(); voidpreorderz(structnode*t); voidinorder(structnode*t); voidpostorder(structnode*t); do { printf("\n主菜单\n"); printf("1建立二叉树\n"); printf("2先序非递归遍历\n"); printf("3中序非递归遍历\n"); printf("4后序非递归遍历\n"); printf("5结束程序运行\n"); printf("-----------------------------------\n"); printf("请输入您的选择(1,2,3,4,5)"); scanf("%d",&cord); switch(cord) { case1: { root=creat();//建立二叉树 printf("建立二叉树程序以执行完，\n"); printf("请返回主菜单，用遍历算法验证程序的正确性\n"); }break; case2: { preorderz(root); }break; case3: { inorder(root); }break; case4: { postorder(root); }break; case5: { printf("二叉树程序执行完，再见！\n"); exit(0); } } }while(cord<=6);}structnode*creat(){ structnode*t,*q,*s[30]; inti,j,x; printf("i,x="); scanf("%d%d",&i,&x);//i是按满二叉树编号，节点应有的序号，x是节点的数据 while((i!=0)&&(x!=0)) { q=(structnode*)malloc(sizeof(structnode)); q->data=x; q->lc=NULL; q->rc=NULL;//建立新节点q s[i]=q; if(i==1) t=q;//t代表树根节点 else { j=i/2;//i的双亲节点的编号 if((i%2)==0) s[j]->lc=q; else s[j]->rc=q; } printf("i,x="); scanf("%d%d",&i,&x); } return(t);}voidpreorderz(structnode*p)//前序非递归算法{ structnode*q,*s[30];//s辅助栈 inttop,bools; q=p;top=0;//栈顶指针 bools=1;//bools=1为真值继续循环；bools=0为假时栈空，结束循环 do { while(q!=NULL) { printf("%6d",q->data);//访问节点 top++; s[top]=q; q=q->lc; } if(top==0) bools=0; else { q=s[top]; top--; q=q->rc; } }while(bools); printf("\n");}voidinorder(structnode*p)//中序非递归遍历{ structnode*s[30],*q; inttop,bools; q=p;top=0; bools=1; do { while(q!=NULL) { top++; s[top]=q; q=q->lc; } if(top==0) bools=0; else { q=s[top]; top--; printf("%6d",q->data);//访问节点 q=q->rc; } }while(bools);}voidpostorder(structnode*p){ structnode*s[30],*s2[30],*q; inttop,bools; q=p;top=0; bools=1; do { while(q!=NULL) { top++; s[top]=q; s2[top]=1; q=q->lc; } if(top==0) bools=0; else { if(s2[top]==1) { s2[top]=2; q=s[t