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

《中国石油大学数据结构上机实验6》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、《数据结构》实验报告学号2015011512姓名胡明禹专业数学与应用数学时间2018.5.8一、实验题目实验6二叉树的遍历二、实验目的1.掌握二叉树的存储思想与建立算法2.掌握二叉树各种遍历方法的实现思想3.实现二叉链表的递归遍历算法与非递归遍历算法三、算法设计分析(一)实验内容1.从键盘输入数据，建立一颗含有n个结点的二叉树2.从对二叉树进行先序，中序和后序遍历的递归算法实现，输出遍历序列3.实现先序遍历或中序遍历的非递归算法实现(二)总体设计此处给出主要函数功能、及函数间调用关系的的描述。例如：①先序创建二叉树函数②先序遍历函数③屮序遍历函数④后序遍历函数⑤前序遍历非递

2、归算法⑥中序遍历非递归算法其功能描述如下：(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;}②先遍历StatusPreOrderTravers

3、e(BiTreeT,Status(*Visit)(TEIemTypee)){if(T){if(Visit(T->data))if(PreOrderTraverse(T->lchild,Visit))if(PreOrderTraverse(T->rchild,Visit))returnOK;returnERROR;}elsereturnOK;}©中序遍历StatuslnOrderTraverse(BiTreeT,Status(*Visit)(TEIemTypee)){if⑴{if(lnOrderTraverse(T->lchild,Visit))if(Visit(T->dat

4、a))if(lnOrderTraverse(T->rchild,Visit))returnOK;returnERROR;}elsereturnOK;}④后序遍历函数StatusPostOrderTraverse(BiTreeT,Status(*Visit)(TEIemTypee)){if(T){if(PostOrderTraverse(T->lchild,Visit))if(PostOrderTraverse(T->rchild,Visit)}if(Visit(T->data))returnOK;returnERROR;}elsereturnOK;}⑤先序遍历非递归算法St

5、atusIPreOrderTraverse(BiTreeT,Status(*Visit)(TEIemTypee)){BiTreep;p=T;intNUM=-1;BiTNode*stack[30];while(p

6、

7、NUM>0){Visit(p->data);NUM++;stack[NUM]=p;p=p->lchild;while(!p&&NUM>-l){p=stack[NUM];NUM-;p=p->rchild;}returnOK;}④屮序遍历非递归算法StatusIlnOrderTraversefBiTreeT/Status(*Visit)(TEIemTypee)){Bi

8、Treep;p=T;intNUM=0;BiTNode*stack[30];while(p

9、

10、NUM>0){if(p){stack[NUM++]=p;p=p->lchild;}else{NUM-;p=stack[NUM];if(!Visit(p->data))returnERROR;p=p->rchild;}}returnOK;四、实验测试结果及结果分析（一）测试结果（此处给山程序运行截图）"D:MicrosoftVisualStudioCommonMSDev98BinDebughmy6.exe"木木木木木木木彐彐J3J3J3递递525251":•二-二二,、I二

11、I二叉历历历历历二先中后先1.2.3.4.5.6.0.木木木木木木木请输入你的选择:"D:MicrosoftVisualStudioCommonMSDev98BinDebughmy6.exe”ABCDEGF请按任意键继续."D:MicrosoftVisualStudioCommonMSDev98BinDebughmy6.exe”ABCDEGF请按任意键继续.B3"D:MicrosoftVisualStudioCommonMSDev98BinDebughmy6.exe"CBEGDF