数据结构综合性实验

华南农业大学信息学院

综合性、设计性实验

起止日期:2011秋 专业班级 软件工程R6 学号 201131000923 姓名 学院 实 验 题 目 软件学院 吴鑫潮 实现平衡二叉排序树的各种算法 项 目 算法设计 成功 失败 独立完成情况 独立 独立 独立 独立 独立 独立 独立 独立 独立 帮忙 帮助 算法熟练程度 掌握 掌握 掌握 掌握 掌握 掌握 掌握 掌握 掌握 了解 了解 不懂 测试通过 通过 通过 通过 通过 通过 通过 通过 通过 通过 插入新结点 前序、中序、后序遍历二叉树（递归） 前序、中序、后序遍历的非递归算法 层次遍历二叉树 在二叉树中查找给定关键字 交换各结点的左右子树 自 我 评 价 求二叉树的深度 叶子结点数 删除某结点  成功 成功 成功 成功 成功 成功 成功 成功 成功 A---------完成实验要求的全部功能并运行通过，算法有一定的新意，程序代码符合书写规范，实验报告叙述清晰完整，有详尽的分析和总结。  B---------完成实验要求的全部功能，程序代码符合书写规范，实验报告叙述 清晰完整。  C---------完成实验要求的大部分功能，实验报告良好。  D---------未按时完成实验，或者抄袭。 成绩 教师签名：杨秋妹

一、 分析题目要求

陈述说明程序设计的任务，强调的是程序要做什么并明确规定： 1） 各个函数命名，包含的参数，返回值类型

① int InitQueue(SqQueue &Q) 建立队列函数，int；

② int EnQueue(SqQueue &Q,BSTree e)队列插入元素函数，参数e，int； ③ int DeQueue(SqQueue &Q, BSTree &e)队列删除元素函数，参数e，int； ④ int EmptyQueue(SqQueue Q)判断队列是否为空函数，int； ⑤ int InitStack(SqStack &S)建立栈函数，int；

⑥ int Push(SqStack &S,BSTree e) 栈元素插入函数，参数e，int； ⑦ int Pop(SqStack &S,BSTree &e)栈元素删除函数，参数e，int； ⑧ int StackEmpty(SqStack S) 判断栈是否为空函数，int； ⑨ int StackLength(SqStack S) 栈长度函数，int； ⑩ void R_Rotate(BSTree &p)树的右旋处理函数，void； 11 void L_Rotate(BSTree &p)树的左旋处理函数，void； 12 void LeftBalance(BSTree &T)树的左平衡处理函数，void； 13 void RightBalance(BSTree &T)树的右平衡处理函数，void；

14 int InsertAVL(BSTree &T,ElemType e,int &taller)平衡树的节点插入函数，e，taller，int；

15 int InsertAVLD(BSTree &T)要输入的元素函数，int； 16 int InitDSTable(BSTree &DT)构建动态查找表函数，int； 17 int Visit(ElemType e)输出函数，void；

18 Int PreOrderTraverse(BSTree &T,int (*Visit)(ElemType ch))递归先序遍历函数，ch，int；

19 Int InOrderTraverse(BSTree &T,int (*Visit)(ElemType ch))递归中序遍历函数， ch，int；

20 Int PostOrderTraverse(BSTree &T,int (*Visit)(ElemType ch))递归后序遍历函数，ch，int；

21 int PreOrderTraverse1(BSTree &T,int (*Visit)(ElemType ch))非递归先序遍历函数，ch，int；

22 int InOrderTraverse1(BSTree &T,int (*Visit)(ElemType ch))非递归中序遍历函数， ch，int；

23 int PostOrderTraverse1(BSTree &T,int (*Visit)(ElemType ch))飞递归后序遍历函数，ch，int；

24 int cengciOrderTraverse(BSTree &T)层次遍历函数，int； 25 int exchange(BSTree T)左右子树交换函数，int； 26 int Depth (BSTree T )二叉树的深度函数，int； 27 int mathBiTree(BSTree T)二叉树的节点函数，int；

28 int Search(BSTree T,ElemType ch)二叉树的查找函数，ch，int；

29 int DeleteAVL(BSTree &T, int key, bool &shorter)二叉树的节点删除函数，key，shorter；

30 int main()主函数 ，int；

2） 输入的形式和输入值的范围

输入的形式都死整型int；输入的范围是非负数； 3） 输出的形式

输出格式都是文字加数据，便于使用者操作；

4） 程序所能达到的功能

利用switch处理，实现以下各个功能： （1） 插入新结点

（2） 前序、中序、后序遍历二叉树 （递归） （3） 前序、中序、后序遍历的非递归算法 （4） 层次遍历二叉树

（5） 在二叉树中查找给定关键字(函数返回值为成功1,失败0) （6） 交换各结点的左右子树 （7） 求二叉树的深度 （8） 叶子结点数

（9） 删除某结点

二、 解题思路

对于要实现的各个操作，分别说明其应如何求解，用伪码形式描述其求解过程，求解过程中用到的数据结构。

（1） 插入新结点 调用int InsertAVL(BSTree &T,ElemType e,int &taller)函数，在通过

