二元排序树的相关算法排序

福建农林大学计算机与信息学院计算机课程设计报告课程名称: 数据结构二进制排序树相关算法的实现（在遍历顺序中查找平均搜索长度）删除课程设计主题: 名称: 部门: 特殊年份: 级别: 编号: 指出并判断它是否是平衡的二叉树）Chen Yanhua计算机科学与技术（特殊升级）06级别061142017黄思贤副教授指导老师: 职位: 2007年6月28日Ŀ¼封面. ......................................………………………………………… …………………………………………………………………………………………………………………………………………………………………………………………………………………… …………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………… ………………………………………………………………………………………………………………………………………………………………………………………………………… ................................................... ................................................... ....................................... 4 2正文... .................................... ............................................................. 4 2.1课程设计目的...... ................................................................................. 4 2.2课程设计要求…… ………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………4 4框图…………………………………………2.5 2.5程序调试与测试…………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………… ………………………………9 2.7程序代码.................................. ................................................... ................................................... ................................................... ................................................... .............. 10 3摘要................................. ................................................................................................ .................................. 15摘要................... ................................................... ................................................... ................................................... .............................................. ................................................... ...................................................... 16 4参考... .... ................................................... 162二进制排序树相关算法的实现遍历遍历以查找平均搜索长度，删除节点并判断平衡二进制树的目的2.1课程设计？本课程设计的目的是基于C语言，通过完成一些难的课程设计主题的编写，调试，运行工作，以进一步理解和掌握数据结构和算法的设计方法二叉排序树查找 算法，具有初步的独立分析和设计能力初步掌握软件开发过程中的问题分析，系统设计，程序编码和测试等基本方法和技能；巩固学到的理论知识，将理论与实践相结合.

从而提高您分析和解决问题的能力. 以系统的视角和通用的软件开发规范进行软件开发，培养软件工作者应具备的科学工作方法和风格，同时培养学生的调查研究能力，参考技术文献，材料，手册和技术资料. 撰写技术文献. 2.2课程设计要求①，设计主题可以反映数据结构和算法的分析，设计以及算法的算法实现. ②. 基于您自己对数据结构和算法的基本概念，原理和机制的理解，自行准备主题和设计内容，并结合实际应用尽可能选择主题. 2.3课程设计报告的内容1.程序中使用的数据结构和存储结构的说明程序中的数据使用“树结构”作为其数据结构. 具体地，使用“二进制排序树”. 二进制排序树是空树或具有以下属性的二进制树: （1）如果其左子树不为空，则左子树上所有节点的值小于其根节点的值; （2）如果其右子树不为空，则所有在右子树上的节点值大于其根节点的值； （3）它的左和右子树也是二进制排序树. 该程序使用“两次插入的链表”和“一维数组”作为其存储结构. 双插入链表存储结构中的双插入树的节点由一个数据元素和两个分别指向其左子树和右子树的分支组成. 如: 程序中使用的结构为: 3typedef struct Tnode {int data; / *数据元素* / * lchild，* rchild; / *左右指针* / struct Tnode} *节点，BSTnode；一维数组序列表的存储结构是使用一组具有连续地址的存储单元将节点元素从上到下以及从左到右存储在完整的二叉树上，即用数字存储节点元素i标记为i-1的组件中一维数组中完整二叉树上的i.

使用序列表作为存储结构: typedef struct {int int} BST;一维数组存储结构中节点i的父级为|. _i / 2_ |，左边的孩子是2i，右边的孩子是2i +1. 2 3.算法的设计思想a）二插链表被用作存储结构: 二插排序通过在插入时进行搜索来建立树. 搜索功能以递归方式搜索. 如果搜索成功，则不应插入原始树，否则将返回当前节点的前一个节点. 然后使用insert函数将元素插入到原始树中. 递归函数用于二叉树的中阶遍历. 如果根节点不为空，则首先访问左子树，然后访问根节点，最后是右子树. 在计算两次插入排序树的平均搜索长度时，仍然使用类似于中阶遍历的递归方法. 使用s记录总搜索长度，使用j记录每个节点的搜索长度，使用s将初始值设置为0. 获得总搜索长度s. 平均搜索长度等于s / i（i是树中节点的总数）. 使用删除时搜索的方法删除节点功能. 如果找不到，则不对树进行任何修改；如果找到一个节点，将在四种情况下进行讨论: 1.该节点的左和右子树为空； 2.左子树仅是Empty； 3.只有该节点的右子树为空； 4.该节点的左右子树不为空. 判断二元插值排序树是否为平衡二叉树的功能还在于使用递归函数分别确定树中每个节点为根节点的子树是否为平衡二叉树.

