二叉排序树的插入与删除

《二叉排序树的插入与删除》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、课程设计题目：二叉排序树的插入、删除算法沈阳航空航天大学课程设计报告2沈阳航空航天大学课程设计报告第1章需求分析1需求分析了解二叉排序树组成与其性质，知道其构成。创建一个二叉排序树，并对其先序遍历，输出。然后根据二叉排序树性质，删除，插入，查找其结点与叶子，然后先序遍历输出。内容：1.给定一组关键字，生成一棵二叉排序树；2.删除该二叉排序树中的指定节点，删除后二叉排序树性质不发生变化；3.用直观、易于理解的形式来演示二叉排序树的插入、删除过程。要求：1、独立完成系统的设计、编码和调试。2、系统利用C语言实现。3、按照课

2、程设计规范书写课程设计报告。4沈阳航空航天大学课程设计报告第2章系统设计2系统设计2.1数据结构设计typedefstructTree{intdata;structTree*lchild,*rchild;}Tree,*PTree;定义结构体Tree，data：数据，*lchild：指针左孩子，*rchild：指针右孩子*PTree代表结构体的指针2.2函数设计本系统所设计的函数见表2.1。表2.1函数列表函数名称函数原型功能描述mainvoidmain();系统主程序InsertintInsert(PTree&p,in

3、tk)将数据挨个插入到二叉排序树中Tree*CreateTree*Create(intA[],intn)创建新的二叉排序树searchintsearch(Tree*T,inte,Tree*f,PTree&p)查找二叉排序树中的数据sertvoidsert(PTree&T,inte)在二叉树中插入结点DeleteTreeintDeleteTree(PTree&T,inte)删除二叉树中的结点fvoidf(PTree&p)删除结点并重新排序preordervoidpreorder(Tree*T)遍历先序二叉排序树本系统函数

4、的调用关系见图2.1。5沈阳航空航天大学课程设计报告第2章系统设计mainTree*CreateInsertsearch图2.1函数调用关系6沈阳航空航天大学课程设计报告第2章系统设计2.3关键流程2.3.1系统主流程scanf_s("%d",&j)!=EOFswitch（j）case1case2case4case3return0是否开始结束图2.2系统主流程7沈阳航空航天大学课程设计报告第2章系统设计2.3.2创建函数流程p==NULLp=(Tree*)malloc(sizeof(Tree));p->data=k;p

5、->lchild=p->rchild=NULL;k==->datakdatareturn0Insert(p->lchild,k)Insert(p->rchild,k)是是是否否否开始结束图2.3创建函数主流程8沈阳航空航天大学课程设计报告第2章系统设计2.3.3插入函数流程!search(T,e,NULL,p)s=(PTree)malloc(sizeof(Tree));s->data=e;s->lchild=s->rchild=NULL;p==0edatap->lchild=sT=sp->rchild=

6、s是否否是是否开始结束图2.4插入函数主流程9沈阳航空航天大学课程设计报告第2章系统设计2.3.4删除函数流程T==0e==T->dataedataDeleteTree(T->lchild,e)DeleteTree(T->rchild,e)f(T)return1否否否是是是开始结束图2.5删除函数主流程10沈阳航空航天大学课程设计报告第3章调试分析3调试分析(1)指针问题l问题描述：输入数据时，总不能得到结果。l问题分析：在建立二叉树函数定义中，是对指针的值进行修改l解决方法：使用指向指针的指针(2)字符问题l

7、问题描述：试验中经常出现前后字符不一致的情况。l问题分析：编写时不够自习，遇到比较长的程序，容易出错。l解决方法：勤加练习，认真仔细检查。(3)问题l问题描述：在类似（*T)->key=key,没加括号，程序不能运行。l问题分析：不够仔细。l解决方法：检查程序，注意细节。11沈阳航空航天大学课程设计报告第4章测试及运行结果4测试及运行结果输入6个数据：1995817722先序遍历后的结果：1987179522插入结点56，输出先序遍历结果：19871795225612沈阳航空航天大学课程设计报告第4章测试及运行结果选择

8、删除的结点：7输出先序遍历结果：1981795225613沈阳航空航天大学课程设计报告参考文献参考文献[1]严蔚敏吴伟民数据结构（C语言版）：清华大学出版社[2]王敬华林萍张清国C语言程序设计教程（第二版）：清华大学出版社[3]韦斯数据结构与算法分析（C语言描述）：机械工业出版社[4]王宏生.数据结构.北京：国防出版社。[5]滕国