数据结构课程设计报告

沈阳航空航天大学。

课程设计报告。

课程设计名称：数据结构课程设计。

课程设计题目：二叉排序树的平衡化。

院（系）：计算机学院。

专业：网络工程。

班级：网络1301班。

学号： 2013040102003

姓名：指导教师：

说明：结论（优秀、良好、中等、及格、不及格）作为相关教环节考核必要依据；格式不符合要求；数据不实，不予通过。报告和电子数据必须作为实验现象重复的关键依据。

本人声明：所呈交的报告（含电子版及数据文件）是我个人在导师指导下独立进行设计工作及取得的研究结果。尽我所知，除了文中特别加以标注或致谢中所罗列的内容以外，报告中不包含其他人己经发表或撰写过的研究结果，也不包含其它教育机构使用过的材料。

与我一同工作的同学对本研究所做的任何贡献均己在报告中做了明确的说明并表示了谢意。报告资料及实验数据若有不实之处，本人愿意接受本教学环节“不及格”和“重修或重做”的评分结论并承担相关一切后果。

本人签名日期：年月日。

目录。沈阳航空航天大学 i

学术诚信声明 i

1 题目介绍和功能要求 1

1.1 题目和功能介绍 1

2 概要设计 2

2.1 功能模块图 2

2.2 模块功能说明 2

2.2.1 树的存储 2

2.2.2 中序遍历 3

2.2.3 平衡二叉树的插入 3

2.2.4 左平衡旋转处理 3

2.2.5 右平衡旋转处理 3

3 详细设计 4

3.1 主程序框图 4

3.2 树的存储结构 5

3.3 算法描述 5

4 程序运行结果 11

附录（关键部分程序清单） 14

从键盘输入一个整数无序序列，根据该整数序列构造一颗平衡的二叉排序树。

要求每输入一个整数就将其插入二叉树中进行排序并进行旋转平衡处理使其二叉树平衡，平衡旋转处理后要记录其结点的数据及平衡因子。注意在构造二叉排序树时，要按照整数序列中整数的输入顺序插入结点。

整个序列输入后要将建立的平衡排序二叉树的结果输出，其输出形式是要将结果利用中序遍历算法进行中序遍历将每个节点的数值及平衡因子输出。

示例：输入序列：25,12,34,6,17

输出结果：6，0

图2.1 功能模块图。

排序二叉树与普通二叉树存储结构基本相同，分别为整型类型的数据域（data），指针类型的左、右孩子指针（lchild,rchild）和整型类型的平衡因子（bf）。

中序遍历运用递归的方式，定义树为t，先中序遍历树t的左孩子，在输出t的结点数据及平衡因子，再中序遍历树t的右孩子即可。

同样运用递归的方式，定义树为t，插入整型节点e，定义布尔型taller来检测树是否长高了。

1）若树t为空，则插入新节点，其左右孩子均为空，平衡因子bf为等高，树长高taller为false，返回值为1；

2）若树中存在与e相同的关键字节点，则返回0不插入；

3）若e比t节点的数值小，则递归搜索t的左子树，递归后根据不同的平衡情况调用左平衡旋转处理函数进行调整并修改节点的平衡因子bf，返回值为1；

4）若e比t节点的数值大，则递归搜索t的右子树，递归后根据不同的平衡情况调用右平衡旋转处理函数进行调整并修改节点的平衡因子bf，返回值为1。

检查树t的左子树的平衡度，根据平衡度不同的情况分别作出相应的平衡处理并修改平衡因子。

检查树t的右子树的平衡度，根据平衡度不同的情况分别作出相应的平衡处理并修改平衡因子。

图3.1 主程序框图。

1.在平衡的二叉排序树t上插入一个新的数据元素e的递归算法可描述如下：

1）若t为空树，则插入一个新的数据元素为e的新结点作为t的根结点，树的深度增1；

2）若e的关键字和t的根结点的关键字相等，则不进行插入；

3）若e的关键字小于t的根结点的关键字，而且在t的左子树中不存在和e有相同关键字的结点，则将e插入在t的左子树上，并且当插入之后的左子树深度增加（+1）时，分别就下列不同情况处理之：

