数据结构2叉数遍历

1、内蒙古工业大学信息工程学院实 验 报 告课程名称： 数据结构与算法 实验名称: 二叉树遍历算法的设计 实验类型： 验证性综合性 设计性实验室名称： * 班级： * 学号： *姓名： * 组别： 同组人： 成绩： 实验日期： 2013-9-24 实验报告撰写要求一、 实验前用预习报告纸撰写预习报告，预习报告包括以下内容1 实验目的2 实验用仪器设备、器材或软件环境3 实验原理、方案设计、程序框图、预编程序等4 实验过程中需要记录的实验数据表格二、 实验过程中，要认真观察，仔细记录三、 完成实验后用实验报告纸撰写实验报告，包括以下内容1 仪器设备型号及编号2 实验器材或软件环境3 实验步骤、程序调

2、试方法4 实验数据处理及结果分析5 实验中存在的问题6 体会及思考题四、 报告撰写时，要求格式规范、书写整齐1信息工程学院数据结构与算法程序设计报告预习报告成绩： 指导教师审核（签名）： 年 月 预习报告实验二 二叉树遍历算法的设计一、目的本实验的目的是理解二叉树的逻辑结构和二叉链表存储结构，进一步提高使用理论知识指导解决实际问题的能力，并对算法性能进行分析。二、 题目二叉树遍历算法的设计。三、 实验类型设计性。方案一采用递归算法实现二叉树遍历算法。方案二采用非递归算法实现二叉树遍历算法。四、要求及提示 要求： （1）两种算法以及各种基本操作（创建二叉树）定义为独立函数（注意函数接口的规定）。

3、 （2）采用菜单驱动方式调用各种功能。 （3）用测试数据测试程序的正确性，如下面的二叉树： （4）对同一棵二叉树，分别调用两种算法，单步跟综递归程序的执行过程并观察调用堆栈。 （5）分析算法的时间复杂度。提示：二叉链表可以采用数据类型定义：typedef struct node datatype data; /每个结点的数据域 struct node *lchild, *rchild; / 结点的左孩子指针域lchild，右孩子指针域rchildBinNode;五、实验报告1、写出每个算法的思想和关键代码。2、画出算法流程图。3、调试程序出现的问题及解决的方法。4、报告给出测试的结果并写出设计

4、体会。5、列表对比分析两种算法的时间复杂度、空间复杂度，阐明产生差异的原因。 6、根据实例归纳将递归算法改写为非递归算法的步骤。一：流程图 先序遍历流程图：开始遍历左子树T后退，遍历右子树判断T是否为空打印节点递归栈是否为空结束YNYY中序遍历流程图：开始遍历左子树打印节点遍历右子树判断T是否为空递归栈是否为空结束YNYN后序遍历流程图：开始遍历左子树T后退，遍历右子树判断T是否为空打印节点递归栈是否为空结束YNYY递归代码：#include<stdio.h>#include<stdlib.h>#include<malloc.h>typedef struct

5、 node char data;struct node *lchild,*rchild;BinNode;BinNode *createbn( )BinNode *q;struct node *m30;int j,i,x;printf("建立二叉树，输入结点对应的编号和值n");printf("i,x = ");scanf("%d,%c",&i,&x);while(i != 0 && x != 0) q=(BinNode*)malloc(sizeof(BinNode); q->data = x; q

6、->lchild = NULL; q->rchild = NULL; mi = q; if(i != 1) j = i / 2;if(i % 2 = 0) mj->lchild = q; else mj->rchild = q; printf("i,x = "); scanf("%d,%c",&i,&x);return m1; void BinNodePreorder(BinNode*bn)if(bn!=NULL) printf("%c ",bn->data);BinNodePreorde

7、r(bn->lchild);BinNodePreorder(bn->rchild);void BinNodeInorder(BinNode*bn) if(bn!=NULL) BinNodeInorder(bn->lchild);printf("%c ",bn->data);BinNodeInorder(bn->rchild);void BinNodePastorder(BinNode*bn)if(bn!=NULL) BinNodeInorder(bn->lchild);BinNodeInorder(bn->rchild);print

8、f("%c ",bn->data);void main() BinNode *bn;int select;while(select) printf("1. 建立二叉树 n");printf("2. 二叉树的前序遍历n");printf("3. 二叉树的中序遍历n");printf("4. 二叉树的后序遍历n");printf("0. 结束程序 n");scanf("%d",&select);switch(select)case 1:print

9、f("输入二叉树的结点值n");getchar();bn=createbn();printf("二叉树已建立完成!n");break;case 2:printf("该二叉树前序遍历序列为:");BinNodePreorder(bn);printf("n");break;case 3:printf("该二叉树中序遍历序列为:");BinNodeInorder(bn);printf("n");break;case 4:printf("该二叉树后序遍历序列为:"

10、);BinNodePastorder(bn);printf("n");break;case 0: ;实验结果：非递归代码：#include<stdio.h>#include<stdlib.h>#include<malloc.h>#define MAXNUM 100typedef struct nodeint data;struct node *lchild,*rchild;BinNode;BinNode *createbn( )BinNode *q;struct node *m30;int j,i,x;printf("输入结点对

11、应的编号和值n");printf("二叉树编号i= ");scanf("%d",&i);printf("n");printf("节点的值X= ");scanf("%d",&x);printf("n");while(i != 0 && x != 0) q=(BinNode*)malloc(sizeof(BinNode); q->data = x; q->lchild = NULL; q->rchild = NULL;

12、mi = q; if(i != 1) j = i / 2; if(i % 2 = 0) mj->lchild = q; else mj->rchild = q; printf("二叉树编号i= ");scanf("%d",&i);printf("n");printf("节点的值x= ");scanf("%d",&x);printf("n");return m1; void BinNodePreorder(BinNode*bn) BinNode*st

13、ackMAXNUM,*q;int top=1;stacktop=bn;while(top>=0) q=stacktop;top-;if(q!=NULL)printf("%d",q->data);top+;stacktop=q->rchild;top+;stacktop=q->lchild;void BinNodeInorder(BinNode*bn) BinNode*stackMAXNUM;int top=0;stacktop=bn;dowhile(stacktop!=NULL) top=top+1;stacktop=stacktop-1->l

14、child;top=top-1;if(top>=0) printf("%d",stacktop->data);stacktop=stacktop->rchild;while(top>=0);void BinNodePastorder(BinNode*bn) BinNode*stackMAXNUM;int tagMAXNUM;int top=0;BinNode*n;n=bn;dowhile(n!=NULL) top+;stacktop=n;tagtop=0;n=n->lchild;if(top>=0) n=stacktop;if(tagto

15、p=1)printf("%d",stacktop->data);top-;n=stacktop;if(top>0)if(tagtop!=1) n=n->rchild;tagtop=1;else n=NULL;while(top!=0);void main() BinNode *bn;int select;while(select)/printf("二叉树的建立和非递归遍历n");printf("1. 建立二叉树 n");printf("2. 二叉树的前序遍历n");printf("3. 二叉树的中序遍历n");printf("4. 二叉树的后序遍历n");printf("0. 结束程序 n");scanf("%d",&select);switch(select) case 1:printf("输入二叉树的结点值n");getchar();bn=createbn();printf("建立完成.n");break;case 2:printf("二叉树前序遍历