当前位置：首页 > news >正文

六安网站软件建设做50个网站

news 2026/4/8 22:58:34

六安网站软件建设,做50个网站,wordpress主题如何修改语言,怎样查找企业联系方式文章目录传送门前言树#xff08;重点#xff09;树的数据结构定义性质二叉树的数据结构定义性质储存结构二叉树算法先中后序遍历层次展开法递归模拟法层次遍历遍历序列逆向构造二叉树线索二叉树#xff08;难点#xff09;定义线索化的本质二叉树线索化线索二叉树中… 文章目录传送门前言树重点树的数据结构定义性质二叉树的数据结构定义性质储存结构二叉树算法先中后序遍历层次展开法递归模拟法层次遍历遍历序列逆向构造二叉树线索二叉树难点定义线索化的本质二叉树线索化线索二叉树中找前驱后继中序先序后序树算法储存结构树和森林的遍历树遍历森林遍历树应用哈夫曼树并查集数据结构优化并集控制高度查集压缩路径传送门思维导图精炼的个人思考前言数据结构的笔记相比于其他3门笔记的重要性要低很多毕竟对于选择408的同学来说大二时候应该有足够的时间学习所以基础是比较好的再加上csdn上一大堆数据结构和算法的帖子我再重复造轮子也没啥意思了。所以我这篇文章不打算写的很细节就是单纯地把思路提纯出来并附上自己深入的理解再搭配思维导图就行了而不去记录过于细节的知识。树重点树的数据结构定义除了根节点任何节点有且仅有1前驱根节点0前驱n后继分支节点1前驱n后继叶节点1前驱0后继节点之间的关系祖先/子孙所有有血缘关系的前辈/子孙。注你叔和你没血缘关系所以不算祖先父亲/孩子直接血缘关系的上下层节点兄弟/堂兄弟在树的同一层区分点在于是否是同一个爹生的术语高度从下往上数叶节点是1深度从上往下算根节点默认是1节点的度分支数在图里要分入度出度树的入度确定所以不讨论叶节点度0非叶节点度≠0 树的度最大的节点度性质每个度代表分出一个节点所以n个度即分出n节点考虑到1个根节点即n1个节点。不需要考虑重复因为每次分支都是实实在在的后面再分支也不会影响现在已经分出去的节点度为m的树是m叉树树度≤m的特例树度m至少有一个为m度节点因此至少有m1个节点给定深度/高度后的最多节点数。满度m叉树满度情况下每层节点数是以1开头m为比的等比数列总和用等比数列求和给定深度/高度后的最少节点数 m叉树度没有下限为了满足高度极限情况需要有一条线即h个节点度为m的数在满足高度的一条线前提下还要找一个节点额外分m-1个节点所以hm-1 给定节点数求最小高度。列不等式下界n≤上界变形后可以得到h的范围。二叉树的数据结构定义二叉树是一个纯粹的递归定义二叉树只有两种状态空树非空根节点左右子树左右子树也可以是空树或者非空左右之分代表有序具体来讲有5种细分状态空叶节点度0单个孩子的节点度1两个孩子的节点度2 通过度就可以区分节点的状态后面说的所谓度为几其实就是说xx状态的节点。完全二叉树节点是从上到下从左到右连续排列的没有空隙满二叉树最后一层是满的完全二叉树直接特性就是如果n层有节点代表n-1层一定是排满的且n层这个节点左边也是排满的接下来解读二者差别度分析 n1层无节点因此n层所有节点度0完全二叉树 n-2层开始往上都满度。n层有节点说明n-1层满从n-2层开始往上都是满度2的n-1层可能有0,1,2三种度从左到右先是一排2度然后仅有一个1度然后全是0度。如果有两个1度就会打破完全二叉树连续排列的定义。总结n-2层往上全满n-1层可能有任何类型节点n层全是叶子满二叉树n层满因此n-1层往上都是满度父子关系。左孩子2i右孩子2i1父亲是孩子除以2向下取整结合1,2来定位完全二叉树的1度节点。 1度节点肯定是最后一个孩子的父亲直接除二向下取整1度和2度节点都是分支节点0度节点是叶节点。性质二叉树推导 n0n21 推导nn0n1n2节点总数且nn12n21节点总数总度数1减一下可得结果直观理解度1的节点不影响叶子结点数量。度2的节点每分叉一次都是浪费一个叶子结点同时生成两个叶子结点即最开始有1个叶节点根每分叉一次2度节点就会多一个叶节点因此最后n0n2分叉次数1根 2,3都是等比数列性质完全二叉树推导推导公式要从≤或者≥哪里去推导。因为上下界有两种理解方式所以就会有两种结果 2 h − 1 − 1 n ≤ 2 h − 1 2^{h-1}-1n≤2^h-1 2h−1−1n≤2h−1用右边的小于等于就可以推导出一个公式 2 h − 1 ≤ n 2 h 2^{h-1}≤n2^h 2h−1≤n2h用左边的大于等于也可以推导一个h公式给定完全二叉树的n可以彻底确定其形状节点的数量类型分布下面有三个方程联立就可以算出结果 nn0n1n2n0n21n1只可能是0或者1只需要看n奇偶就可以。n如果是偶数最后这个节点是独生子即其父为1度节点n11如果n是奇数说明这个节点有亲兄弟场上就不存在1度节点了。纵观这些公式关键在于几点完全二叉树对等比数列的认知对完全二叉树结构的认识第n-1层的度数排列左2中1右0分支带来的节点变化对应公式储存结构顺序存储先说完全二叉树首先是第一个元素不储存这样就可以把位序和下标对应简化代码和逻辑。其次就是找父子判断层次这些都是数量关系然后就是判断节点状态是0度还是1,2度 12度的区分这就需要结合n来判断看看其左孩子右孩子的位序是否越界n0度判断要先找到0度2度的分界点即n/2向下取整左边是2右边是0。至于这个节点本身就要区分12度了。一般的二叉树如果在数组中连续存储就会破坏位序关系如果按位序存储仍然有很多不便。一来节点状态无法通过n来判断了只能新增bool变量二来还会浪费空间因此二叉树其实一般是用链式结构储存的。链式储存假设有n个节点那么总共就有2n个链域除根节点外每有一个节点就会有一条边每条边都会占用一个链域总共n-1条边因此就会剩下2n-n-1n1个空链域这些链域可以用来逆向构建线索二叉树在只有两个链域的情况下找父节点要从根节点遍历比较麻烦因此要频繁查找父节点的话还应该加入parent链域。二叉树算法先中后序遍历所谓的先序其实是先根序层次展开法我此前是直接在脑子里去遍历就是在脑子里模拟递归调用栈虽然也能做但是费脑子不如下面的省劲逐层去展开就像是前面从中缀转前缀/后缀的时候先留出括号然后将未处理部分在下一层继续展开二叉树可以理解为一个代表中缀表达式的结构分支节点上是运算符叶节点是操作数树结构代表了运算先后顺序对其进行先序遍历就是把符号放在前面也就是前缀表达式后序就是后缀表达式。注意中缀的时候需要加括号之前我也写过一道这个算法题我记得大致是从层次里提取括号。递归模拟法至于递归代码就很简单了 T!NULL是判断条件如果空就不操作非空就进行遍历。 visit代表对根结点的访问根据前中后序遍历可以在对左右孩子的递归调用之间找到一个合适的位置。有的考题会让你分析递归过程前进回退其实无论是哪种遍历路径都是一模一样的每个节点都被经过三次算上左右孩子为空的情况刚到这个节点从左边返回从右边返回前中后序遍历的区别就在于是在哪一次经过的时候访问节点先序就是在1中序就是在2后序就是3到时候画一条路然后脑补在该访问的时候写出节点就好。需要注意NULL孩子也算孩子即使孩子为空也要象征性地访问一下一来是程序逻辑二来是为了你好写顺序。层次遍历思路很简单就是用队列。访问当前一层的时候把下一层可以加的孩子都按序加进来。直到最后队列为空遍历序列逆向构造二叉树前/后序中序的逻辑一样都是先找到根节点然后去中序里面切分对应回去将前/后序序列分割如此就完成了一段的切分然后递归地去切分剩下两段类似于快排的感觉。层序的话仍然是利用层序找根节点然后用中序切割。层序找根节点是从前往后以层为单位去找的那么每层要考虑几个根节点呢这就得看中序的切分情况了中序切分后该层所有根节点只要有孩子就1最终数量就是下次要考虑的根节点数目比如下图 DABD中序切分后左右非空因此一个节点分2个EFCGAB中序切分后AB节点左右都非空因此是22HIEFCG中序切分后只有CG有子节点C和G各有一个因此是11 又以下图为例 ABA因为中序左边没有因此是1CDB中序左右都有因此是2E 线索二叉树难点这一部分是难点需要深入理解先中后序的逻辑灵活利用展开的方法去分析并且还要熟悉在树上遍历的过程。定义线索化的本质首先这里区分一下这里说的前驱和后继都是特指在中序遍历序列中的前驱后继而不是二叉树上的前驱后继一般情况下我们遍历一颗二叉树一定要从根节点开始否则后面会有一些节点漏掉。比如下图要想找到p的中序前驱和中序后继要用q和pre指针进行一前一后的移动从根节点开始把整个树遍历一次。假如有一种情况需要反复利用中序遍历序列那么每次都从根节点获取中序遍历序列就很麻烦于是有人直接利用线索二叉树把中序遍历序列的信息储存到空链域里这就是线索化的本质。姑且不论线索如何生效你只知道利用线索就可以从中序遍历序列中的一个节点开始遍历出后面完整的中序遍历序列。在上图中完全可以从B开始就可以依次遍历BEAFC不用担心丢了某个节点。按这个思路按照线索可以直接遍历中序加速遍历甚至线索里本身就存着p在中序序列的前驱后继你直接输出就行。这就是线索化的意义下图为线索化的过程先遍历出一个中序序列然后把中序序列前驱后继的信息填充到线索里左对应前驱右是后继有n1个空链域因此有n1个线索。为了区分链域储存的到底是线索还是孩子需要用两个tag区分。此处疑惑的点是有的节点有后继但是没有链域存放后继这个后面有解决办法。你姑且知道有线索就可以从中提取中序的前驱后继下图为标准的储存结构图像先序和后序的思路同中序。二叉树线索化二叉树线索化本质就是把这个节点的左孩子链接到中序前驱右孩子连到中序后继。因此当务之急是在中序遍历的过程中维护前驱和后继信息其实在最开始已经说了就是用一个pre指针全局变量pre是q的前驱而q是pre的后继此乃相对性已经有信息了那么在visit过程中就直接修改链域就好判断条件 q一定非空所以只需要判断左链域而pre可能空所以还要都一个非空判断。添加线索如果链域为空就修改为对应的线索记得把tag同步修改。最后修补注意到最后一次visitq指向尾部而pre指向倒数第二也就是说q的后继是没有考虑的因此在程序执行完毕后还要额外判断pre的右链域全局变量的好处在此处体现。有些写法是直接让pre右链域NULLpre-rtag1的这种也没错因为在中序遍历里如果这个节点有右孩子那这个节点就不是最后一个节点了。但是在后序遍历里面最后一个visit的节点有可能有右孩子所以就不能这么个判断。总的来说加判断可以涵盖一切情况因此就统一加判断只有前序和中序情况下才可以不判断。下图为具体的代码左上角为主函数初始化preNULL然后线索化q就是从T开始最后再善后pre右链域先序线索化基本照搬就是在先序遍历的过程中去添加线索。但是这里有一个bug对于没有左孩子的节点比如D按道理说添加完线索以后就没他什么事情了而且访问过以后也没有机会再访问第二次了。但是在先序线索化过程中会先visit添加前驱线索之后左孩子的链域就非空了此时如果还按照原有逻辑就又会跳回到前驱开始进行遍历这就是一个死循环。破解办法很简单本来左孩子的链域应该是空的此时有了指针可以用tag来判断原来是否为空只有tag0原来非空真正的有左子树这才能跳转到左孩子的节点。线索二叉树中找前驱后继总评这一章是线索二叉树的核心难点尤其是三叉链表情况下的别扭题。我的建议是一切的一切要抓准先序中序后续的本质特性比如先序就是“根左右”你到时候现场推导判断条件灵活且不容易出错。中序之所以用中序为例子是因为中序线索化是完美的“左根右”有根节点找前驱就去左孩子里面找找后继就去右孩子里找而先序只能找后继后序只能找前驱。先说后继判断rtag两种情况 rtag1证明右链域是线索那么直接用线索rtag0证明右链域有右子树那么就需要找到右子树中序遍历序列中最左边的节点其实就是右子树左下角的节点具体就是下面FirstNode函数一直找左孩子直到没有左子树因为此时已经线索化了终止条件所以不再用NULL而是用ltag判断既然能找到中序后继一次快速的中序遍历就很简单了先通过FirstNode找到第一个节点然后从第一个节点开始不停找后继直到遍历完毕这种方法的特色在于找后继过程中可以通过线索大大加速遍历速度复杂度为O1 中序线索的前驱思路和后继一样整体是镜像的感觉左变右有前驱线索就用线索没有就找左子树右下角节点。 LastNode函数就是一直去找右孩子直到rtag1 因此也衍生出逆向遍历中序线索的方式。先序中序最为规整符合直观先序后序就比较别扭容易混乱本质上是先序会浪费链域比如本来就有左孩子然后你右链域如果为空还要再指向左孩子这就是浪费这也就是其前驱后继只能二选一的原因浪费了信息自然就无法实现全部的功能。回归正题先序找后继后序找前驱反之则不一定容易记混而且实际生产也没用要我说还不如深入理解临场画图更加保险先序找后继本质思路就是“根左右” rtag1有线索用线索rtag0无线索即有右孩子此时用“根左右”思考有左孩子则左孩子为后继无左孩子则右孩子为后继前驱不一定有逻辑如下 ltag1有线索用线索ltag0有左孩子问题在于遍历序列是“根左右”以根开始无论你找左孩子还是右孩子先序情况下只要你找的是孩子你顶天了只能是后继因此ltag0的时候只能从根开始遍历用不了线索但是很明显这里可以加考点如果用三叉链表允许找到父节点那么事情会有转机当然也特别麻烦为考而考一切的关键是理解先序遍历的根左右思想 ltag1用线索lgat0先找父节点情况1p无父节点则无前驱p有父节点有前驱然后进行判断。先看上层结构“根左右” 情况2p是左孩子则为“根根左右右”则父根节点为前驱p是右孩子p处在序列中“右”的位置则要判断“左这一部分的情况” 情况3“左”为空即“根根左右”那么父节点当前驱情况4“左”非空即“根左子树根左右”那么就要在父节点左子树里走一遍先序遍历用其最后一个节点当前驱。这一步要求你对先序遍历极其熟悉可以简化有右找右没右找左右左都没就是最后一个说实话真的有点大冰建议直接画图思考把这几种情况都画出来这么多背不会的。后序后序线索只能找前驱如果要找后继同样麻烦。后序前驱 ltag1用线索ltag0则有左孩子利用“左右根”寻找前驱有右孩子则为“左左右根根”因此右孩子就是前驱无右孩子则为“左右根根”因此左孩子就是前驱后续后继因为是“左右根”无法通过左右子树找根的后继同样需要三叉链表配合 rtag1用线索rtag0先找父节点情况1p无父节点则无后继p有父节点此时上一层为**“左右根”**我们这一层仍然需要先定位情况2p为右孩子则为左左右根根因此p的后继就是父节点p为左孩子因此要判断“右”这一部分是否存在情况3父节点无右孩子则为“左右根根”p的后继是父节点情况4父节点有右孩子则为“左右根左右根根”p的后继是父节点右子树后序遍历序列中第一个输出的节点简化逻辑就是有左就左没左找右没左没右就是后继再次吐槽真的是有大冰建议推导两三次就不用记了直接临场速推。树算法储存结构树的难点在于因为度是没限制的所以链域给几个是不确定的树的所有结构都是为了解决这个核心问题而创造的。最开始双亲表示法的思路出度不确定入度确定啊因此采用逆向指针链域1非根节点就可以保证有且只有1个前驱因为结构比较简陋因此一般用数组存也只能用数组存因为找孩子节点只能用遍历实现查增删如何实现呢增在最后增加元素就行删就是直接把链域抹-1就行但是更好的方法是把最后一个元素挪到这个位置覆盖因为这样可以缩减数组长度提高遍历速度。双亲表示是纯数组表示而孩子表示法是数组链表的混合存储结构其实就是图的邻接表结构用在了树上延续链域不确定的思路解决不确定的数量自然会想到链表因此用一串链表表示一个节点的所有孩子数组元素储存节点本身链表元素储存孩子的位置信息。链表元素可以看做是两类指针的结合体孩子下标算一个指针指向具体元素而链表next也是指针指向下一个链表元素。这个结构其实是图的结构优劣势这里就不讲了简单来说就是找孩子简单找双亲难。最后就是孩子兄弟表示法纯链式存储。纯链式存储怎么能解决链域不定的问题呢换个思路链域里不储存所有孩子的指针而是储存一个孩子右兄弟这样链域就固定为两个了可以用二叉树储存了。从视图来看新的二叉树就是就是原有的树顺时针旋转45°然后用孩子兄弟法重新连线后的结果。逆过来转换就是左转然后重新连线。为了防止出错可以用两种颜色的笔区分孩子链域和兄弟链域又或者你直接记住左分叉是孩子链域右分叉是兄弟链域就好。森林和二叉树只需要补兄弟边就好每一颗树的根合起来在同一层互为兄弟。之后就是经典的旋转转化了还原的时候几何上应该从右边开始画线一层一层往左边推。树和森林的遍历对应关系森林-树-二叉树二叉树是宇宙万法的尽头硬要你写代码的话一切代码都可以用二叉树实现。树遍历树只有先序和后序不存在中序的说法因为无法确定孩子数量所以干脆就不往中间排要么先访问再依次递归孩子要么先递归完孩子再访问。数的初始逻辑结构和其二叉树形态有所不同因此遍历序列也不相同对应关系树先序二叉树先序树后序二叉树中序森林遍历森林遍历涉及二层递归这里先简单理解下。先序还好主要是中序为什么树没有中序森林这里就是中序了呢因为可以以一个节点切分出两片森林这才可以把根节点放在中间即中序。理论上森林还有后序但是过于阴间就没有放出来。写代码的话比较复杂直接换个思路用效果等价森林先序每棵树先序遍历森林中序每棵树后序遍历实在考出来写代码也可以取巧先把森林转化为二叉树储存结构然后把森林的遍历等效到树的遍历再对标到二叉树的遍历比如森林中树后二叉树中这样也可以写代码。树应用哈夫曼树首先说带权路径长度WPLWeighted Path Length 一条路径的WPL经过的边数×终点权值一棵树的WPL所有叶节点的WPL 哈夫曼树就是WPL最小的二叉树给定一些带权叶节点这里首先定义一下树的总权值叶节点权值和构造一颗哈夫曼树过程如下所有叶节点构成一个集合合并找场上总权值最小的两棵树二合一并将树的总权值记录在根节点上循环2步骤直到集合中只剩一个元素哈夫曼树的特点如下 WPL最小。权值小的路径长权值大的路径短那么总共的WPL就被平衡下来达到最小。无歧义。初始节点最后只能成为叶节点中间结点无意义。哈夫曼树不唯一哈夫曼树的应用是可变长度编码权值可以理解为使用频率或者重要程度。重要的就应该放在上面以更少的消耗编码先按照权值构造哈夫曼树哈夫曼树获得编码如下图C最重要因此只用1个bitABD长度依次增加。这种不定长编码的问题在于可能会有歧义因为无法定长分节解析但是恰巧哈弗曼编码无歧义为前缀编码因此可以使用异步方式解析。如何解码呢其实就是把这一串序列送到哈夫曼树里面走到叶节点就解析一个字符然后下一个序列继续从根开始。这个过程其实就是一个FDA和编译原理有共同之处如此从概率来看最后编码和解码的总消耗都是最少的实际上不见得最少并查集数据结构并查集就是集合集合之间互不相交我们此处要用数据结构描述这种互不相交的关系。基于这个关系还应该实现两个基本功能查给定元素判断所属的集合这个操作说白了就是找根节点并合并两个集合直接让一颗树的根节点成为另一棵树的子节点就好这两种方法用双亲表示法都是最有效率的实现也很容易。其实也可以用链表我也做过链表的题但是因为链表找到头比较慢要On而树结构分叉高度大概只有OlogN查一次要的迭代次数更少因此时间效率上双亲表示法完胜现在唯一的技术难点其实就是如何用一个数组储存一个森林呢本质就在于要同时维持多个根节点但是这个问题其实不是问题因为不同的根节点可以通过下标来区分反正我们只有并查操作只需要找双亲所以这样储存完全没问题就这么简单粗暴。说白了把操作限制在并查就可以针对性的使用高效率的结构实现操作越复杂耗时越多还需要用更精巧复杂的结构来降低操作的损耗这是不变的道理优化并集控制高度优化效率就要分析复杂度。并集为O1改下指针就行查需要逆向迭代如果所有元素串成一条线那么最坏就是On反之如果平铺开来尽可能降低高度就可以提高效率。注意双亲法是树不限制孩子个数所以每次并集都是直接并到根节点上现在我们要优化这个过程仔细分析Union过程在把一颗高度为n的树插到另一颗树上时这颗子树算上根节点总高度其实是变成了n1。假如有三个节点ABC把C插到B上再把B插到A上总高度就是3 换个思路如果把C插到B然后把A插到B总高度只有2在第二次插入过程中总高度并没有变化。具体逻辑如下把矮树并到高树上就不会增加总高度若两树高度相同则并集会令高度1 但是呢我们对高度其实并没有一个衡量所以只能用挂载节点的数量元素数量来近似高度既然无法判断高矮判断大小也是可以的具体操作如下但是你以为这就完了吗如果你从离散的叶节点开始合并你会发现最后的长度无论如何都不会超过这个数即时间复杂度最好O1最坏都是OlogN 查集压缩路径前面说的是在并集过程中对于高度的优化现在进一步在查集的过程中进一步优化属实是脑洞大开令人拍案首先找到根节点保存根节点位置然后进行二轮回溯压缩路径从路径终点开始先保存父节点备用拆桥把当前节点挂载到根节点保存的父节点派上用场当做下一轮循环要调整位置的节点如此每次查询都可以进行一次压缩越查越快可以对抗并集导致的高度增加配合并集优化可以使得一般情况下高度维持在4以内牛逼。

查看全文

http://www.w-s-a.com/news/443162/