编者按：本文主要从大型作业（课程设计）题目和内容；程序中所采用的数据结构及存储结构的说明；算法的设计思想；平衡二叉树与未平衡化的二叉树查找效率比较；时间复杂度的分析；心得和总结，对数据结构作业报告进行讲述。其中，主要包括：用二叉链表作存储结构、用顺序表（一维数组）作存储结构、二插链表作存储结构、对于未平衡化的二叉树、查找函数最坏的情况是要找的点正好是二叉树的最深的叶子结点，此时时间复杂度＝O（n）、删除函数不采用递归手法，而是采用重新建立一颗不含要删结点的二插排序树、只有真正理解这样定义数据类型的好处，才能用好这样一种数据结构。了解典型数据结构的性质是非常有用的，它往往是编写程序的关键，具体材料请详见：

一、大型作业（课程设计）题目和内容

1、用二叉链表作存储结构

（1）以回车（‘\n’）为输入结束标志，输入数列L，生成二叉排序树T；

（2）对二叉排序树T作中序遍历,输出结果；

（3）计算二叉排序树T的平均查找长度，输出结果；

（4）输入元素x，查找二叉排序树T，如果存在含x的结点，则删除该结点，并作中序遍历(执行操作2)；否则输出信息“无结点x”；

（5）判断二叉排序树T是否为平衡二叉树，输出信息“OK!”/“NO!”;

*（6）再用数列L，生成平衡二叉排序树BT：当插入新元素后，发现当前二叉排序树BT不是平衡二叉排序树，则立即将它转换成新的平衡二叉排序树BT；

*（7）计算平衡二叉排序树BT的平均查找长度，输出结果。

2、用顺序表（一维数组）作存储结构

（1）以回车（‘\n’）为输入结束标志，输入数列L，生成二叉排序树T；

（2）对二叉排序树T作中序遍历,输出结果；

（3）计算二叉排序树T的平均查找长度，输出结果；

（4）输入元素x，查找二叉排序树T，如果存在含x的结点，则删除该结点，并作中序遍历(执行操作2)；否则输出信息“无结点x”；

（5）判断二叉排序树T是否为平衡二叉树，输出信息“OK!”/“NO!”。

二、程序中所采用的数据结构及存储结构的说明

程序中的数据采用“树形结构”作为其数据结构。具体的，我采用的是“二叉排序树”。

二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：（1）若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；（2）若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；（3）它的左右子树也分别为二叉排序树。

程序中分别采用了“二插链表”和“一维数组”作为其存储结构。

二插链表存储结构中二插树的结点由一个数据元素和分别指向其左、右子树的两个分支构成。如：我的程序中采用的结构是：

typedefstructTnode{

intdata;/*数据元素*/

structTnode*lchild,*rchild；/*左右指针*/

}*node,BSTnode;

一维数组顺序表存储结构是用一组地址连续的存储单元依次自上而下、自左而右存储完全二插树上的结点元素，即将完全二叉树上编号为i的结点元素存储在如上定义的一维数组中下标为i-1的分量中。利用顺序表作为存储结构：

typedefstruct{

int*data;/*一维数组基址*/

intlenth;/*一维数组的长度*/

}BST;

一维数组存储结构中结点i的父母亲为|_i/2_|,左孩子为2i，右孩子为2i+1.

三、算法的设计思想

a)二插链表作存储结构：

建立二插排序树采用边查找边插入的方式。查找函数采用递归的方式进行查找。如果查找成功则不应再插入原树，否则返回当前结点的上一个结点。然后利用插入函数将该元素插入原树。

对二叉树进行中序遍历采用递归函数的方式。在根结点不为空的情况下，先访问左子树，再访问根结点，最后访问右子树。

计算二插排序树的平均查找长度时，仍采用类似中序遍历的递归方式，用s记录总查找长度，j记录每个结点的查找长度，s置初值为0，采用累加的方式最终得到总查找长度s。平均查找长度就等于s/i(i为树中结点的总个数)。

删除结点函数，采用边查找边删除的方式。如果没有查找到，则不对树做任何的修改；如果查找到结点，则分四种情况分别进行讨论：1、该结点左右子树均为空；2、该结点仅左子树为空；3、该结点仅右子树为空；4、该结点左右子树均不为空。

判断二插排序树是否为平衡二叉树的函数，也是采用递归函数的方式，分别判定以树中每个结点为根结点的子树是否为平衡二叉树。只要有一个子树不为平衡二叉树，则该树便不是平衡二叉树。

b)一维数组作存储结构：

建立二插排序树，首先用一个一维数组记录下读入的数据，然后再用边查找边插入的方式将数据一一对应放在完全二叉树相应的位置，为空的树结点用“0”补齐。

中序遍历二叉树也采用递归函数的方式，先访问左子树2i,然后访问根结点i,最后访问右子树2i+1.先向左走到底再层层返回，直至所有的结点都被访问完毕。

计算二插排序树的平均查找长度时，采用类似中序遍历的递归方式，用s记录总查找长度，j记录每个结点的查找长度，s置初值为0，采用累加的方式最终得到总查找长度s。平均查找长度就等于s/i(i为树中结点的总个数)。

删除二插排序树中某个结点，采用边查找边插入的方式，类似重新建立一个一维数组作为存储新树的空间。将原数组中的数据一个一个的插入树中，若遇到需要删除的结点则不执行插入操作。