t的根结点的平衡因子为-1：则将根结点的平衡因子更改为0，t的深度不变；

t的根结点的平衡因子为0：则将根结点的平衡因子更改为1，t的深度增1；

t的根结点的平衡因子为1：若t的左子树根结点的平衡后果因子为1：若t是左子树根结点的平衡因子为1，则需进行单向右旋平衡处理，并且在右旋处理之后，将根结点和其右子树根结点的平衡因子更改为0，树的深度不变；

若t的左子树根结点的平衡因子为-1，则需进行先向左、后向右的双向旋转平衡处理，并且在旋转处理之后，修改根结点和其左、右子树根结点的平衡因子，树的深度不变；

4）若e的关键字大于t的根结点的关键字，而且在t的右子树中不存在和e有相同关键字的结点，则将e插入在t的右子树上，并且当插入之后的右子树深度增加（+1）时，分别就不同情况处理之。其处理操作和（3）中所述相对称。

图3.2 插入新元素。

2.中序遍历二叉树的操作定义为：

若二叉树为空，则空操作；否则。

中序遍历左子树；

访问跟结点并输出；

中序遍历右子树。

图3.3 中序遍历。

3.旋转平衡处理。

1）单向右旋平衡处理：由于在*a的左子树根结点的左子树上插入结点，*a的平衡因子由1增至2，致使以*a为根的子树失去平衡，则需进行一次向右的顺时针旋转操作。

2）单向左旋平衡处理：由于在*a的右子树根结点的右子树上插入结点，*a的平衡因子由-1增至-2，致使以*a为根的子树失去平衡，则需进行一次向左的逆时针旋转操作。

3）双向旋转（先左后右）平衡处理：由于在*a的左子树根结点的右子树上插入结点，*a的平衡因子由1增至2，致使以*a为根结点的子树失去平衡，则需要进行两次旋转（先左旋后右旋）操作。

4）双向旋转（先右后左）平衡处理：由于在*a的右子树根结点的左子树上插入结点，*a的平衡因子由-1增至-2，致使以*a为根结点的子树失去平衡，则需要进行两次旋转（先右旋后左旋）操作。

由于左旋和右旋方法相同，只是方向相反，因此只列出左旋的流程图）

图3.4 左旋转处理。

图3.5 左平衡旋转处理。

1.第一组序列测试：23,52,13,4,37,48

输入：23 52 13 4 37 48 0

生成的平衡二叉排序树为：

中序遍历结果为：4,13,23,37,48,52

测试结果为：

图4.1 运行结果（1）

2.第二组序列测试：13,24,37,13,90,53

输入：13 24 37 13 90 53 0

生成的平衡二叉排序树为：

中序遍历结果为：13,24,37,53,90

测试结果为：

图4.2 运行结果（2）

参考文献。1] 高富平，张楚 . 电子商务法［m］. 北京：北京大学出版社，2002

2] huang s c，huang y m，shieh s m．vibration and stability of a rotating shaft containing a transerse crack［j］, j sound and vibration，1993，162（3）：387－401．

4] 严蔚敏，吴伟民。数据结构（c语言版）.北京：清华大学出版社，2007

#include ""

#include<>

#include ""

#define overflow

#define ok 1

#define error 0

#define null 0

#define true 1

#define false 0

#define lh +1 //左高。

#define eh 0 //等高。

#define rh -1 //右高

#define max 1000

typedef struct bstnode{

int data;

int bf结点的平衡因子。

struct bstnode *lchild,*rchild;

bstnode,*bstree;

int r_rotate(bstree&p){

//对以*p为根的二叉排序树作右旋转处理。

bstree lc;

lc=p->lchild;

p->lchild=lc->rchild;

lc->rchild=p;

p=lc;return 0;

int l_rotate(bstree&p){

//对以*p为根的二叉排序树作左旋转处理。

数据结构课程设计报告

数据结构课程设计报告

数据结构课程设计报告

数据结构课程设计报告

其他用户还读了