二叉排序树的插入与删除.docx

课程设计题目：二叉排序树的插入、删除算法沈阳航空航天大学课程设计报告2沈阳航空航天大学课程设计报告 第1章 需求分析1 需求分析了解二叉排序树组成与其性质，知道其构成。创建一个二叉排序树，并对其先序遍历，输出。然后根据二叉排序树性质，删除，插入，查找其结点与叶子，然后先序遍历输出。内容：1. 给定一组关键字，生成一棵二叉排序树；2. 删除该二叉排序树中的指定节点，删除后二叉排序树性质不发生变化；3. 用直观、易于理解的形式来演示二叉排序树的插入、删除过程。要求： 1、独立完成系统的设计、编码和调试。2、系统利用C语言实现。3、按照课程设计规范书写课程设计报告。4沈阳航空航天大学课程设计报告 第2章 系统设计 2 系统设计2.1 数据结构设计typedef struct Treeint data;struct Tree *lchild, *rchild;Tree, *PTree;定义结构体Tree，data：数据，*lchild：指针左孩子，*rchild：指针右孩子*PTree代表结构体的指针2.2 函数设计本系统所设计的函数见表2.1。表2.1 函数列表函数名称函数原型功能描述mainvoid main();系统主程序Insertint Insert(PTree &p, int k)将数据挨个插入到二叉排序树中Tree *CreateTree *Create(int A, int n)创建新的二叉排序树searchint search(Tree *T, int e, Tree *f, PTree &p)查找二叉排序树中的数据sertvoid sert(PTree &T, int e)在二叉树中插入结点DeleteTreeint DeleteTree(PTree &T, int e)删除二叉树中的结点fvoid f(PTree &p)删除结点并重新排序preordervoid preorder(Tree *T)遍历先序二叉排序树本系统函数的调用关系见图2.1。5mainTree *Create Insertsearch图2.1 函数调用关系62.3 关键流程2.3.1 系统主流程scanf_s(%d, &j) != EOFswitch（j）case1case2case4case3return0是否开 始结 束图2.2 系统主流程72.3.2 创建函数流程p = NULLp=(Tree*)malloc(sizeof(Tree);p-data = k;p-lchild = p-rchild = NULL;k= -datakdatareturn0Insert(p-lchild, k)Insert(p-rchild, k)是是是否否否开 始结 束图2.3 创建函数主流程82.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 = s是否否是是否开 始结 束图2.4 插入函数主流程92.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 问题描述：试验中经常出现前后字符不一致的情况。l 问题分析：编写时不够自习，遇到比较长的程序，容易出错。l 解决方法：勤加练习，认真仔细检查。(3) 问题l 问题描述：在类似（*T)-key=key,没加括号，程序不能运行。l 问题分析：不够仔细。l 解决方法：检查程序，注意细节。11沈阳航空航天大学课程设计报告 第4章 测试及运行结果4 测试及运行结果输入6个数据：19 95 8 17 7 22 先序遍历后的结果：19 8 7 17 95 22插入结点56，输出先序遍历结果：19 8 7 17 95 22 5612沈阳航空航天大学课程设计报告 第4章 测试及运行结果 选择删除的结点：7 输出先序遍历结果：19 8 17 95 22 5613沈阳航空航天大学课程设计报告 参考文献 参考文献1 严蔚敏 吴伟民 数据结构（C语言版）：清华大学出版社2 王敬华 林萍 张清国 C语言程序设计教程（第二版）：清华大学出版社3 韦斯 数据结构与算法分析（C语言描