判断二插排序树是否为平衡二叉树的函数，也是采用递归函数的方式，分别判定以树中每个结点为根结点的子树是否为平衡二叉树。只要有一个子树不为平衡二叉树，则该树便不是平衡二叉树。

四、平衡二叉树与未平衡化的二叉树查找效率比较

(1)对于未平衡化的二叉树：

当先后插入的关键字有序时，构成的二插排序树蜕变为单支树。树的深度为n,其平均查找长度为（n+1）/2.这是最差的情况。这种情况下比较关键字的最大次数为n次。

(2)最好的情况是：

建成的树是一棵平衡二叉树。在这种情况下，二插排序树的平均查找长度和log2(n)成正比。比较关键字的最大次数为：0.5logψ（5）＋logψ(n+1)-2次（其中ψ＝（1＋根号5）/2）。

(3)那么，平均情况下分析：

假设在含有n(n>=1)个关键字的序列中，i个关键字小于第一个关键字，n-i-1个关键字大于第一个关键字，则由此构造而得的二插排序树在n个记录的查找概率相等的情况下，其平均查找长度为

：P(n,i)=[1+i*(P(i)+1)+(n-i-1)(P(n-i-1)+1)]/n

其中P(i)为含有i个结点的二插排序树的平均查找长度，则P(i)+1为查找左子树中每个关键字时所用比较次数的平均值，P（n-i-1）+1为查找右子树中每个关键字时所用比较次数的平均值。又假设表中n个关键字的排列是“随机”的，即任一个关键字在序列中将是第1个，或第2个，…，或第n个的概率相同，则可对上式从i等于0至n-1取平均值。最终会推导出：

当n>=2时，P（n）<=2（1＋1/n）ln(n)

由此可见，在随机的情况下，二插排序树的平均查找长度和log（n）是等数量级的。

五、时间复杂度的分析

说明：对时间复杂度的分析，均指在最坏情况下的时间复杂度。

二插链表存储结构中：

（1）查找函数最坏的情况是要找的点正好是二叉树的最深的叶子结点，此时时间复杂度＝O（n）。

（2）插入函数最坏的情况是要插入的点正是二叉树的最深的那一支的叶子结点，此时时间复杂度＝

O（n）。

（3）中序遍历函数，求平均查找长度的函数，删除函数以及判断二插排序树是否为平衡二叉树的函数，其时间复杂度均与以上情况类似，等于O（n）。

一维数组顺序表存储结构中：

（1）插入函数最坏的情况是要插入的点正是二叉树的最深的那一支的叶子结点，此时时间复杂度＝O（n）。

（2）创建函数最坏的情况就是调用插入函数时插入函数遇到最坏的情况。因此，创建函数的时间复杂度也等于O（n）。

（3）中序遍历函数，求平均查找长度的函数，查找函数，以及判断二插排序树是否为平衡二叉树的函数，其时间复杂度均与以上情况类似，等于O（n）。

（4）删除函数不采用递归手法，而是采用重新建立一颗不含要删结点的二插排序树。其时间复杂度＝O（n）。

六、心得和总结

这次暑假的课程设计作业我选择做数据结构是出于我对用高级语言编程的极大兴趣。通过这次实验我也着实又感受了一次编程的乐趣，从中也学到了不少知识。

虽然都说“程序＝数据结构＋算法”，但我在学习运用数据结构编程之前，并没能深刻体会到这一点，直到这次课设实践。

我感受最深的一点是：以前用C编程，只是注重如何编写函数能够完成所需要的功能，似乎没有明确的战术，只是凭单纯的意识和简单的语句来堆砌出一段程序。感觉有点像张飞打仗，有勇无谋，只要能完成任务就行。但现在编程感觉完全不同了。在编写一个程序之前，自己能够综合考虑各种因素，首先选取自己需要的数据结构，是树还是图或是别的什么？然后选定一种或几种存储结构来具体的决定后面的函数的主要风格。最后在编写每一个函数之前，可以仔细斟酌比对，挑选出最适合当前状况的算法。这样，即使在完整的程序还没有写出来之前，自己心中已经有了明确的原图了。这样无形中就提高了自己编写的程序的质量。

另外，我还体会到深刻理解数据结构的重要性。只有真正理解这样定义数据类型的好处，才能用好这样一种数据结构。了解典型数据结构的性质是非常有用的，它往往是编写程序的关键。

我以前对递归算法一直很害怕，总是看不明白究竟这递归是怎么进行的。在这次实验中我终于克服了这一障碍，一次次单步执行书中递归函数的例子，并一遍遍在心中自己默默的走，终于弄明白了，真的是功夫不负有心人啊！同时我还根据自己的理解写出了类似的递归函数实现了新的功能，真是受益良多啊！

在这次实验中，我对参数的调用也进行了很多种尝试，已经能够相对准确的选择合适的参数形式来实现函数之间的数据传输交互了。

这次实验中我也出现过一些比较严重的错误。在用一维数组顺序表结构编写程序时我错误的运用静态链表来实现函数功能。这是我对基本概念理解的模糊不清造成的。我原以为只要采用一维数组作为存储结构它就一定也是顺序表结构，而实质上这根本是两个不相干的概念。后来在同学的指点下我意识到自己的错误。不过收获也很不少。至少我又练习了运用静态链表来实现同样的功能，同时我也发现两者在很多函数上是互通的，只需稍作修改即可移植。

总之，我会继续我的兴趣编写程序的，相信在越来越多的尝试之后，自己会不断进步不断提高的。