二叉排序树的查找算法代码实现_如何判断完全二叉树

1.本周学习总结（0-4分） 　　0.PTA得分截图 　　
　　1.本周学习总结（0-4分） 　　1.1 总结查找内容 　　查找的基本概念 　　动态查找表：在查找的同时对表做修改操作 　　静态查找表：在查找中不涉及表的修改操作 　　平均查找长度ASL：关键字的平均比较次数 　　
　　ASL还有分为查找成功和查找不成功两种情况 　　静态查找 　　用于查找运算的顺序表采用数组表示，改数组素的类型声明如下 　　1.顺序查找 – 顺序查找的基本思路：从表的一端向另一端逐个将素的关键字与给定值K比较。相等则查找成功，若整个查找表都扫描结束后仍未找到，则查找失败 　　具体代码如下： 　　算法分析 – 该算法查找第i个素所需要的关键字比较次数取决于改素在表中的位置。 – 查找成功时的平均比较次数约为表长的一半：ASL成功=(n+1)/2 – 若k不在表中则需遍历完表，查找n次：ASL不成功=n – 从代码中可以看出来，由一层循环完成，顺序查找的平均时间复杂度为O(n) 存储结构选择 顺序查找优点是算法简单，且对表的结构无特别要求，即顺序表和链表都可。缺点就是查找效率低。 2.折半查找 折半查找又称二分查找，它是一种效率较高的查找方法。 – 其前提是：折半查找要求线性表必须是有序表 　　如下图为一棵二叉查找的判定树： 　　
　　
折半查找的基本思路 　　是设R[low……high]为当前的查找区间，首先确定该区间的中点位置mid=[(low+high)/2],然后将待查的k值与R[mid].key比较，并且不断缩小查找区间。 　　重复知道找到关键字为k的素，或者直到查找区间为空，即查找失败。 　　具体代码 　　算法分析 计算ASL: – 计算成功ASL时，分母是内部结点个数，计算不成功ASL时，分母则是查找不成功的所有区间（最好补全区间后再计算，不容易出错） – 计算单个比较次数要注意查找得到和查找不到的比较次数的区别： 　　
　　
计算时间复杂度： – 由二叉判定树我们可知经历比较的关键字次数恰好为改素在树中的层数。 当n比较大时，判定树看成内部节点的总数为n = 2h – 1、高度为h = log2(n + 1)的满二叉树 　　则折半查找成功时的平均查找长度：ASL成功=log2(n+1) -1 折半查找在查找失败所需比较的关键字个数不超过判定书的高度，在最坏情况下查找成功的比较次数也不超过判定树的高度 归纳起来，折半查找的时间复杂度为O（log2 n） 存储结构选择 由于折半查找需要确定查找的区间，因此利用数组下标更为方便，所以适用于适用顺序表。 　　哈希表 　　哈希表（Hash Table）又称散列表，是除顺序表存储结构、链接表存储结构和索引表存储结构之外的又一种存储线性表的存储结构。 　　注意：哈希表是一种存储结构，它并非适合任何情况，主要适合记录的关键字与存储地址存在 *某种函数关系 的数据。 　　对于哈希地址相同的要插入哈希表中的两个素我们称为哈希冲突（同义词冲突） 　　注意设计哈希表时：哈希表长度与装填因子有关。 哈希函数构造方法 　　哈希冲突解决方法 (开放定址法) 　　哈希表上的运算 　　结构体 　　具体操作代码 　　哈希表插入以及创建哈希表 　　哈希表查找 　　哈希表删除 　　哈希链的相关操作 　　哈希链即采用拉链法解决冲突的哈希表。 　　结构体定义 　　注意学习堆区建哈希链的方法 　　动态查找 　　1.二叉搜索树（二叉排序树） 　　其定义为二叉排序树或者是空树。若左子树非空则左子树上的所有节点关键字均小于根结点关键字，若右子树非空，则右子树上的所有节点关键字均大于根结点关键字 　　中序遍历的二叉排序树是一个递增序列 　　结构体定义 　　-即至少包括关键字和左右孩子 二叉搜索树的相关操作 1.1二叉搜索树的查找 二叉搜索树，和二分查找类似，也是一个逐步缩小查找范围的过程。 　　具体代码 　　递归进行查找，若bt=NULL,则说明查找失败，返回空指针。因此要注意初始化时，若创建新结点注意初始化左右孩子为空 二叉排序树的中序序列是一个递增有序序列因此： 根结点的最左下结点是关键字最小的结点 　　根结点的最右下结点是关键字最大的结点 　　1.2二叉搜索树的插入和创建 　　二叉搜索树插入思路 　　
　　插入的素一定在叶结点上，因此为空则说明该结点为叶结点所以插入 　　该插入过程就是边查找边插入，因此递归函数插入，最后结果为插入是否成功 　　（同时表示了，若插入成功说明原表中无此关键字，失败则说明已存在） 　　具体代码 　　二叉搜索树的创建思路 即为不断的调用插入函数，但要注意，二叉排序树初始是一棵空树，然后根据序列不断插入 　　具体代码 　　同时需要注意的一点是，正是由于插入是插入在叶子结点，尽管关键字一样，若插入序列顺序不同，所建出的二叉排序树也可能长得不同 　　
1.3二叉搜索树的删除 　　二叉搜索树删除的思路：查找到要删除的结点后分情况讨论（因此在也是边查找，在查找的框架下进行删除操作） 　　具体代码 　　接下来，图示具体说明有左右孩子时，如何删除： 　　
　　
　　
　　
递归函数的写法 写递归函数时，将左右孩子都有的情况另写一个函数 　　关于左右子树都有部分对两种写法进行比较 　　
　　递归过程图示： 　　
2.平衡二叉树 2.1定义 　　问题提出：在含有n个结点的二叉排序树查找操作执行时间与树形有关，最坏情况下就是单支树执行时间就为O(n),为了使最坏情况下的时间也是O(log2 n)。 　　因此有了平衡二叉树，就是在插入或删除结点时通过调整树的形态来保持树的平衡。 　　平衡二叉树有很多中，其中较为著名的是AVL树 　　若一棵二叉树中每个结点的左右自述的高度最多相差1，则称此二叉树为平衡二叉树 　　平衡因子：一个结点的平衡因子是该结点左子树的高度减去右子树的高度，即当平衡因子的绝对值小于等于1时，该结点平衡。 　　若一棵二叉树的所有结点都平衡，才为平衡二叉树 2.2平衡二叉树的插入 　　（此部分仅需掌握过程，无需具体掌握代码） 在插入调整过程中共分为四种情况: 　　1）：LL型调整 起因是在A结点左孩子（结点B）的左子树插入结点，使得A结点不平衡 　　
调整方法是:将B结点向上代替A结点称为根结点，而A结点作为B结点的右孩子，同时B的右孩子作为A的左孩子 　　
　　2):RR型调整（与LL型相对称） 起因是在A结点右孩子（结点B）的右子树插入结点，使得A结点不平衡 调整方法同样将B结点向上代替A作为根结点，但A结点作为B的左孩子，B的左孩子作为A的右孩子 　　
　　3）：LR型调整 起因是在A结点左孩子（结点B）的右子树插入结点，使得A结点不平衡 调整方法将结点C上升作为根结点，B结点作为C的左孩子，A结点作为C的右孩子，C的结点的原左子树作为B结点的右子树，C结点的原右子树作为A结点的左子树 　　
　　4）：RL型调整（与LR型对称） 起因是在A结点右孩子（结点B）的左子树插入结点，使得A结点不平衡 调整方法将结点C上升作为根结点，A结点作为C的左孩子，B结点作为C的右孩子，C的结点的原左子树作为A结点的右子树，C结点的原右子树作为B结点的左子树 　　
调整方法总结 　　2.3平衡二叉树的删除 　　平衡二叉树中删除一个结点与二叉排序树中删除结点类似，只是增加了调整这一步骤 　　调整：若被删除的是结点q,则从结点q向根结点方向查找第一个失去平衡的点。 　　（具体调整类型同上） 　　3.B-树和B+树 　　基本概念等： BST和AVL树都是内存中，适用小数据量。每个节点放一个关键字，树的高度比较大。 　　B-树和B+树：一个节点可放多个关键字，降低树的高度。可放外存，适合大数据量查找。如数据库中数据。 　　每个结点n为关键字个数，n+1孩子指针。（因为分成n+1个区域，每个指针分别指向这n+1个区域） 　　
B_结构体类型 　　B-树的查找 和二叉树的查找思路差不多，只是分情况不同 　　B_树的插入 　　分裂过程： 　　
　　下面以一棵3阶B_树的插入过程为例： 　　
　　插入图示： 　　
B_树的删除 B_树的删除分为叶子结点和非叶子结点的删除 叶子结点的删除又分为三种： 　　如删除叶子结点中关键字15，min=2: 　　删除15后，双亲结点17下移到原关键字15的位置，兄弟结点18上移到原双亲结点17的位置 　　
　　如删除叶子结点中关键字15，min=2: 　　
该例中，删除后，双亲中关键字小于min,则应继续2操作（合并） 非叶子结点的删除 　　结合上述删除操作，下面以 MIN=1 　　对B-树做下面操作： 1.删除80 2.删除60 3.删除35 　　
　　哈希表 　　哈希表（Hash Table）又称散列表，是除顺序表存储结构、链接表存储结构和索引表存储结构之外的又一种存储线性表的存储结构。 　　注意：哈希表是一种存储结构，它并非适合任何情况，主要适合记录的关键字与存储地址存在 *某种函数关系 的数据。 　　对于哈希地址相同的要插入哈希表中的两个素我们称为哈希冲突（同义词冲突） 　　注意设计哈希表时：哈希表长度与装填因子有关。 哈希函数构造方法 　　哈希冲突解决方法 (开放定址法) 　　哈希表上的运算 　　结构体 　　具体操作代码 　　哈希表插入以及创建哈希表 　　哈希表查找 　　哈希表删除 　　哈希链的相关操作 　　哈希链即采用拉链法解决冲突的哈希表。 　　结构体定义 　　注意学习堆区建哈希链的方法 　　哈希链插入和删除操作，与链表的插入删除类似。 　　1.2.谈谈你对查找的认识及学习体会。 　　学了查找这部分，学习过程中，对各种查找的算法分析进行了具体的学习，感觉对各个算法间的优劣认识有所提高。不同的算法有不同的特点，不同的适用范围，今后也要学着根据具体情况，对情况分析，选择适合的算法。 　　2.PTA题目介绍 　　2.1 7-1 是否完全二叉搜索树 　　
　　
　　
2.1.1 该题的设计思路 　　先通过序列将二叉排序树建起来，再进行判断。 　　通过层次遍历，根据完全二叉树的特点对其进行判断。 　　层次遍历时同时判断，层次遍历不间断输出结点，最后函数返回判断结果 　　层次遍历时完全二叉树的 一个特点：即当遍历到某个顶点时，无论左孩子是否存在，只要右孩子不存在就说明， 　　接下来遍历的是接下来遍历的点一定都是都是叶子结点（则遍历这些结点是是不可能有孩子的） 　　!
　　以该特点作为判断，一旦开始发现叶子结点，此后在遍历叶子结点过程中，若有孩子则一定不为完全二叉树。 　　总的框架还是在层次遍历的基础上完成，因为这是完全二叉树在层次遍历时的特点 　　该算法遍历一次序列创建树，又层次遍历一次树输出并判断，因此时间复杂度为O(n) 2.1.2 该题的伪代码 　　
2.1.3 PTA提交列表 　　
　　之前花的时间主要是在思考如何判断是否完全二叉树的误区，一开始没什么思路。 　　之前甚至调用高度函数，但是其中要考虑的东西太多了没法实现。一开始还有就是思考控制层的输出，就是已知层中素个数，认真思考仍有些例子无法解决。 　　后来看题目是层次遍历输出，就想着说不定能通过层次遍历过程中康康如何实现。于是才对此深究起来。 　　代码上的错误基本上都在调试时修改，后面提交的错误就是格式错误控制输出的问题：输出之间空格，末尾无空格 　　
　　在while（队列不空）循环中加上该语句，并且要在最后。 　　当所有素都出队，并且无孩子再进队了，则说明无节点要遍历了，说明是结束了，其余情况都输出空格 2.1.4 本题设计的知识点 　　1.本题回顾了完全二叉树，根据树的特点以及自己对题目的思考，归纳了一个完全二叉树在层次遍历时的特点借此来判断是否完全二叉树的： 　　当遍历到某个顶点时，无论左孩子是否存在，只要右孩子不存在就说明，接下来遍历的是接下来遍历的点一定都是都是叶子结点（即接下来遍历的点左右孩子一定都是不存在的） 　　2.对树的层次遍历又进行了复习，该题判断是否完全二叉树的思路代码，也是在层次遍历的代码上进行改造，进一步加深树层次遍历利用队列的代码写法。 　　3.关于二叉排序树的建立，先是创建空树，再根据序列，不断的调用插入函数，将序列中关键字一个个插入树中。 　　2.2 7-2 二叉搜索树的最近公共祖先 　　
　　
　　
　　
2.2.1该题的设计思路 　　首先本题给的先序序列，由于先序序列是根左右，重要的是根结点先遍历，因此我们仍然按照原有的插入结点方式建树即可 　　先调用常规查找函数，分别查找两个数是否在树中，判断是否特殊情况 　　难点在于判断祖先：递归判断结点 　　若要查找的两个结点分别在左右树，则该点就为他们的祖先 　　若都在左子树或都在右子树，说明还有离这两个点更近的祖先结点，则进一步递归查找。 2.2.2该题的伪代码 　　
主函数中先对两数的查找情况进行判断后，若都存在，则调用该寻找祖先函数 2.2.3PTA提交列表 　　
　　部分正确的是又两个测试点超时错误。 　　上课听了老师的讲解，关于调用函数的花费时间。因此判断只有在一开始查找两数是否都在树中时才需要调用，其后递归判断两树在左或在右，则直接根据二叉排序的特性，与其值比较即可 　　还有一些需要调用函数的条件判断句，就修改成用变量保存调用函数的结果，尽量减少调用次数，来节约时间 2.2.4本题设计的知识点 　　对于给定排序树的先序序列，我们判断出由于其顺序特殊性，可以直接按照原插入方式进行插入，联系了二叉排序树的插入和建立 　　再次使用回顾了二叉排序树的查找，来先判断具体题目的特殊情况 　　对二叉排序树的结构有了更深的理解，关于祖先结点。查找两个数的祖先结点的结构特点，结构关系，并且利用递归函数来写。 　　2.3 7-5(哈希链) 航空公司VIP客户查询 　　
　　
　　
　　
　　
　　
　　
2.3.1该题的设计思路 　　利用哈希链表来存储这些会员信息 　　利用ID来设计哈希地址： 　　若是ID中部分相同的则可能得到哈希地址相同的情况，这时我们同样通过ID来判断是否同个会员。同哈希地址的不同会员就插入该链 　　（注意：我们虽然是将每条会员记录都创建一个新的结点，但若是相同用户，并不是插入，而是将其他数据项（飞行里程）叠加，只要不同会员才插入） 　　如图所示，同一个会员只有在表中一个结点，同哈希地址链中的结点ID一定不同 　　
　　该题的输入输出用scanf,printf. 2.3.2该题的伪代码 　　本题多个函数套用，大多为哈希链的基本操作函数，这里主要介绍一个查找插入位置的函数 　　UserList Findnode(UserList* User, char* id)//找到插入结点。主要解决同哈希地址，但id不同问题 　　{ 　　调用哈希地址GetAddress(id) ;//起始是哈希地址 　　p取链头 ; 　　} 这是个将查找和插入位置结合起来的函数，若找不到则遍历完后p->next=NULL,只要在其他函数中对此进行判断就能知道是找不到。而若找得到，循环直接结束返回地址，则找到到，需要进行叠加里程的结点即为p->next结点 2.3.3PTA提交列表 　　
　　之前一直超时过不了，后来将输入输出改成了scanf printf,提交才通过 　　关于查找判断是否存在的条件不够清晰，实际上就是根据哈希地址，在该链中遍历查找是否存在，若是一直遍历到空则说明查找不到。 　　想要达成查找同时返回插入结点，因此利用前驱指针遍历pre,返回插入位置后，根据指针pre->是否为空，就可判断是否找到了，若未找到也可直接插入到pre后面 2.3.4本题设计的知识点 　　主要就是关于哈希链的知识解题 　　如何根据具体题目设计计算哈希地:该题就是去ID中的几位数进行计算 　　如何创建哈希链：计算出哈希地址后，往该链查找，若不存在则插入，根据此题情景，若已存在则累计 　　如何利用哈希链解决冲突问题：哈希地址冲突，但ID不可能完全相同，我们就插在该链中。