二叉树操作实验报告.doc

PAGE PAGE 1 XX学院实验报告 课程名称 数据结构 实验名称 二叉树操作 系 计算机与信息科学系 班 级 专业班级 教育技术学 学号 姓 名 实验日期 2009-10-23 实验教室 多媒体实验室 指导教师 评阅意见 一、实验目的和要求：（本次实验所涉及并要求掌握的知识点） 二叉树是“数据结构”课程中的第一种非线性结构，通过本次实验帮助学生加深理解二叉树的特点及其存储表示的理解；帮助学生熟练掌握二叉树的基本操作在链式存储结构表示下的实现。 要求：每位同学独立完成。 二、实验环境：（本次实验所需要的平台和相关软件） 可以在Visual C++、Turboc2.0、WinTC191下编程实现均可 三、实验内容及步骤：（本次实验计划安排的实验内容和具体实现步骤） 编写实现以下操作的算法，并上机调试、运行： 1、实现对二叉树的先序、中序、后序遍历操作； 2、求二叉树中结点数； 3、求二叉树的深度； 4、求二叉树的叶结点数； 5、将二叉树中所有结点的左、右子树相互交换； 提示： 1、以二叉链表树表示二叉树，其类型定义如下： typedef struct BiTNode { ElemType data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; 2、结点元素类型可以自由选取； 3、一定注意，建立二叉链表树时结点数据输入顺序及结束符的添加。 四、实验过程和结果： 四、实验过程和结果：（记录实验过程和结果、以及所出现的问题和解决方法） 1．在windowsXP中打开 wintc 191 应用平台 2．编写一个菜单函数menu. 3．编写二叉树创建函数createbitree. 4. 编写二叉树先序遍历函数preordertraverse. 5．编写二叉树中序遍历函数inordertraverse. 6. 编写二叉树后序遍历函数postordertraverse. 7. 编写求二叉树结点数的函数lnodenum. 8. 编写求二叉树深度的函数height。 9. 编写求二叉树叶结点数的函数leafnum。 10.编写二叉树左右子树函数changelr. 11.编写主函数main，并在其中调用以上函数。 12.调试并运行程序！ 实验的结果如下： 1，建树成功： 五、实验总结和思考：（填写收获和体会，分析成功或失败的原因） 收获：只有通过不断练习，才能获取经验，避免下次犯同样的错误！ 成功和失败： 在实验过程中，遇到了一些细节性的问题，不好寻找，导致结果错误。 结果：找到了问题所在，发现了一些平时不曾注意的问题。 附件：（源代码） /* 说明 1、树的元素类型为字符形； 2、实现对二叉树的先序遍历操作； 3、实现对二叉树的中序遍历操作； 4、实现对二叉树的后序遍历操作； 5、求二叉树的深度； 6、求二叉树的叶结点数； 7、将二叉树中所有结点的左、右子树相互交换； */ #include stdio.h #include conio.h #define OVERFLOW -1 typedef char telemtype; typedef struct bitnode { telemtype data; struct bitnode *lchild,*rchild; }bitnode,*bitree; void createbitree(bitree *t) { telemtype ch; scanf(%c,ch); if(ch== ) *t=NULL; else { *t=(bitnode *)malloc(sizeof(bitnode)); if(!(*t)) exit(OVERFLOW); (*t)-data=ch; createbitree(((*t)-lchild)); createbitree(((*t)-rchild)); } return; } void preordertraverse(bitree t) { if(t) { printf(%c ,t-data); preordertraverse(t-lchild); preordertraverse(t-rchild); } } void inordertraverse(bitree t) { if(t) {