二叉树的应用程序设计

实验三：二叉树建立及遍历操作一、实验目的1.熟悉二叉树的存贮结构及遍历方式，掌握有关算法的实现。2.能够利用二叉树解决具体问题。二、实验环境1.硬件：每个学生需配备计算机一台。2.软件：DOS或Windwos操作系统+TurboC；三、实验要求1.要求采用二叉链表作为存贮结构，完成二叉树的建立、先序、中序、和后序遍历的操作。其中先序遍历和后序遍历采用递归算法，中序遍历采用非递归算法。2.输入数据：树中每个结点的数据类型设定为字符型。四、实验内容1.在自己的U盘“姓名+学号”文件夹中创建“实验六”文件夹，本次实验的所有程序和数据都要求存储到本文件夹中。2.完成如下二叉树处理函数。建树子函数先序遍历子函数中序遍历子函数后序遍历子函数程序代码：#includestdio.h#includestdlib.h#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10intleafcount=0;typedefstructBiTNode{chardata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree,*SElemType;typedefstruct{SElemType*base;SElemType*top;intstacksize;}SqStack;intgjy_InitStack(SqStack*S){S-base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!S-base)exit(0);S-top=S-base;S-stacksize=STACK_INIT_SIZE;return1;}intgjy_StackEmpty(SqStack*S){if(S-base==S-top)return1;elsereturn0;}intgjy_Push(SqStack*S,BiTreee){if(S-top-S-base=S-stacksize){S-base=(SElemType*)realloc(S-base,(S-stacksize+STACKINCREMENT)*sizeof(SElemType));if(!S-base)exit(0);S-top=S-base+S-stacksize;S-stacksize+=STACKINCREMENT;}*S-top++=e;return1;}BiTNode*gjy_Pop(SqStack*S,BiTreee){if(S-top==S-base)return0;e=*--S-top;printf(%c,e-data);returne;}intgjy_CreateBiTree(BiTree*T){charch;scanf(%c,&ch);if(ch==''){*T=NULL;}else{if(!(*T=(BiTree)malloc(sizeof(BiTNode))))return0;(*T)-data=ch;gjy_CreateBiTree(&((*T)-lchild));gjy_CreateBiTree(&((*T)-rchild));}return1;}intgjy_preOrder(BiTreeT){if(T){printf(%c,T-data);if(!T-lchild&&!T-rchild)leafcount+=1;gjy_preOrder(T-lchild);gjy_preOrder(T-rchild);}return1;}intgjy_InOrderTraverse2(BiTreeT){SqStackS;BiTreep,t;gjy_InitStack(&S);p=T;while(p||!gjy_StackEmpty(&S)){if(p){gjy_Push(&S,p);p=p-lchild;}else{t=gjy_Pop(&S,p);p=t;p=p-rchild;}}return1;}intgjy_oldOrder(BiTreeT){if(T!=NULL){gjy_oldOrder(T-lchild);gjy_oldOrder(T-rchild);printf(%c,T-data);}return1;}voidmain(){BiTreeT;leafcount=0;gjy_CreateBiTree(&T);printf(*************高君燕****************\n);printf(先序遍历序列为：);gjy_preOrder(T);printf(\n中序遍历序列为：);gjy_InOrderTraverse2(T);printf(\n后序遍历序列为：);gjy_oldOrder(T);printf(\n叶子节点：%d\n,leafcount);}运行结果：