只要一个子树不是平衡二叉树，该树也不是平衡二叉树. b）一维数组作为存储结构: *数据； lenth / *一维数组的基地址* / / *一维数组的长度* / 4建立二插排序树，首先记录一维数组Data的读入，然后采用搜索的方式将数据一一插入到完整二叉树的对应位置. 空树节点用“ 0”填充. 中阶遍历二叉树还使用递归函数，首先访问左子树2i，然后访问根节点i，最后访问右子树2i +1. 首先向左走，然后逐层返回，直到所有节点都接受了采访. 在计算二插值排序树的平均搜索长度时，使用类似于中阶遍历的递归方法，s用于记录总搜索长度，j用于记录每个节点的搜索长度，而s设置为初始值0. 总搜索长度s. 平均搜索长度等于s / i（i是树中节点的总数）. 使用插入时搜索的方法在二插排序树中删除节点，类似于将一维数组重建为存储新树的空间. 将原始数组中的数据一一插入到树中. 如果遇到需要删除的节点，将不会执行插入操作. 判断二元插值排序树是否为平衡二叉树的功能还在于使用递归函数来分别确定以树中的每个节点为根节点的子树是否为平衡二叉树. 只要子树不是平衡二叉树，该树也不是平衡二叉树.

3. 平衡二叉树和不平衡二叉树的搜索效率比较（1）对于不平衡二叉树: 当按顺序插入关键字时，形成的两插式排序树成为单个分支树. 树的深度为n，平均搜索长度为（n +1）/2. 这是最坏的情况. 在这种情况下，比较关键字的最大数量为n. （2）最好的情况是: 生成的树是平衡的二叉树. 在这种情况下，两次插入排序树的平均搜索长度与log2（n）成正比. 比较关键字的最大数量为: 0.5logψ（5）+logψ（n + 1）-2次（其中ψ=（1 +根数5）/ 2）. （3）然后进行平均分析: 假设在一个包含n（n> = 1）个关键字的序列中，i个关键字小于第一个关键字，ni-1个关键字大于第一个关键字，在n条记录的搜索概率相等的条件下构造的两次插入排序树为: P（n，i）= [1 + i *（P（i）+1）+（ni-1）（P（ni -1）+1）] / n其中，P（i）是具有i个节点的二元插值排序树的平均搜索长度，而P（i）+1是左搜索. 每个关键字使用的比较次数的平均数树中的关键字是5次，P（ni-1）+1是用于在右侧子树中找到每个关键字的平均比较次数.

假定表中n个关键字的排列是“随机”，即任何关键字将是序列中的第一个或第二个，...或第n个概率，则将上述公式取平均值从i等于0到n-1. 最终将得出: 当n> = 2时，P（n）<= 2（1 +1 / n）ln（n）可以看出，在随机条件下，平均搜索长度和log（n）为相同的数量级. 4.时间复杂度分析解释: 时间复杂度分析是指最坏情况下的时间复杂度. 在两个插入的链表的存储结构中: （1）搜索功能的最坏情况是要找到的点恰好是二叉树的最深叶节点，并且时间复杂度= O（n）. （2）插入函数的最坏情况是要插入的点是二叉树的最深分支的叶节点. 此时，时间复杂度= O（n）. （3）中阶遍历函数，求平均搜索长度的函数，删除函数以及确定二元插值排序树是否为平衡二叉树的函数，其时间复杂度类似于上述情况；等等O（n）. 在一维数组序列表的存储结构中: （1）插入函数的最坏情况是要插入的点是二叉树的最深分支的叶节点，并且时间复杂度= O（ n）. （2）创建函数的最坏情况是插入函数在调用插入函数时遇到最坏情况.

因此，创建函数的时间复杂度也等于O（n）. （3）中阶遍历函数，求平均搜索长度的函数，搜索函数以及确定二元插值排序树是否为平衡二叉树的函数，其时间复杂度类似于上述情况；等等O（n）. （4）delete函数不使用递归方法，而是用于重建两插入的排序树，而无需删除该节点. 它的时间复杂度= O（n）. 6设计原理二叉排序树查找 算法，2.4设计原理，框图以二进制链表作为存储结构，以序列表作为存储结构输入序列L，使用回车（'\\ n'）作为输入结束标记，以生成二进制排序树T； sort binary依次遍历树T，并使用输出来计算二进制排序树T的平均搜索长度，并输出输出元素x，然后搜索二进制排序树T以找到节点x. 没有节点x. 有带有x的节点，然后删除该节点，并对7个二元排序树T进行中阶遍历. 平衡二叉树NY OK！ 2.5程序调试和NO补充测试； 2.6 2.6运算结果2.7程序#include typedef struct Tnode {int data; / *输入数据* / struct Tnode * lchild，* rchild; / *节点的左右指针，指向节点的左右子节点* /} *节点，BSTnode； searchBST（节点t，int键，节点f，节点* p）/ *查找功能* / {if（！t）{* p = f; return（0）;} / *搜索失败* /否则{* p = t; return（1）;} / *查找成功* / else if（key data）if（key == t-> data）searchBST（t-> lchild，key，t，p）; / *继续在左侧子树中搜索* / else searchBST（t-> rchild，key，t，p）; / *继续在右边的子树中搜索* /} insertBST（node * t，int key）/ *插入函数* / {node p = NULL，s = NULL; if（！SearchBST（* t，key，NULL，＆p））/ *搜索失败* / {s =（节点）malloc（sizeof（BSTnode））; s-> data = key; s-> lchild = s-> rchild = NULL;如果（！p）* t = s; / *插入的节点* s是新的根节点* /否则，如果（key

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