题目。班级。姓名。
学号。完成日期。
目录。一、课程设计概述3
二、问题描述3
三、需求分析3
四、概要设计4
五、存储结构5
六、基本流程图6
七、详细设计6
八、调试分析17
九、运行结果。
十、参考文献。
本次数据结构课程设计完成二叉平衡树的创建、插入以及先序、中序、后序的输出操作。
实验内容：二叉平衡树的实现。
使用语言：c
编译环境：visual c++6.0
目的：1、通过不同类型的程序设计使学生学会分析数据如何组织，进一步掌握数据的几种不同的存储方式。2、 为专业课的深入学习和毕业设计打基础。
实现二叉平衡树的创建、插入、输出，并对二叉平衡进行平衡处理。
本程序在vc6.0环境用c语言编写，完成二叉平衡树的创建、插入以及先序、中序、后序的输出操作。
1、输入形式和输入值范围：
进入程序主界面后，根据用户需要的执行的工作，输入要执行工作的序号；
创建时只需要输入结点的关键字就会进行创建，如输入的关键字已经存在，则停止创建，关键字只可为整型变量；
如果已经创建过，则无法进行创建，则会进行中序、先序、后序遍历方式进行输出，然后询问用户是否重新创建；
插入结点时，需要输入结点关键字方会进行插入，如若插入关键字已存在，则停止插入；
如若插入结点造成失衡，则系统会自动进行平衡，并且告诉用户用的是何种平衡方式进行平衡，并按中序、先序、后序遍历方式进行输出；
如未先进行创建则无法进行插入；
2、输出的形式。
输出可以根据用户需要分别进行中序、先序、后序或者三者皆有的遍历方式进行输出；
如若未进行创建，则输出不存在二叉平衡树；
3、程序所能达到的功能：完成二叉平衡树的创建、插入、输出操作；
4、测试数据：
1） 按主界面提示输入要进行操作的行为的序号，如1.创建一棵二叉平衡树，然后输入各个结点的关键字，创建二叉平衡树；
2） 插入操作中如已完成创建，则输入插入的结点的关键字，如关键字存在，则会提示“插入失败，该结点已经存在”并询问是否继续插入，否则插入成功再询问是否继续插入；未完成创建，则提示“不存在二叉平衡树”并返回主界面；
3） 输出时会询问用户要按何种遍历方式，按用户爱好需求分别可进行中序、先序、后序或者三者皆有的遍历方式进行输出；
=adt=-
数据对象 d：d具有相同特性的数据元素的集合。各个数据元素均含有类型相同，可唯一标识数据元素的关键字。
数据关系 r：数据元素同属一个集合。
基本操作 p：
inordertr**erse(t);
初始条件：二叉树t存在。
操作结果：先序遍历输出二叉树。
inordertr**erse2(t)
初始条件：二叉树t存在。
操作结果：后序遍历输出二叉树。
inordertr**erse1(t)
初始条件：二叉树t存在。
操作结果：先序遍历输出二叉树。
phyz(t,j)
初始条件：二叉树t存在，二叉树指针j存在。
操作结果：查找失去平衡结点的位置并将地址返回l
right(&t,&j)
初始条件：二叉树t存在，二叉树指针j存在。
操作结果：二叉树t上与指针j有相等关键字结点进行右右式旋转。
left(&t, &j)
初始条件：二叉树t存在，二叉树指针j存在。
操作结果：二叉树t上与指针j有相等关键字结点进行左左式旋转。
right_l(&t, &j)
初始条件：二叉树t存在，二叉树指针j存在。
操作结果：二叉树t上与指针j有相等关键字结点进行右左式旋转。
left_r(&t, &j)
初始条件：二叉树t存在，二叉树指针j存在。
操作结果：二叉树t上与指针j有相等关键字结点进行左右式旋转。
sd(t)初始条件：二叉树t存在。
操作结果：返回二叉树t的深度。
pdphyz(t)
初始条件：二叉树t存在。
操作结果：若不平衡，则将不平衡点地址给j
searchbst(t, f, &p, key)
初始条件：二叉树t存在，key为关键字。
操作结果：若t中存在与key相等的元素，则指针p指向该数据元素结点，并返回true，否则指针p指向最后一个结点并返回false,指针f指向t的双亲。
insertbst(&t, key)
初始条件：二叉树t存在，key为待插入元素。
操作结果：若t中不存在与key相等元素，则插入key到t，并进行平衡。
sc(t)初始条件：二叉树t存在。
操作结果：按需要用不同遍历方法输出二叉树t
typedef struct bitnode
int data;//关键字。
int bf;//结点的平衡因子。
struct bitnode *lchild,*rchild;//左右子树指针。
bitnode,*bitree;//二叉平衡树。
#include<>
#include<>
#include<>
#include//调用清屏函数。
#define false 0
#define true 1
typedef struct bitnode
int data;//关键字。
int bf;//结点的平衡因子。
struct bitnode *lchild,*rchild;//左右子树指针。
bitnode,*bitree;//二叉平衡树。
void inordertr**erse(bitree t)//中序遍历输出二叉树。
if(t)//if
//inordertr**erse
void inordertr**erse2(bitree t)//后序遍历输出二叉树。
if(t)//if
//inordertr**erse2
void inordertr**erse1(bitree t)//先序遍历输出二叉树。
if(t)//if
//inordertr**erse1
bitree l全局二叉树指针。
void phyz(bitree t,bitree j) /平衡因子函数，查找失去平衡结点的位置的上一结点并将地址返回l
if(t)//if
//phyz
bitree right(bitree &bt,bitree &j) /右右式旋转函数。
l=null;
if(bt->data!=j->data)//判断破坏平衡点是否与根节点相同。
//ifif(j)
//ifif(l)//l为失去平衡点的结点。
//ifelse
return j;//else
//right
bitree left(bitree &bt,bitree &j) /左左式旋转函数。
数据结构课程设计报告
东莞理工学院城市学院。题目 二叉排序树 专业 计算机科学与技术 本 年级 2010级计算机科学与技术专业 1 班。个人姓名 何振江。指导教师 张娟老师 时间 2010至2011第二学期第18周 地点 实验楼615机房 东莞理工学院城市学院计算机与信息科学系制。2011年 6月。实习报告的内容。一 问...
数据结构课程设计报告
设计一个校园导游程序，为来访的客人提供信息查询服务。1 设计学校的校园平面图。选取若干个有代表性的景点抽象成一个无向带权图 无向网 以图中顶点表示校内各景点，边上的权值表示两景点之间的距离。2 存放景点代号 名称 简介等信息供用户查询。3 为来访客人提供图中任意景点相关信息的查询。4 为来访客人提供...
数据结构课程设计报告
河北科技大学。课程设计报告。学生姓名学号。专业班级。课程名称数据结构。学年学期 2 012 2 013学年第 2 学期指导教师 黄春茹。2 0 13年 6 月。课程设计成绩评定表。一 数据结构课程设计目标。二 问题描述。三 需求分析。四 概要设计。五 详细设计。六 软件说明书 给出软件如何使用，使用...