二分类树课程设计报告

计算机科学与技术系课程设计报告2008〜2009学年第二学期课程数据结构与算法二进制排序树计算课程设计学校的名称指的是指导课，老师，年级师，2009年6月，问题分析和任务定义问题分析和任务定义主题: 二进制排序树操作主题: 任务定义: 并在二进制排序树中实现多种搜索方式. 基本任务: 任务定义为一组数据构造一个二进制排序树，（1）选择一个合适的存储结构来构造一个二进制排序树； （2）对二元分类树T进行中阶遍历，并输出结果. （3）中的二进制排序树实现了多种搜索方式，并在二进制排序树中提供了插入和删除操作. （4）尝试给出“序列和链”两种不同结构下的运算并进行比较. 要完成该问题的需求，您需要解决以下问题: 1.选择一种数据结构来存储二叉树的信息. 2.建立一个新的二进制排序树3.在二进制排序树中插入，删除和查找相关节点2.数据结构选择和摘要设计数据结构选择和摘要设计1.数据结构选择: 主题要求选择合适的存储结构构建一个二进制排序树，然后选择一个链结构存储. 在链接列表中构造节点，并将节点存储在二进制排序树中！节点类型和指针类型如下！ typedef结构节点{int键;其他struct node * lchild，* rchild;} Bstnode; 2.概述设计: 为了完成所需的功能，所需的功能及其功能如下: main（）: 主要功能模块Bsearch（）: 找到对应的节点InsertBST（）: 插入新的节点CreateBST（）: 创建二进制排序树Inorder（）: 对二进制排序树菜单（）进行有序遍历: 主功能显示菜单模块DeleteBST（）: 删除节点主功能流程图: 开始在菜单中输入元素二进制排序树调用菜单函数显示菜单输入k = 1调用子函数InsertBST（）Inorder（）k = 2调用子函数Bsearch（）k = 3调用子函数DeleteBST（）Inorder（）k = 4结束图（a ）主要功能流程图子功能流程图: 插入子功能InsertBST（）流程图: 开始Y x = p-> keyNx keyN Yp = p-> rchild p = p-> lchild图（b）的流程图子功能InsertBST（）子功能Bsearch（p）的流程图开始输入需要t的值o将被搜索并调用搜索功能，并返回标志= 0 Y值找不到为％. d的节点N已找到节点的末端图（c）子功能Bsearch的流程图（p）3. 详细设计与编码二进制分类树的详细设计和基本操作1.二进制分类树的搜索算法（1）如果二进制分类树为空，则搜索失败.

（2）否则，将根节点的关键字与要检查的关键字进行比较. 如果它们相等，则搜索成功；否则，搜索成功. 如果root node关键字大于要检查的值，则输入左子树并重复上述步骤；否则，输入右子树进行该步骤. 如果在搜索过程中遇到了二进制排序树的叶节点，并且没有找到要搜索的节点，则搜索不成功. 算法如下: Bstnode * Bsearch（Bstnode * t，int x）//查找{Bstnode * p; int标志= 0; p = t; while（p！= NULL）{if（p->键== x）{printf（“已找到节点！”）；标志= 1;返回（p）;如果（x 键）p = p-> lchild; else p = p-> rchild;} if（标志== 0）{printf（“未找到值％d的节点！”，x）; return NULL;}} 2.二进制排序树的节点插入算法在二进制排序树中插入一个新节点，第一步是查找该节点是否已存在于二进制排序树中. 如果在二进制排序树中没有键等于x的节点，请插入. 要将键值为x的节点s插入二进制排序树中，可以使用以下方法: （1）如果二进制排序树为空，则关键字x的节点s成为二进制排序树的根'（2）如果二进制排序树不为空，则将x与二进制排序树的根进行比较. 如果x的值等于根节点的键值，则停止插入；如果x的根节点的值小于根节点的键值，则将x插入左子树；如果x的值大于根节点键的值，则将x插入右子树.

