数据结构二叉排序树的实现__(用顺序和二叉链表作存储结构_)课程设计.doc

1、课程名称：软件综合算法 一、设计题目1、 题目：二叉排序树的实现(用顺序和二叉链表作存储结构)2、要求（功能）： 1)以回车(n)为输入结束标志,输入数列L，生成一棵二叉排序树T； 2)对二叉排序树T作中序遍历，输出结果； 3)输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历(执行操作2)；否则输出信息“无x”；二、 需求分析 建立排序二叉树，主要是建立节点来存储输入的数据，需要建立函数来创造排序二叉树。该题目包括三方面的内容：一个是二叉排序树的建立，二是二叉树的中序遍历，三是二叉树元素的查找并删除。 三、 数据结构设计 在写算法之前，应对数据结构进行设计。本题主要会

2、用到指针变量，插入节点函数和建立二叉树，以及中序遍历函数，还有一些输入输出语句。四、算法设计算法设计思想二叉链表作存储结构： 建立二叉排序树采用边查找边插入的方式。查找函数采用递归的方式进行查找。如果查找成功则不应再插入原树，否则返回当前结点的上一个结点。然后利用插入函数将该元素插入原树。对二叉树进行中序遍历采用递归函数的方式。在根结点不为空的情况下，先访问左子树，再访问根结点，最后访问右子树。 删除结点函数，采用边查找边删除的方式。如果没有查找到，则不对树做任何的修改；如果查找到结点，则分四种情况分别进行讨论：1、该结点左右子树均为空；2、该结点仅左子树为空；3、该结点仅右子树为空；4、该结

3、点左右子树均不为空。在进行算法设计时，应将题目分为五个函数模块：1、中序遍历，符合升序输出void inorder(node *&root) if(root!=NULL) inorder(root-left); coutdataright); 2、在查找树中插入元素void insert(node *&ptr,int item) if(ptr=NULL) ptr=new node(item); else if(itemdata) insert(ptr-left,item); else insert(ptr-right,item); 3、在查找树中查找元素 node *find(node *&p

4、tr,int item) if(ptr=NULL) return NULL; if(ptr-data=item) return ptr; else if(itemdata) find(ptr-left,item); else find(ptr-right,item); 4、在查找树中查找肯定存在的元素,并返回其引用node *&findy(node *&ptr,int item) if(ptr-data=item) return ptr; else if(itemdata) findy(ptr-left,item); else findy(ptr-right,item); node* rl()

5、return left; node* rr()return right;5、删除指定值为所在结点void dele(node *&ptr) if(ptr-rl()=NULL&ptr-rr()=NULL) ptr=NULL; else if(ptr-rr()=NULL) ptr=ptr-rl(); else ptr=ptr-rr(); private: int data; node *left; node *right; ;五、 程序实现1、 调入文件#include 2、 主函数int main() int t,i=0,j; cout endl; cout1.二叉排序树T的输入:endl; c

6、outt; cout输入tj; node *x=new node(j); for(;ij; x-insert(x,j); coutinorder(x); /作中序遍历 coutn; cout2.二叉排序树T的元素查找和删除:endl; coutn输入操作(当输入-1时程序结束):j; while(j!=-1) node *t=x-find(x,j); /定位结点 if(t!=NULL) node *&y=x-findy(x,j); x-dele(y); coutinorder(x); else cout无j; coutn输入操作(当输入-1时程序结束):j; return 0;六、程序编码#i

7、nclude using namespace std;class nodepublic:node(int i):data(i),left(NULL),right(NULL) void inorder(node *&root) /中序遍历，符合升序输出 if(root!=NULL) inorder(root-left); coutdataright); void insert(node *&ptr,int item) /在查找树中插入元素 if(ptr=NULL) ptr=new node(item); else if(itemdata) insert(ptr-left,item); else

8、insert(ptr-right,item); node *find(node *&ptr,int item) /在查找树中查找元素,找到返回所在结点指针，找不到返回空指针。 if(ptr=NULL) return NULL; if(ptr-data=item) return ptr; else if(itemdata) find(ptr-left,item); else find(ptr-right,item); node *&findy(node *&ptr,int item) /在查找树中查找肯定存在的元素,并返回其引用 if(ptr-data=item) return ptr; els

