- 博客(147)
- 资源 (2)
- 收藏
- 关注
RSS订阅原创 Java设计模式（25）：责任链模式（职责链模式）
25，责任链模式25.1，问题引入_采购需求采购员需要采购一批教学器材，对器材采购金额有分级审批权限如果金额小于等于3000元，由教学主任审批（0 < x <= 3000）如果金额小于等于10000元，由院长审批（3000 < x <= 10000）如果金额大于10000元，由校长审批（x > 10000）在传递方案中，拿到采购金额后，根据金额不同，推送到不同的处理人进行处理客户端需要进行更多的逻辑分支处理，调用不同的审批人进行审批如果各个级别的审批金
2020-12-22 09:29:15
306
1
原创 Java设计模式（24）：策略模式
24，策略模式（Strategy）24.1，问题引入_鸭子问题有各种鸭子（如：北京鸭，野鸭，玩具鸭），鸭子存在各种行为（如：叫，游泳，飞行等）。需要做一个程序，显示鸭子的各种信息在传统方案中，通过定义一个抽象的 Duck 类，用具体鸭子类继承该类，进行相对应的行为实现首先：通过继承，会让所有具体鸭子类有共同是行为方式，这是明显不合适的其次：通过方法重写，为不同的鸭子实现不同的实现方式，这样需要覆盖所有的实现方法可以通过策略模式进行解决24.2，基本介绍策略模式（Strategy Pat
2020-12-22 09:29:11
247
1
原创 Java设计模式（23）：状态模式
23，状态模式23.1，问题引入_APP抽奖活动提供一种抽奖活动，每一次抽奖扣除用户50积分，且中奖概率为10%，奖品数量固定，送完为止活动存在四种状态：不能抽奖：未进行积分兑换可以抽奖：已经进行积分兑换。抽奖完成后，如果未中奖，转到不能抽奖；如果中奖，转到发放奖品发放奖品：对中奖用户发放奖品。奖品发送后，如果还有剩余奖品，转到不能抽奖；如果奖品已经送完，转到奖品领完奖品领完：奖品全部领完这种需求可以通过状态模式完成23.2，基本介绍状态模式（State Pattern）：主
2020-12-22 09:29:07
307
1
原创 Java设计模式（22）：解释器模式
22，解释器模式（Interpreter）22.1，问题引入_计算器问题在界面输入计算表达式，如：a+b+c+d，然后针对每一个元素输入具体值并保存，对该表达式进行填充求值，得到结果在固有表达式中，如果需要加入新的运算符，如* / （）等，可能会造成功能扩展困难此时可以考虑引入解释器模式，对运算符等进行隔离，对每一种类型进行单独的解释计算22.2，基本介绍在编译原理中，一个算术表达式通过词法分析器形成词法单元，而后这些词法单元再根据语法分析器构建语法分析树，最终形成一颗抽象的语法分析树。这
2020-12-22 09:29:00
175
1
原创 Java设计模式（21）：备忘录模式
21，备忘录模式（Memento）21.1，问题引入_游戏角色恢复问题游戏角色有攻击力和防御力，在大战BOSS前保存自身的状态，当大战BOSS后攻击力和防御力下降，从备忘录中恢复初始状态在传统方式中，new对象简单做备份，再需要恢复数据时，从新对象中取初始数据进行覆盖，这样会暴露对象的内部实现细节这时候可以通过备忘录模式实现21.2，基本介绍备忘录模式（Memento Pattern）：行为型模式；在不破坏封装性的前提下，捕获一个对象的内部状态，并在该对象之外保存这个状态，以便于在后续对该
2020-12-19 14:20:21
109
1
原创 Java设计模式（20）：中介者模式
20，中介者模式（Mediator）20.1，问题引入_租房中介在一个租房者去市场上租房的时候，面临的是众多的被租房子，及每一套房子后面的房东首先，租房者需要跟每一个房东打交道，去确认房子，去议价其次，房东间可能也会存在沟通，形成一张沟通网在整个沟通过程中，各方都会很累，没有效率，此时需要一个承上启下的角色存在，就是租房中介这就可以用中介者模式进行处理20.2，基本介绍中介者模式（Mediator Pattern）：是行为模式的一种。用一个中介对象，封装一系列的对象交互（发送东）。中介
2020-12-19 14:17:34
177
2
原创 Java设计模式（19）：观察者模式
19，观察者模式（Observer）19.1，问题引入_天气预报问题气象站可以将每天测量到的温度、湿度、气压等发布出去，发布到自己的页面或者第三方系统发布的形式可以采用两种方式：修改数据等待获取和直接数据推送在进行数据推送时，需要明确对端系统，然后在变更时调用对端接口进行数据修改对端系统肯定是不确定多个，并且随时可能存在增减，如何对多系统进行管理，并进行数据推送，可以使用观察者模式19.2，基本介绍观察者模式（Observer Pattern）：是解决对象间关系一对多依赖的一种设计方案。
2020-12-19 14:15:44
120
1
原创 Java设计模式（18）：迭代器模式
18，迭代器模式（Iterator）18.1，问题引入_学校体系结构在 组合模式 中引入了学校体系结构，并通过 List 集合对各个层级进行定义，可以很方便的对整个结构进行遍历但是如果各个层级的下属部门集合不一定都是用 List 集合定义，而是通过 Set，array 或者其他自定义方式进行存储，那就没有一个统一的方式进行结构遍历此时可以引入迭代器模式进行统一18.2，基本介绍迭代器模式（Iterator Pattern）是一种常用的设计模式，属于行为型模式如果我们的集合是通过不同的方式
2020-12-19 14:13:57
124
1
原创 Java设计模式（17）：访问者模式
17，访问者模式（Visitor）17.1，问题引入_账本查看财务系统是存在财务账本，财务账本有很多分类，而其中大体可以分为两种：支出和收入查看账本的人也分为好几种：老板，注会等等，每一个人查看账本的目的也是不相同的这时候对有多个固定元素的账本和多个角色的访问者，可以考虑使用访问者模式17.2，基本介绍访问者模式（Visitor Pattern）：封装一些作用于某种数据结构的各元素操作，可以在不改变数据结构的前提下定义作用与这些元素的新的操作主要是将数据结构（元素）与数据操作（访问者）分
2020-12-19 14:03:27
116
1
原创 Java设计模式（16）：命令模式
16，命令模式（Command）16.1，问题引入_智能生活项目需求假如有一套智能家电，照明灯、风扇、空调、冰箱、洗衣机等，需要在手机上安装APP进行控制这些智能家电来自不同的厂家，每一个厂家针对设备都有不同的APP，但是我们不想下载那么多的APP，希望通过一个APP进行全控制，如万能遥控要实现一个APP控制所有智能家电的需要，则各个智能家电需要一个统一的接口提供给APP使用，这时候可以考虑命令模式命令模式可以将 动作的请求者 从 动作的执行者 对象中解耦出来在这个例子中：动作的请求者是手机A
2020-12-19 14:00:26
124
1
原创 Java设计模式（15）：模板方法模式
15，模板方法模式（TemplateMethod）15.1，基本介绍模板方法模式（Template Method Pattern），在一个抽象类中公开定义执行它的方法的模板。子类中可以按需重写相关方法进行自定义，调用则通过抽象类以多态的形式进行。简单来说，模板方法模式定义了一个算法骨架，将一些步骤的实现延伸到子类中，使得子类可以不改变算法结构，但能重定义算法中的某个步骤15.2，类图定义顶层抽象类：CommonTemplate，在该抽象类中定义算法骨架，对公共的部分进行公共实现，对需要子类
2020-12-19 13:57:14
134
1
原创 Java设计模式（14）：代理模式
14，代理模式（Proxy）14.1，代码模式基本介绍代理对象为对象提供一个中介，以控制对这个对象的访问，即通过代理对象去访问目标对象被代理的对象可以是远程对象，开销大的对象或者是需要安全控制的对象代理模式有不同的形式，大体可以分为三种：静态代理，JDK动态代理（接口代理）和CGLIB动态代理（不需要接口）对象被代理后，可以在目标对象现有的基础上，增加额外的功能操作，即对现有目标对象的扩展。如执行前后日志打印，方法鉴权等等，是AOP的基本思想14.2，静态代理14.2.1，基本介绍静态
2020-12-19 13:32:41
117
1
原创 Java设计模式（13）：享元模式（蝇量模式）
13，享元模式（FlyWeight）13.1，问题引入13.1.1，展示网站项目需求 小型的外包项目，给客户A做一个产品展示网站，客户A的朋友觉得效果不错，也需要这样的产品展示网站，但是需求有些变化：有客户要求以新闻的形式发布有客户要求以博客的形式发布有客户要求以微信小程序的形式发布13.1.2，传统方式解决网站项目直接将项目复制一份，根据不同客户的需求，进行定制化修改13.1.3，问题分析需要的网站相似度很高，而且都不是高访问量网站，如果分成多个虚拟机进行部署，相当于一
2020-12-19 13:32:32
119
1
原创 Java设计模式（12）：外观模式
12，外观模式（Facade）12.1，问题引入_家庭影院组建一个家庭影院，需要准备屏幕，投影仪，灯光。此时看一场电影的大概过程为：放下屏幕，打开投影仪，调暗灯光；等电影看完后，大致过程为：调两灯光，关闭投影仪，收回屏幕。此时如果不进行各种模式统筹管理，在实际操作中，需要通过三个开关对三种设备进行单独控制。如果设备过多，会造成过程混乱，还有可能出现顺序（逻辑）错误这时候可以引入外观模式，通过外观类，进行具体操作流程进行管理，面向客户端只包括打开，关闭等基本操作，提高用户体验12.2，基本介绍
2020-12-19 13:32:23
122
1
原创 Java设计模式（11）：组合模式
11，组合模式（Composite）11.1，问题引入_学院系统展示一个学校的体系结构，一个学校有多个学院，一个学院有多个专业11.2，基本介绍组合模式（Composite），又叫部分整体模式，属于结构性模式，创建了对象组的树形结构，将对象组合成树状结构以表示整体—部分的关系组合模式使得用户对单个对象和组合对象的访问具有一致性，即组合模式能让客户以一致的方式处理单个对象和组合对象11.3，类图顶层抽象类：OrgComponent，定义了组合模式中的强一致类型，并提供了基本属性和方
2020-12-18 17:32:08
121
1
原创 Java设计模式（10）：装饰者模式
10，装饰者模式（Decorator）10.1，问题引入10.1.1，星巴克咖啡订单项目咖啡种类：Espresso（意大利浓咖啡），LongBlack（美式咖啡），Decaf（无因咖啡）调料：Milk（牛奶），Soy（豆浆），Chocolate（巧克力）要求在增加新的咖啡时能有更好的扩展性，改动方便，维护方便使用OO计算不同种类咖啡的价格：包括咖啡价格和调料价格10.1.2，方式一：穷举类方式Drink：是顶层抽象类，表示饮品，price是咖啡价格， description是对咖啡的
2020-12-18 17:30:15
170
1
原创 Java设计模式（9）：桥接模式
9，桥接模式（Bridge）9.1，问题引入_手机类型现在对不同类型不同品牌的手机实现操作编程，如下手机外观类型和对应品牌：则需要编写的代码类图可能如下：带来的问题如下：如果我们需要添加一个手机，则需要在各个类型下添加手机如果我们需要添加一个品牌，则需要在该品牌下添加各个类型的手机这样会造成基本的类爆炸，可以使用桥接模式对实现（手机品牌）和抽象（手机类型）分别进行向上抽取，通过抽象依赖实现的方式增强代码维护性9.2，基本介绍桥接模式是指将实现和抽象放在两个不同
2020-12-18 17:23:27
167
2
原创 Java设计模式（8）：适配器模式
8，适配器模式（Adapter）8.1，基本介绍适配器模式是将某个类的接口转换为客户端期望的另一个接口表示，主要目的是兼容性，让原本不能工作的接口经过一次转换适配后可以正常工作适配器属于结构性模式主要可以分为三类：类适配器，对象适配器，接口适配器[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-0oaPgGaj-1608282459295)(E:\gitrepository\study\note\image\designMode\1595824104472.
2020-12-18 17:09:07
158
1
原创 Java设计模式（7）：建造者模式
7，建造者模式（Build）7.1，基本介绍建造者模式（Builder Pattern）是一种对象构建模式，可以将复杂对象的建造过程抽象出来，使这个抽象过程的不同实现过程可以构造出不同的对象建造者模式是一步一步创建一个复杂的对象，它允许用户只通过复杂对象的类型和内容就可以创建它们，用户不需要知道具体的构建细节在JDK中的应用：StringBuilder7.2，四个基本角色Product：产品角色，一个具体的产品类AbstractBuilder：抽象建造者，抽取一个向上的抽象类，定义具体产
2020-12-18 17:03:29
169
原创 Java设计模式（6）：原型模式
6，原型模式（Prototype）6.1，基本介绍原型模式是通过原型实例指定创建对象的种类，并通过拷贝这些原型，创建新的对象原型模式是一种创建型设计模式，允许通过一个对象再创建一个可定制的对象，且不用对外暴露创建过程原型模式拷贝对象的方式，分为浅拷贝和深拷贝两种：浅拷贝通过JDK提供的API可直接进行处理，只会改变外部对象的地址，对内部引用对象地址不会改变深拷贝需要通过一些其他途径，如序列化，递归拷贝等，关联对内部引用对象地址进行改变，新对象与原对象不会再有任何联系在Spring中的使
2020-12-18 16:57:54
138
1
原创 Java设计模式（5）：工厂模式
5，工厂模式（Factory）工厂模式在逻辑上可以分为三种：简单工厂模式，工厂方法模式和抽象工厂模式。其中简单工厂模式不属于23种设计模式。从实际中理解三种工厂模式，大致可以理解为工厂发展的三个阶段，下面将从一个专营炸鸡，汉堡，可乐的小店说起，可能不是很具体，但就是那么回事5.1，简单工厂模式5.1.1，基本介绍简单工厂模式属于创建者模式，是工厂模式的一种，由一个工厂对象决定建出哪一种产品类的实例。简单工厂模式是工厂模式家族中最简单使用的模式简单工厂模式：定义了一个创建对象的类，由这个类来
2020-12-18 16:44:50
85
1
原创 Java设计模式（4）：单例模式
4，单例模式（Singleton）4.1，单例模式基本介绍所谓单例模式，就是通过一定的方式保证在系统中，对某一个类只存在一个对象实例，并且该类只提供一个获取该对象的方法（静态方法）单例模式创建方式比较多，目前大致可以分为五类八种，后面为一一分析，其中标红表明不可取方式，分别如下：饿汉式：静态常量，静态代码块懒汉式：线程不安全方式，同步方法，同步代码块双重检查方式（推荐）静态内部类方式（推荐）枚举方式（推荐）4.2，饿汉式_静态常量&静态代码块4.2.1，代码示例
2020-12-18 16:12:42
88
1
原创 Java设计模式（2）：UML类图
2，UML类图2.1，类关系（Dependency）依赖，泛华（继承），实现，关联，聚合和组合2.2，依赖关系依赖关系介绍成员变量可以作为类依赖关系返回值可以作为类依赖关系方法参数传递可以作为类依赖关系局部变量定义可以作为类依赖关系凡是在该类中出现的其他类，都可以作为该类的依赖类依赖类是关联关系最弱的关系，只要在类中有出现其他类，都可以首先定义为该类的依赖类代码示例package com.self.designmode.uml.dependency;/**
2020-12-18 15:50:45
135
原创 Java设计模式（1）：设计模式的七大原则
1，设计模式的七大原则1.1，设计模式的目的在程序编写过程中，程序员面临着耦合性，内聚性以及可维护性，可扩展性，重用性，灵活性等多方面的挑战，设计模式就是为了让软件，可以更好的满足上面的标准代码重用性：相同功能的代码，不用多次编写代码可读性：编程规范性，便于其他程序员对代码的阅读和理解可扩展性：当需求变更，需要增加新的功能时，能最小改动，最快时间实现可靠性：增加新的功能时，对现有功能没有影响通过设计，使程序呈现出高内聚，低耦合的特性1.2，设计模式的七大原则单一职责原则接口隔离原则
2020-12-18 15:38:56
182
1
原创 骑士周游（马踏棋盘）问题
1，马踏棋盘算法介绍马踏棋盘问题也被称为骑士周游问题将马随机放在国际象棋的8*8的棋盘中的某个格子里，马按照走棋规则（日子）进行移动。要求每个方格只进入一次，走遍64个方格2，马踏棋盘算法思路分析马踏棋盘算法是对图的深度遍历优先（DFS）的使用，通过递归加回溯实现对问题的解决，同时可使用贪心算法对最终算法进行优化从一点出发，对该点标记为已访问，并寻找该点通过日子走法，下一步可能访问的点坐标的集合如果存在对应的点坐标集合，并且存在点未访问，则按顺序对集合中的未访问坐标点进行递归访问，即重复
2020-07-18 22:28:06
1347
原创 弗洛伊德（Floyd）算（F算法）— 最短寻径问题
1，应用场景—最短寻径问题弗洛伊德算法与迪杰斯特拉算法解决问题完全一致，这是解题思路不同2，弗洛伊德算法介绍和迪杰斯特拉（Dijkstra）算法一样，弗洛伊德（Floyd）算法也是一种用于寻找加权图中顶点间最短路径的算法，该算法创始人为1978年图灵奖获得者罗比特 · 弗洛伊德与迪杰斯塔拉算法不同的是：迪杰斯特拉算法基于一个给定的出发顶点，求出该顶点到其他顶点的最短距离；弗洛伊德算法将每一个顶点作为出发顶点，所以需要求出每一个顶点到其他顶点的最短路径；迪杰斯特拉算法最后给出的结果是一个一维
2020-07-18 22:25:24
1999
原创 迪杰斯特拉（Dijkstra）算法（D算法）：最短寻径问题
1，应用场景—最短寻径问题如图，存在7个村庄['A', 'B', C', 'D', 'E', 'F', 'G']，现在有6个邮差，从G点出发，需要分别赶往['A', 'B', C', 'D', 'E', 'F']六个村庄各个村庄的距离通过边的权值表示，如A <-> B = 5问：如何计算G村庄到其他村庄的最短距离注意：之前两篇说的普里姆算法和克鲁斯卡尔算法，都是求图内连接各个节点的最短路径；该问题是从一点出发，到各个顶点的最短路径。注意，此处是到各个顶点，不是总和的最短路径2，迪
2020-07-18 22:15:54
718
原创 克鲁斯卡尔（Kruskal）算法（K算法）：公交站问题
1，应用场景—公交站问题某城市从新增的7个站点（A，B，C，D，E，F，G），现在需要把7个站点联通各个站点的距离用边权表示，比如A-B为12公里如何修路保证各个站点都能走通，并距离最短从图和问题可以看出，克鲁斯卡尔算法与普里姆算法解决的问题完成一致，只是解决问题的方式不同2，克鲁斯卡尔算法介绍克鲁斯卡尔算法，是用来求加权连通图的最小生成树的算法基本算法思想：按照边权值大小从小到大的顺序选取n - 1条边，并保证这n - 1条边不构成回路回路的判断标准是连接边的两个顶点的终点重合
2020-07-18 22:10:21
1072
原创 普里姆（Prim）算法（P算法）：修路问题
1，应用场景—修路问题如图，此时有7个村庄['A', 'B', 'C', 'D', 'E', 'F', 'G']，现在需要把这7个村庄连通村庄之间的连接线表示可能修路的图示，权值表示举例此时，如果想要把7个村庄连通，怎么才能让连接的路程最短？此时应该尽可能的寻找少的线路，保证每条线路最短，最终达到整体线路最短（该部分有点类似贪心，但是贪心的最终结果不一定是最优解）2，最小生成树问题修路问题本身就是最小生成树（Minimum Cost Spanning Tree）问题，简称MST：给定一个
2020-07-18 22:07:10
2604
原创 贪心（Greed）算法：电台覆盖问题
1，应用场景—集合覆盖问题假设存在下面需要付费的广播电台，以及广播电台可以覆盖的地区。如何选择最少的电台，能实现区域的全覆盖2，贪心算法介绍贪心算法（贪婪算法）是指在对问题进行求解时，在每一步的选择中都选择最优解，从而期望能够导致结果是最优解的算法贪心算法所得到的结果不一定是最优解，但是一定是相对近似最优解的结果3，贪心算法最佳应用演示—集合覆盖问题已知存在多少电台，及电台对应的覆盖城市集合；并且各个电台所覆盖城市存在部分重复，需要最少几部电台可实现全覆盖首先汇总需要覆盖的城市，取
2020-07-18 22:04:42
580
原创 KMP算法：字符串匹配问题
1，暴力匹配算法1.1，基本介绍暴力匹配算法是对字符串及匹配子串的字符进行一一匹配，完全匹配后则说明字符串匹配假设存在字符串str和子串childStr，需要进行字符串的暴力匹配，才从头开始匹配此时取字符串str的索引位置i = 0，子串childStr的索引位置j = 0，用str[0]和childStr[0]进行比较，如果匹配，则进行i++, j++，并依次进行下一个字符匹配此时如果不匹配，说明i = 0处起始匹配是匹配不到的，则进行回溯，重新从i = 1处开始重复以上逻辑进行匹配但是此时
2020-07-18 22:03:00
217
原创 动态规划算法：背包问题
1，应用场景：背包问题问题描述：有一个容量为4磅的背包，需要装入如列表下的物品，在装入物品可重复和不可重复两种场景下，怎样才能使装入机制最大化商品名称商品重量商品价格吉他11500音响43000电脑320002，动态规划算法描述动态规划算法（Dynamic Programming）核心的思想是：将大问题划分为小问题进行解决，从而 一步步 获得最优解的处理算法（这个一步步是重点，等会就发现真是一步步）动态规范算法和分治算法类似，基本思想都是将待
2020-07-18 21:54:42
1114
原创 分治算法：汉诺塔问题
1，基本介绍分治算法是一种重要的算法。基本思想就是“分而治之”，将一个复杂的问题分为多个相似的子问题，然后再把子问题分为更小的子问题，直到最后子问题可以以一种最简单的方式直接求解，原问题的解即为子问题解的合并。分治算法的一些经典算法如：二分搜索，棋盘模型，合并排序，快速排序，汉诺塔等，以下将用汉诺塔举例2，基本步骤分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题解决：如果子问题规模较小，则直接求解；如果规模较大，则递归求解合并：将各个子问题的解合并为主问题的解3，汉
2020-07-18 21:49:26
298
原创 图：深度优先遍历&广度优先遍历
1，图的基本概念1.1，图的基本介绍线性表局限于一个直接前驱和一个直接后继的关系树也只能有一个直接前驱也就是父节点当需要多对多的关系的时候，就应该用到图1.2，图的常用概念顶点（Vertex）边（Edge）路径无向图有向图带权图1.3，图的表达方式图的表示方式有两张：二维数组表示（邻接矩阵），链表表示（邻接表）邻接矩阵：是表示图形中顶点之间相邻关系的矩阵，对于N个顶点的图而言，矩阵的row和column分别表示n个点邻接表邻接矩阵需要为每个顶点分配n个边的空
2020-07-18 21:43:15
193
原创 多路查找树
1，二叉树问题分析二叉树添加到内存中后，如果二叉树的节点少，那没有什么问题。但是如果二叉树的节点很多，在构建二叉树时就需要进行多次I/O操作，同时也会造成二叉树的高度很大，降低操作速度2，B树（2-3树，2-3-4树）2.1，B树基本介绍B树通过重新组织节点，降低树的高度，从而提高操作效率文件系统及数据库系统的设计者利用磁盘预读原理，将一个节点的大小设置为页的倍数（4K的倍数，MySQL一个节点为4页），这样每一个节点只需要一次I/O就可以完全载入将树的度M设置为1024，600E元素最多
2020-07-18 21:36:54
306
原创 树：红黑树
1，红黑树引入红黑树是对AVL树的补充。AVL树要求整个树的高度差不能超过1，超过后需要进行左旋或者右旋操作再次对树进行平衡，虽然这样能够解决二叉树退化为链表的缺点，将查询的时间复杂度控制在O(logN)，但却不是最佳的；因为AVL树对高度差的控制太严，在需要频繁进行插入/删除的场景中，AVL需要频繁进行树平衡调整，影响整体性能，为了解决这个问题，引入红黑树2，红黑树性质性质1：每个节点要么是黑色，要么是红色性质2：根节点是黑色性质3：每个叶子节点(NIL)是黑色，NIL表示虚拟节点性质4
2020-07-18 21:30:23
196
原创 树：平衡二叉树
1，二叉排序树问题对于一个有序数组{1, 2, 3, 4, 5}，其生成的二叉排序树如下；由图可见，最终形成一个类似单链表形式的二叉树，对插入速度没有影响，但是对于查询速度明显减低，不能通过BST进行查询，时间复杂度为O(n)；需要对二叉排序树这种现象进行优化，则引入平衡二叉树(AVL)2，平衡二叉树基本介绍平衡二叉树也叫平衡二叉搜索树(self-balancing binary search tree)，又被称为AVL树，可以保证较高的二分查找效率平衡二叉树特点：是一颗空树或者左右子树的高
2020-07-18 21:09:50
132
原创 树：赫夫曼树&赫夫曼编码
1，赫夫曼树1.1，赫夫曼树基本介绍及相关概念给定n个权值作为n个叶子节点，构造一颗二叉树，若该树的**带权路径长度(WPL)**达到最小，称这样的的二叉树为最优二叉树，也称为赫夫曼树，或者哈夫曼树、霍夫曼树赫夫曼树是带权路径长度最短的数，权值较大的节点离根较近路径和路径长度：在一棵树中，从一个节点往下可以达到的孩子和孙子节点之间的通路，称为路径；通路中分支的数量称为路径长度；若规定根节点的层数为1，则从根节点到第L层节点的路径长度为L - 1节点的权及带权路径长度：若将树中的节点赋给一个有意义
2020-07-18 21:03:24
417
原创 树：线索化二叉树
1，线索化二叉树基本介绍线索化二叉树是对普通二叉树的扩展，对于普通二叉树而言，一个节点会包含一个数据域以及指向左右子节点的位置索引；但是对于叶子节点来讲，左右子节点的位置索引并没有被利用到，线索二叉树充分利用该部分节点，普通二叉树如下：在n个节点的二叉树中总共含有n - 1（类似5指向2表示一个位置指向）个位置指向，即2n（每一个节点有左右两个指针域）个指针域，这样对于一个二叉树来讲，共有2n - (n - 1) = n + 1个空指针域。利用二叉树的空指针域，根据前/中/后序不同遍历方式存储前驱节
2020-07-18 20:50:53
420
原创 树：顺序存储二叉树
1，线索化二叉树基本介绍顺序存储二叉树是堆排序的基本思想从数据存储来看，数组存储方式和树的存储方式可以相互转换，即数组可以转换为树，树也可以转换为数组，如下图所示顺序存储二叉树只考虑完全二叉树，并且元素间存在函数对应关系第n个元素的左子节点为：index = 2 * n + 1第n个元素的右子节点为：index = 2 * n + 2第n个元素的父节点为：index = （n - 1）/ 2其中n表示在完全二叉树中的第几个元素，同时也表示数组中的索引下标，从0开始2，代码实现p
2020-07-18 20:41:52
431
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人