void R_Rotate(BSTree &p)树的右旋处理函数； void L_Rotate(BSTree &p)树的左旋处理函数；

void LeftBalance(BSTree &T)树的左平衡处理函数；

void RightBalance(BSTree &T)树的右平衡处理函数；找出要插入的位

（2） 前序、中序、后序遍历二叉树 （递归） 先序： T

if(PostOrderTraverse(T->lchild, Visit))

if(PostOrderTraverse(T->rchild, Visit))

if(Visit(T->data))

子，将元素插入到二叉树中。

中序： T

if(InOrderTraverse(T->lchild,Visit))

if(Visit(T->data))

if(InOrderTraverse(T->rchild,Visit))

后序：T

if(PostOrderTraverse(T->lchild, Visit))

if(PostOrderTraverse(T->rchild, Visit))

if(Visit(T->data))

（3） 前序、中序、后序遍历的非递归算法 先序：SqStack S;

BSTree p=T; InitStack(S); Visit(p->data );

Push(S,p->rchild ); p=p->lchild;

依次将根节点打印，右子树进栈，左子树乡下传； 传完后在将栈元素一次取出来 Pop(S,p);在进行上诉操作直到栈为空。 中序：Push(S,p);

p=p->lchild;

根节点进栈，左子树下传；

Pop(S,p); if(!Visit(p->data ))

return ERROR; p=p->rchild;

元素退栈，打印节点，节点右传；循环上面操作直到栈空。

后序：SqStack S1,S2;

Pop(S1,p); Push(S2,p); if(p->lchild) Push(S1,p->lchild); if(p->rchild) Push(S1,p->rchild);

利用栈的先入后出将树的节点存入S1，并按要求的顺序存到

S2中； Pop(S2,p);

printf(\"%d \取出栈S2中的元素，打印。

（4） 层次遍历二叉树

（5） 在二叉树中查找给定关键字(函数返回值为成功1,失败0)

if(ch>T->data) Search(T->rchild,ch);

SqQueue Q; BSTree p=T; DeQueue(Q,p); if(p->lchild ) { }

if(p->rchild ) {

Visit(p->rchild ->data); EnQueue(Q,p->rchild ); Visit(p->lchild->data); EnQueue(Q,p->lchild );

}利用队列将树顺序存储，顺序打印。

else if(chdata) Search(T->lchild,ch); else if(T->data==ch) p=T->lchild; T->lchild=T->rchild ; T->rchild=p; if(T->lchild) exchange(T->lchild ); if(T->rchild) exchange(T->rchild);

depthLeft = Depth( T->lchild ); depthRight= Depth( T->rchild );

depthval = 1 + (depthLeft > depthRight ?depthLeft : depthRight); a=0;

else if(T->lchild==NULL&&T->rchild ==NULL) a=a+1; else

a=mathBiTree(T->lchild )+mathBiTree(T->rchild ); 先找出要删除的节点位子； 判断处理，重新平衡二叉树。

（6） 交换各结点的左右子树

（7） 求二叉树的深度

（8） 叶子结点数

（9） 删除某结点

三、 调试分析

1） 调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析

对平衡二叉树的删除的算法设计程序存在很大问题。删除节点后需要

对新的排序树平衡化，改变节点的信息，使之形成一棵新的平衡二叉树；主函数中的实参和子函数中的实参相等，造成调用该子函数时，虽然没有错误，但其功能不能正确的实现。改变该变量后程序成功实现各种功能 ；一些逻辑逻辑运算符书写不正确，造成实现的功能不正确或程序死循环。

2） 使用的测试数据（要求多组）

3） 算法的效率分析和改进设想

由于二叉树的存储结构采用的是链式存储，每个二叉树的结点至少包 括三个域：数据域和左、右指针域。各种操作的算法时间复杂度基本 比较合理。大多数操作时间复杂度都为O(n)，n为平衡二叉树中结点的个数。

前，平衡二叉树中已有n个关键字，在插入时，要找到插入e的合适位置，需要n次对函数InsertAVL的递归调用，所以时间复杂度为

对插入算法InsertAVL时间复杂度的分析如下：设在插入关键字e之

O(n)；每次InsertAVL算法结束后，都有对二叉树的左处理或右处理，时间复杂度为O(n)；所以整个插入算法的时间复杂度为O(n)。 对删除算法DeleteAVL时间复杂度的分析和插入算法的分析类似，其时间复杂度也为O(n)。

4） 经验和体会

通过本次实验，我深深的明白了过去打过的代码的重要性，想本次的

四、 附录

带注释的源程序。

注意：1.只交电子版

2.每个同学的资料存放在以学号姓名为文件夹名的目录下，有学习委员收齐后统一交 给任课教师。

实验中计算树的深度，交换左右子树，节点数，遍历等功能都是之前自己就经验实现过的，如果之前的代码有保留的话就可以直接引用了；此外加深了我对平衡二叉树的理解，及对于二叉树的节点删除的理解，不仅仅是删除节点，更重要的是删除后如何确保树的平衡；最重要的是加强了我对代码的调试能力。