《数据结构》综合性实验平衡二叉排序树实验指导.doc

《数据结构》综合性、设计性实验指导 一、 实验题H 实现平衡二叉排序树的各种算法 二、 实验内容 用函数实现如下平衡二叉排序树算法： （1） 插入新结点 （2） 前序、中序、后序遍历二叉树（递归） （3） 前序、中序、后序遍历的非递归算法 （4） 层次遍历二叉树 （5） 在二叉树屮查找给定关键字（函数返冋值为成功1,失败0） （6） 交换各结点的左右子树 （7） 求二叉树的深度 （8） 叶子结点数 （9） 删除某结点 三、 实验目的 （1） 掌握递归算法 （2） 掌握堆栈算法 （3） 掌握队列算法 （4） 掌握树型查找 （5） 提高对树型结构的综合应用能力 四、 实验要求 （1） 独立完成实验内容 （2） 算法设计符合程序书写规范，耍求有注释、函数功能及参数说明 （3） 实验报告的封面见附表A （4） 实验报告参考附表《实验报告书写规范》书写 （5） 课程结束时要求在指定时间内上交实验的电子文档 华南农业大学信息学院 综合性、设计性实验 起止日期:2011秋 学院 软件学院 专业班级 学号 姓名 实 验 题 目 实现平衡二叉排序树的各种算法 自 我 评 价 项 目 算法设计 独立完成情况 算法熟练程度 测试 通过 成功 失败 独立 帮助 掌握 了解 不懂 插入新结点 7 前序、中序、后序遍历一叉树 （递归） 7 前序、屮序、后序遍历的非递 归算法 层次遍历二叉树 寸 7 在二叉树中查找给定关键字 V 交换各结点的左右子树 7 V 求二叉树的深度 7 V 叶子结点数 7 V 删除某结点 7 7 7 A 完成实验要求的全部功能并运行通过，算法有一定的新意，程序代码 符合书写规范，实验报告叙述清晰完整，有详尽的分析和总结。 B 完成实验要求的全部功能，程序代码符合书写规范，实验报告叙述 清晰完整。 c 完成实验要求的人部分功能，实验报告良好。 D 未按时完成实验，或者抄袭。 成 绩 教师签名: 实验报告：实现平衡二叉排序树的各种算法 班级： 姓名： 学号： 完成日期：2012年12月21日 一、分析题口要求 实验任务: 用函数实现如下平衡二叉排序树算法： （1） 插入新结点 （2） 前序、中序、后序遍历二义树（递归） （3） 前序、中序、后序遍历的非递归算法 （4） 层次遍历二叉树 （5） 在二叉树中查找给定关键字（函数返回值为成功1,失败0） （6） 交换各结点的左右子树 （7） 求二.义树的深度 （8） 叶子结点数 （9） 删除某结点 现在根据任务作为目标，进行分析： 1）各个函数命名，包含的参数，返回值类型 int THeight ( int THeight (Tree T) int Max (int a, int b ) Tree Min (Tree T) Tree Left Rot ate (Tree g) Tree Right Rot ate (Tree g) Tree L_RRotate (Tree g) Tree R_LRotate (Tree g ) Status insert (Tree T , ElemType e ) Status Delete ( Tree T, ElemType e ) 〃实现求树的高度的函数 〃实现求较人值的函数 〃实现查找最小元索的函数 〃实现树的向左旋转函数 〃实现树的向左旋转函数 〃实现树的向左旋转再向右旋转函数 〃实现树的向右旋转再向左旋转两数 〃实现在二叉树中插入新结点的函数 〃实现在二叉树中删除某结点的函数 Status CreatQueue（Queue Q） 〃实现队列的建立函数 Status LevelTraverse(Tree T) 〃实现层次遍历函数 int exchange （ Tree T） 〃实现交换左右子树结点 int traver （ Tree T ） 〃实现输出平衡二义树的各种遍历 Status print ( ElemType e ) 〃实现输!1| e 元素 Status PreOrderTraverse ( Tree T)〃递归前序遍历 Status InOrderTraverse (Tree T)〃递归屮序遍历 Status PostOrderTraverse (Tree T)〃递归后序遍历 Status initStack ( Stack s )//创建栈 Status push ( Stack s , Tree e )〃入栈操作 Status pop ( Stack s , Tree c )//出栈操作 Status stackEmpty( Stack s )〃判断栈是否为空栈 Status pre (Tree T )//非递归前序遍历 Status ino (Tree T)〃非递归中序遍历 Status post (Tree T )〃非递