用于构建二进制排序树的C程序设计方案

建立二进制排序树的C程序的设计程序和目标1.目的数据结构课程设计是学习数据结构课程后的综合实践环节，是课程学习的综合和补充. 通过课程设计，培训学生使用所学的理论和技能来分析和解决实际问题，并增强他们的实践技能和创新能力. 2.目标1.结合c和数据结构的理论知识，根据需要设计一个独立的计划，并培养独立分析和解决实际问题的能力. 增强学生的实践能力和创新能力. 2.学习查阅数据，并熟悉常见算法的使用和技术. 3.认真编写课程设计报告，树立严谨的作风和科学的态度. 2.问题分析该程序需要满足以下要求: 首先输入任何数据集，将其放入二进制排序树中，然后依次遍历，然后输出遍历的数据序列；第二，二进制排序树可以实现基本操作，例如搜索，插入和删除数据（即，二进制排序树的节点）. 该程序的实现需要解决以下问题: 1.如何构造二进制排序树. 2.如何通过中间顺序遍历输出二进制排序树. 3.如何实现多次搜索. 4.如何执行插入和删除等操作. 二进制排序树的定义: 如果左子树不为空，则左子树中所有节点的值小于根节点的值. 如果右子树不为空，则右子树中所有节点的值都大于根节点的值. 左右子树也是二进制排序树.

此问题的关键在于构建二进制排序树. 根据上面的二进制排序树，二进制排序树的生成需要通过插入算法来实现: 输入（插入）的第一个数据是根节点；继续插入，当插入的新节点的键值小于根节点的值时，该值用作左子节点；当插入的新节点的键值大于根节点的值时，则为作为合适的孩子；左右子树中的插入方法与整个二进制排序树相同. 当在建立二进制分类树之后要插入新数据时，有必要确定当前插入的数据在已建立的二进制分类树序列中是否存在. 因此，插入算法还包括搜索和判断数据的过程. 这个问题的难点在于二进制分类树的删除算法的实现. 在删除之前，我们必须首先搜索以确定给定节点在二进制排序树中是否已经存在；在删除时，为了确保删除节点后的二叉树仍然是二叉排序树，我们必须考虑各种情况，选择正确的方法. 有几种情况讨论删除操作，稍后将介绍. 3.总体设计使用二进制链表作为二进制排序树的存储结构，其中key是节点的键值，* lchlid和* rchild分别是左和右子指针. 该程序的流程图如下所示: 开始I = 0退出输入节点值N节点是否为0是输入主菜单输入i I = 3 I = 4 I = 1 I = 2查找插入删除显示输入J = 1 J = 2一般流程图4.特定设计首先定义二进制排序树的数据类型，如下所示: typedef struct node {int key; //关键字项目struct node * lchild，* rchild; //左，右子指针} Bstnode;然后按一定顺序编写算法程序: 4.1递归搜索算法的具体思想如下: （1）如果二叉树为空，则搜索失败.

（2）否则，将根节点的键值与要检查的关键字进行比较二叉排序树 c二叉排序树 c，如果相等，则搜索成功；如果根节点的关键值大于待检查的值，则输入左子树并重复此步骤；否则，输入右子树并重复此步骤；如果在搜索过程中遇到了二进制排序树的叶节点，并且尚未找到要检查的节点，则搜索失败. if（t == NULL）返回NULL; else {if（t-> data == x）返回t; if（x data）return（Bsearch（t-> lchild，x））; else return（Bsearch（t-> rchild，x））;}二元排序树的流程图返回搜索算法4.2非递归搜索算法的搜索过程从根节点开始，并逐层向下进行. 并定义标签数量记录是否找到节点. Bstnode * searchBST（Bstnode * t，int x）{Bstnode * p; int flag = 0; p = t; //定义* p个节点用于逐层搜索，丛根节点开始搜索，而（p！= NULL）//二进制排序树不为空{if（p-> key == x）//搜索成功{printf（节点值存在！）; flag = 1; break;} //搜索失败，继续查找if（x key）p = p-> lchild; //查找左子树；否则p = p-> rchild; //查找右子树} if （flag == 0）{printf（未找到值％d的节点！，x）; p = NULL;}返回p;}（p-> key == x）是，找到成功Y是下一层？ N找不到节点p = p-> lchild; p = p-> rchil d二叉排序树的非递归搜索算法流程图4.3插入算法从根节点开始，根据比较规则，与要插入的节点的值一一对应. 插入节点在二进制排序树中的将来位置，然后插入该节点.

将具有x的键值的节点s插入到二进制排序树中，如下所示: （1）如果二进制排序树为空，则具有x的键值的节点s成为二进制树的根. （2）如果二进制排序树不为空，则将x与二进制排序树的根进行比较. 如果x的值等于根节点密钥的值，则停止插入；如果x的值小于根节点密钥，则x的值小于根节点关键字. 如果x的值大于根节点键的值，则将x插入右子树. 左右子树中的插入方法与整个二进制排序树相同. Bstnode * InsertBST（Bstnode * t，int x）//插入键值为x的元素{Bstnode * s，* p，* f; // * s是要插入的节点，* p是查找节点层按层，* f是要插入的节点的父节点p = t; while（p！= NULL）{f = p; //在搜索过程中，f指向* p的父节点if（x == p-> key）//如果有一个键值为x在二叉树中，不需要插入return t; if（x key）{p = p-> lchild;} else {p = p-> rchild;}} s =（Bstnode *）malloc（sizeof（Bstnode））; s-> key = x; s-> lchild = NULL; s-

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