9、e if(itemdata) findy(ptr-left,item); else findy(ptr-right,item); node* rl()return left; node* rr()return right; void dele(node *&ptr) /删除值为item所在结点 if(ptr-rl()=NULL&ptr-rr()=NULL) ptr=NULL; else if(ptr-rr()=NULL) ptr=ptr-rl(); else ptr=ptr-rr(); private: int data; node *left; /左孩子结点 node *right; /右孩

10、子结点;int main() int t,i=0,j; cout 10计科一班 李敬芳（100212116）endl; cout1.二叉排序树T的输入:endl; coutt; cout输入tj; node *x=new node(j); for(;ij; x-insert(x,j); coutinorder(x); /作中序遍历 coutn; cout2.二叉排序树T的元素查找和删除:endl; coutn输入操作(当输入-1时程序结束):j; while(j!=-1) node *t=x-find(x,j); /定位结点 if(t!=NULL) node *&y=x-findy(x,j);

11、 x-dele(y); coutinorder(x); else cout无j; coutn输入操作(当输入-1时程序结束):j; return 0;七、运行结果输入节点数输入二叉树数，并输出中序遍历八、时间复杂度分析1、查找函数最坏的情况是要找的点正好是二叉树的最深的叶子结点，此时时间复杂度O（n）。2、插入函数最坏的情况是要插入的点正是二叉树的最深的那一支的叶子结点，此时时间复杂度O（n）。3、中序遍历函数，删除函数，其时间复杂度均与以上情况类似，等于 O（n）。注：对时间复杂度的分析，均指在最坏情况下的时间复杂度。九、心得与体会 这次数据结构的课程设计作业在第15周作业布置下来的，但紧接

12、着是我们的英语四级考试，数据结构、Java等一系列考试，既要做这次的课程设计，也要认真准备考试，因此时间非常紧。但基于我对编程的极大兴趣，我对这次的课程设计非常重视。通过这次实验我也着实又感受了一次编程的乐趣，从中也学到了不少知识。 虽然都说“程序数据结构算法”，但我在学习运用数据结构编程之前，并没能深刻体会到这一点，直到这次课设实践。 我感受最深的一点是：以前用C、C+编程，只是注重如何编写函数能够完成所需要的功能，似乎没有明确的战术，只是凭单纯的意识和简单的语句来堆砌出一段程序。感觉有点像张飞打仗，有勇无谋，只要能完成任务就行。但现在编程感觉完全不同了。在编写一个程序之前，自己能够综合考虑

13、各种因素，首先选取自己需要的数据结构，是树还是图或是别的什么？然后选定一种或几种存储结构来具体的决定后面的函数的主要风格。最后在编写每一个函数之前，可以仔细斟酌比对，挑选出最适合当前状况的算法。这样，即使在完整的程序还没有写出来之前，自己心中已经有了明确的原图了。这样无形中就提高了自己编写的程序的质量。另外，我还体会到深刻理解数据结构的重要性。只有真正理解这样定义数据类型的好处，才能用好这样一种数据结构。了解典型数据结构的性质是非常有用的，它往往是编写程序的关键。我以前对递归算法一直很害怕，总是看不明白究竟这递归是怎么进行的。在这次实验中我终于克服了这一障碍，一次次单步执行书中递归函数的例子，并一遍遍在心中自己默默的走，终于弄明白了，真的是功夫不负有心人啊！同时我还根据自己的理解写出了类似的递归函数实现了新的功能，真是受益良多啊！在这次实验中，我对参数的调用也进行了很多种尝试，已经能够相对准确的选择合适的参数形式来实现函数之间的数据传输交互了。这次实验中我也出现过一些比较严重的错误。这是我对基本概念理解的模糊不清造成的。后来在同学的指点下我意识到自己的错误。不过收获也很不少。 通过此次的课程设计，我更加体验到了编程的乐趣，我将在以后的学习中进一步运用数据结构这门课程所学来处理更多的问题。