第6章实验-二叉树的建立与遍历-教案.doc

湖北第二师范学院计算机学院2012 至2013 学年 第1 学期数据结构课程教案课程编码：B0310008 课程类别：专业基础 学分：_3.5_总学时/周学时： 68 / 5 上课学时： 54 实验学时： 18 开课时间： 2012 年 9 月 4 日 第 1 周至第 17 周 授课年级、专业、班级：2011级、计算机科学与技术(嵌入式)、11计科4使用教材： 数据结构 C语言描述（第二版） 授课教师与职称：鲁静 讲师_ 周 次第 周时间年 月 日 第 节授课方式（请打）理论课 讨论课 实验课 习题课 其他课时安排2授课题目（教学章、节或主题）：第6章 树和二叉树。主题：二叉树的建立与遍历（实验课）。教学目的、要求（分掌握、熟悉、了解三个层次）：熟练掌握二叉树的二叉链表存储结构，以及二叉树建立的基本算法。熟悉二叉树前序、中序、后序遍历的递归与非递归算法。了解二叉树的层次遍历算法。教学重点及难点：重点： 二叉树前序、中序、后序遍历的递归与非递归算法。难点：二叉树遍历的递归算法。教 学 基 本 内 容方法及手段教学内容及板书纲要：仪器介绍： Windows XP操作系统、VC+6.0编译环境。第6章 树和二叉树实验一、二叉树的建立1. 实验目的了解二叉树的结构特点及有关概念，掌握二叉树建立的基本算法2. 实验内容依序输入元素值，以链表方式建立二叉树，并输出节点内容3. 实验要点及说明先依序输入元素值，并存入数组nodelist中，再用函数insert_node一一插入二叉树的节点建立成二叉树，节点的建立是将左子针指向左子树，右子针指向右子树。最后用print_btree输出节点内容。4. 二叉树结点的存储结构typedef struct bnodeint data ; / 结点数据类型struct bnode *lchild,* rchild; / 定义左、右孩子为指针型btree;5. 相关操作btree *insert_node(btree *root,int node) / 插入二叉树的节点btree *create_btree(int data ,int len) / 建立二叉树void print_btree(btree *root) / 打印二叉树二、二叉树的前序遍历1. 实验目的了解前序遍历二叉树的概念，掌握前序遍历二叉树的算法2. 实验内容以链表方式建立二叉树，并以前序遍历二叉树的方式输出节点内容3. 实验要点及说明先输入元素值建立二叉树，然后前序遍历该二叉树。前序遍历的规则是根结点最先遍历，其次左子树，最后右子树。4. 参考程序void preorder1(bitree *root) / 前序非递归遍历二叉树bitree *p,*s100; int top=0; / top为栈顶指针 p=root; while(p!=NULL)|(top0)while(p!=NULL)printf（%d,p-data）;只给学生定义存储结构，要求学生完成二叉树的建立。结合理论课知识，讲解程序，帮助学生理解递归遍历的算法。s+top=p; p=p-lchild; p=stop-; p=p-rchild; 三、二叉树的中序遍历1. 实验目的了解中序遍历二叉树的概念，掌握中序遍历二叉树的算法2. 实验内容以链表方式建立二叉树，并以中序遍历二叉树的方式输出节点内容3. 实验要点及说明先输入元素值建立成二叉树。中序遍历的规则是先遍历左子树，其次根结点，最后遍历右子树，本程序是递归算法。4. 参考程序void inorder(btree *root) / 中序递归遍历二叉树 if(root!=NULL)inorder(root-lchild);printf(%d,root-data);inorder(root-rchild);四、二叉树的后序遍历1. 实验目的了解后序遍历二叉树的概念，掌握后序遍历二叉树的算法。2. 实验内容以链表方式建立二叉树，并以后序遍历二叉树的方式输出节点内容。3. 实验要点及说明先输入元素值，建立成二叉树。后序遍历的规则是先遍历左子树，其次遍历右子树，最后访问根结点，本程序是递归算法。4. 参考程序void postorder(btree *root) / 后序递归遍历二叉树 if(root!=NULL)postorder(root-lchild);postorder(root-rchild);printf(%d,root-data);结合理论课知识，讲解程序，帮助学生理解递归遍历的算法。本程序要求学生模仿二叉树的前序、中序遍历算法，自行完成。实验后记：（通过提问，帮助同学回顾本次课的主要内容。）1 通过比较二叉树遍历的递归与非递归算法，深入理解递归的思想，思考为什么可以使用递归算法？2 灵活运用遍历算法实现二叉树的其它操作，如查找共同祖先，在符合条件的位置插入或者删除结点等等。作业、讨