左右子树的插入方法与整个二进制排序树相同. 算法如下: Bstnode * InsertBST（Bstnode * t，int x）//插入{Bstnode * s，* p，* f; p = t; while（p！= NULL）{f = p; //在搜索过程中，如果（x == p->键）返回t，则f指向* p的父节点； //如果（x 键）p = p-> lchild;则乱序插入二进制排序树中带有关键字x的元素； else p = p-> rchild;} s =（Bstnode *）malloc（sizeof（Bstnode））; s->键= x; s-> lchild = NULL; s-> rchild = NULL;如果（t == NULL）返回s; //如果（x 键）f-> lchild = s，则原始树为空二叉排序树构造，新节点成为二进制排序树的根. //新节点位于* f子项的左边，否则f-> rchild = s; //新节点是* f return t;}的右子节点. 3.二进制排序树的节点删除算法会删除二进制排序树中的节点，首先，需要执行搜索操作以确定是否删除的节点不在二进制排序树中，不执行任何操作；否则，假定要删除的节点是* p，节点* p的父节点是* f，并假定* p是* f child的左侧.

根据删除的节点* p是否具有子节点，可以在以下三种情况下讨论删除: （1）如果* p是叶节点，则其父节点* f的左子指针字段可以保留为空，直接将其删除. （2）如果* p节点仅具有右侧或左侧子树，则可以直接将p的左侧或右侧子树更改为其父节点f的左侧子树. （3）如果* p同时具有左子树和右子树；节点* s是* p的中阶前任. 首先找到* p的中级前任节点* s，然后用node * s的值替换node * p的值，然后删除node * s，将node * s的原始左子树更改为父级* s * q的节点右子树；算法如下: Bstnode * DeleteBST（Bstnode * t，int k）//删除{Bstnode * p，* f，* s，* q; p = t; f = NULL; while（p）{//如果（p-> key == k）中断，则用关键字k * p查找要删除的节点； //找到它，然后退出循环f = p; //如果（p-> key> k）p = p-> lchild;则节点* f是节点* p的父节点； else p = p-> rchild;}如果（p == NULL）返回t; //如果未找到，则返回原始二进制排序树的根指针，如果（（p-> lchild == NULL）||（p-> rchild == NULL））{//如果* p没有左或右child if（f == NULL）// if * p是原始二进制文件if（p-> lchild == NULL）t = p-> rchild;否则t = p-> lchild;否则if（p-> lchild == NULL）//如果* p没有左子if（f-> lchild == p）f-> lchild = p-> rchild; // p是* f的左子元素； f-> rchild = p-> rchild;否则if（f-> lchild == p）//如果* p没有合适的孩子f-> lchild = p-> lchild; // p是* f的左子元素； f-> lchild = p-> lchild; // p是* f free（p）的右子；}否则{q = p; s = p-> lchild; //如果p具有左右子树，而（s-> rchild）{q = s; s = s-> rchild; // * *的左子节点如果（q == p）q-> lchild = s-> lchild;在树中找到最右边的底部节点； p->键= s->键； //将* s分配给* p free（s）;} return t;} 4.机上调试机上调试1.我编写的程序与教科书中的二进制排序树基本相同！但是，在调试过程中遇到了一些问题.

我使用非递归思维进行遍历，因此存在基本的语法错误. 问题主要在于函数和变量的定义. 编写关键字和函数名称. 2.时空性能分析: 二叉树的搜索类似于二叉树的搜索，是一个逐一缩小搜索范围的过程. 具有n个节点的排序二叉树是深度为n的单分支树，平均搜索长度与顺序搜索相同，为（n +1）/ 2；也就是说，平均搜索长度约为O（n）. 五岁以下测试结果和分析测试结果和分析1.输入节点信息: 图（1）输入节点信息图2.显示菜单后，根据提示选择操作选择并插入新的节点图（2）插入新的节点图选择在该操作中，找到一个现有的节点图（3）找到一个现有的节点图4，找到一个不存在的节点. 图（4）查找丢失的节点图5.删除节点图（5）删除节点图6.如果操作完成，请退出程序. 图（6）退出图6.用户指令用户指令1.进一步提示用户输入二进制排序树的节点信息，并以0结尾. 2.根据菜单提示，选择相应的操作3.输出结果是遍历后结果的中间顺序. 7参考文献参考文献[1]王昆仑，李宏等. 数据结构和算法. 北京: 中国铁道出版社，2007. [2]李业立，郑良斌. 数据结构（c）实验教程.

