【2017年整理】数据结构实验三.doc

实验报告 学院（系）名称：计算机与通信工程学院 姓名 王宏昌 学号专业 计算机科学与技术 班级 2班 实验名称 实验三 二叉树操作 课程名称 数据结构 课程代码 实验时间 2016 实验地点 7-220 批改意见 成绩 教师签字： 实验目的和二叉树性质掌握二叉树二叉二叉树遍历算法实验要求1）问题描述：在主程序中提供下列菜单： 1…建立树 2…前序遍历树 3…中序(非递归)遍历树 4…后序遍历树 0…结束 2）实验要求： ① 定义下列过程： CreateTree(): 按从键盘输入的前序序列，创建树 PreOrderTree()：前序遍历树（递归） InOrderTree()：中序(非递归)遍历树 LaOrderTree(): 后序遍历树（递归） ② 每位同学在实验过程中要单步运行程序，跟踪二叉树的创建过程与前序遍历的递归过程。 2. 树的转换我们都知道用“兄弟”可以将一棵一般的树转换为二叉树请将树用这种方法转换为二叉树，并输出转换前和转换后树的。 1. #includestdio.h #includestdlib.h #define Max 100 typedef struct DoubTree { char data; struct DoubTree *lchild,*rchild; }DoubTree; DoubTree *CreateTree() { DoubTree *root; char s; root=(DoubTree * )malloc(sizeof(DoubTree)); if(!root) { printf(ERROR! NO SPACE! EXIT!); exit(1); } scanf(%c, s); if(s==#) root=NULL; else { root-data=s; root-lchild=CreateTree(); root-rchild=CreateTree(); } return root; } void PreOrderTree(DoubTree *root) { DoubTree *rot; rot=root; if(rot==NULL) return; printf(%c ,rot-data); PreOrderTree(rot-lchild); PreOrderTree(rot-rchild); } void InOrderTree(DoubTree *root) { DoubTree *rot, *stack[Max]; int top=0; rot=root; if(!rot) return; while(!(rot==NULLtop==0)) { while(rot) { if(topMax-1) { stack[top]=rot; top++; } else { printf(ERROR! FULL!); return; } rot=rot-lchild; } if(top=0) return; else { top--; rot=stack[top]; printf(%c ,stack[top]-data); rot=rot-rchild; } } } void LaOrderTree(DoubTree *root) { DoubTree *rot; rot=root; if(rot==NULL) return; LaOrderTree(rot-lchild); LaOrderTree(rot-rchild); printf(%c ,rot-data); } int main() { DoubTree *DTree; printf(Enter Tree`s Order: ); DTree=CreateTree(); printf(Recursion: PreOrder is: ); PreOrderTree(DTree); printf(\nNon-Recursion: InOrder is: ); InOrderTree(DTree); printf(\nRecursion: LaOrder is: ); LaOrderTree(DTree); return 0; } 第2页 共4页