中国石油大学数据结构上机实验6

《数据结构》实验报告学号2015011512姓名胡明禹专业数学与应用数学时间2018.5.8一、实验题目实验6二叉树的遍历二、实验目的1.掌握二叉树的存储思想与建立算法2.掌握二叉树各种遍历方法的实现思想3.实现二叉链表的递归遍历算法与非递归遍历算法三、算法设计分析（一）实验内容1.从键盘输入数据，建立一颗含有n个结点的二叉树2.从对二叉树进行先序，中序和后序遍历的递归算法实现，输出遍历序列3.实现先序遍历或中序遍历的非递归算法实现（二）总体设计此处给出主要函数功能、及函数间调用关系的的描述。例如：①先序创建二叉树函数②先序遍历函数③中序遍历函数④后序遍历函数⑤前序遍历非递归算法⑥中序遍历非递归算法其功能描述如下：（1）主函数：统筹调用各个函数以实现相应功能voidmain()（2）①先序创建二叉树StatusCreateBiTree(BiTree&T){charch;scanf(%c,&ch);if(ch=='')T=NULL;else{if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))exit(OVERFLOW);T-data=ch;CreateBiTree(T-lchild);CreateBiTree(T-rchild);}returnOK;}②先序遍历StatusPreOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){if(T){if(Visit(T-data))if(PreOrderTraverse(T-lchild,Visit))if(PreOrderTraverse(T-rchild,Visit))returnOK;returnERROR;}elsereturnOK;}③中序遍历StatusInOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){if(T){if(InOrderTraverse(T-lchild,Visit))if(Visit(T-data))if(InOrderTraverse(T-rchild,Visit))returnOK;returnERROR;}elsereturnOK;}④后序遍历函数StatusPostOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){if(T){if(PostOrderTraverse(T-lchild,Visit))if(PostOrderTraverse(T-rchild,Visit))if(Visit(T-data))returnOK;returnERROR;}elsereturnOK;}⑤先序遍历非递归算法StatusIPreOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){BiTreep;p=T;intNUM=-1;BiTNode*stack[30];while(p||NUM0){Visit(p-data);NUM++;stack[NUM]=p;p=p-lchild;while(!p&&NUM-1){p=stack[NUM];NUM--;p=p-rchild;}}returnOK;}⑥中序遍历非递归算法StatusIInOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){BiTreep;p=T;intNUM=0;BiTNode*stack[30];while(p||NUM0){if(p){stack[NUM++]=p;p=p-lchild;}else{NUM--;p=stack[NUM];if(!Visit(p-data))returnERROR;p=p-rchild;}}returnOK;四、实验测试结果及结果分析（一）测试结果（此处给出程序运行截图）（二）结果分析成功完成了题目的基本操作。五、实验总结附录实验程序代码(该部分请加注释)#includestdio.h#includestdlib.h#includemalloc.h#defineOK1#defineERROR0#defineOVERFLOW-1typedefcharTElemType;typedefintStatus;typedefstructBiTNode{//二叉树的二叉链表存储表示TElemTypedata;//结点数据structBiTNode*lchild,*rchild;//左右孩子指针}BiTNode,*BiTree;StatusCreateBiTree(BiTree&T){//先序创建二叉树，从键盘输入数据charch;scanf(%c,&ch);if(ch=='')T=NULL;else{if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))exit(OVERFLOW);T-data=ch;CreateBiTree(T-lchild);CreateBiTree(T-rchild);}returnOK;}StatusVisit(TElemTypee){putchar(e);returnOK;}StatusPreOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){//先序if(T){if(Visit(T-data))if(PreOrderTraverse(T-lchild,Visit))if(PreOrderTraverse(T-rchild,Visit))returnOK;returnERROR;}elsereturnOK;}StatusInOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){//中序if(T){if(InOrderTraverse(T-lchild,Visit))if(Visit(T-data))if(InOrderTraverse(T-rchild,Visit))returnOK;returnERROR;}elsereturnOK;}StatusPostOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){//后序if(T){if(PostOrderTraverse(T-lchild,Visit))if(PostOrderTraverse(T-rchild,Visit))if(Visit(T-data))returnOK;returnERROR;}elsereturnOK;}StatusIPreOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){//先序遍历非递归算法BiTreep;p=T;intNUM=-1;BiTNode*stack[30];while(p||NUM0)//p不为空或栈不为空时循环{Visit(p-data);//打印当前节点NUM++;stack[NUM]=p;//当前节点进栈p=p-lchild;//在左子树上移动while(!p&&NUM-1)//若左子树为空，则让栈顶元素出栈，并在右子树上寻找直到pCur不为空{p=stack[NUM];NUM--;p=p-rchild;}}returnOK;}StatusIInOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){//中序遍历非递归算法BiTreep;p=T;intNUM=0;BiTNode*stack[30];while(p||NUM0){if(p){stack[NUM++]=p;p=p-lchild;}else{NUM--;p=stack[NUM];if(!Visit(p-data))returnERROR;p=p-rchild;}}returnOK;}voidmainmenu()//输出菜单,供用户进行操作选择{printf(1.创建二叉树\n);printf(2.先序遍历的递归\n);printf(3.中序遍历的递归\n);printf(4.后序遍历的递归\n);printf(5.先序遍历的非递归\n);printf(6.中序遍历的非递归\n);printf(0.退出\n);}voidmain()//主函数{BiTreeT;intchoose;while(1){mainmenu();printf(\n请输入你的选择：);scanf(%d,&choose);switch(choose){case1://在此插入创建二叉树函数system(cls);CreateBiTree(T);system(PAUSE);system(cls);break;case2://在此插入递归先序遍历函数system(cls);fflush(stdin);PreOrderTraverse(T,Visit);printf(\n);system(PAUSE);system(cls);break;case3://在此调用递归中序遍历函数system(cls);fflush(stdin);InOrderTraverse(T,Visit);system(PAUSE);system(cls);break;case4://在此调用递归后序遍历函数system(cls);flush(stdin);PostOrderTraverse(T,Visit);system(PAUSE);system(cls);break;case5://在此调用非递归先序遍历函数system(cls);fflush(stdin);IPreOrderTraverse(T,Visit);printf(\n);system(PAUSE);system(cls);break;case6://在此调用非递归中序遍历函数system(cls);fflush(stdin);IInOrderTraverse(T,Visit);system(PAUSE);system(cls);break;case0://退出exit(0);break;default://输入非法，提示用户重新输入printf(\n输入错误，重新输入！\n);}}}