北京理工大学出版社2005年VIII. 附录（源代码），附录（源代码）#include“ stdio.h” #include“ malloc.h” #define NULL 0 typedef struct node {int key;其他struct node * lchild，* rchild;} Bstnode; Bstnode * Bsearch（Bstnode * t，int x）//查找（Bstnode * p; int标志= 0; p = t; while（p！= NULL）{if（p-> key == x）{printf（“已经找到了该节点！“）;标志= 1；返回（p）;中断;}如果（x 键）p = p-> lchild；否则p = p-> rchild;}如果（flag = = 0）{printf（“未找到值％d的节点！”，x）；返回NULL；}} Bstnode * InsertBST（Bstnode * t，int x）//插入{Bstnode * s，* p，* f; p = t; while（p！= NULL）{f = p; //在搜索过程中，如果（x == p-> key）返回t; f指向* p的父节点； //如果（x 键）p = p-> lchild;否则p = p-> rchild;} s =（Bstnode *）malloc（sizeof（Bstnode） ）; s-> key = x; s-> lchild = NULL; s-> rchild = NULL; if（t == NULL）返回s; if（x key）f-> lchild = s; else f-> rchild = s; return t;} //原始树为空，新节点成为二进制排序树的根// //新节点为* f的左子节点// new节点为右辣椒d of * f Bstnode * CreateBST（）//创建新的二叉树{Bstnode * t;整数键; t = NULL; //将二进制排序树的初始状态设置为空scanf（“％d”，＆key）; //读取第一个节点的关键字while（key！= 0）{t = InsertBST（t，key）; scanf（“％d”，＆key）;} return t;} void Inorder（Bstnode * T）//有序遍历{if（T）{Inorder（T-> lchild）; printf（“％4d”，T->键）； Inorder（T-> rchild）;}} //如果二进制树不为空//序列遍历左子树//访问根节点//序列遍历右子树Bstnode * DeleteBST（Bstnode * t，int k）//删除{Bstnode * p，* f，* s，* q; p = t; f = NULL; while（p）{//如果（p-> key == k）中断，则用关键字k * p查找要删除的节点； //找到，然后退出循环f = p; //如果（p-> key> k）p = p-> lchild，则节点* f是节点* p的父节点; else p = p-> rchild;}如果（p == NULL）返回t; //如果未找到，则返回原始二进制排序树的根指针，如果（（p-> lchild == NULL）||（p-> rchild == NULL））{//如果* p没有左子项或合适的子代if（f == NULL）//如果* p是原始二进制排序树的根if（p-> lchild == NULL）t = p-> rchild;否则t = p-> lchild;否则if（p-> lchild == NULL）//如果* p没有左子if（f-> lchild == p）f-> lchild = p-> rchild; // p是* f的左子元素； f-> rchild = p-> rchild;否则if（f-> lchild == p）//如果* p没有合适的子代f-> lchild = p-> lchild;否则f-> lchild = p-> lchild; free（p）;}否则{q = p; s = p-> lchild;而（s-> rchild）{q = s; s = s-> rchild;点} if（q == p）q-> lchild = s-> lchild; p->键= s->键； free（s）;} return t;} // p是* f的左子// // p是* f的右子// //如果p具有左右子树//在左子树中找到最右边的下部of * p //将* s的值分配给* pvoid菜单（）{printf（“┏━━━━━━━━━━━━━━┓\ n”）; printf（“┃1----------插入节点-----------┃\ n”）； printf（“┠────────────┨\ n”）； printf（“┃2------ ----查找节点-----------┃\ n”）； printf（“┠────────────┨\ n”）； printf（“┃3----------删除节点-----------┃\ n”）； printf（“┠───────────────┨\ n”）； printf（“┃4-----------退出--------------┃\ n”）； printf（“┗━━━━━━━━━━━━━━━━┛n”）;} void main（）{Bstnode * tree，* p; int seai，deli，x; int k，标志= 1; printf（“请输入节点信息并以'0'结尾: \ n”）； tree = CreateBST（）; printf（“中间序列的遍历序列为: \ n”）;有序（树）； printf（“ \ n”）;菜单（）; while（flag）{printf（“请选择操作: ”）； scanf（“％d”，＆k）;开关（k）{情况1: {printf（“插入新节点: ”）； scanf（“％d”，＆x）; InsertBST（tree，x）; printf（“插入后，将按顺序遍历结果序列: \ n”）；有序（树）； printf（“ \ n”）;中断；}情况2: {printf（“输入搜索数据: ”）； scanf（“％d”，＆seai）; p = Bsearch（树，seai）； printf（“ \ n”）;中断；}情况3: {printf（“输入已删除的数据: ”）； scanf（“％d”，＆deli）;树= DeleteBST（树，熟食店）; printf（“删除后二叉排序树构造，遍历顺序为: \ n”）；有序（树）； printf（“ \ n”）;中断；}情况4: {flag = 0;休息;}}}}

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-227938-1.html