【坐在马桶上看算法】算法9:开启“树”之旅

2023-11-10 02:10

本文主要是介绍【坐在马桶上看算法】算法9:开启“树”之旅,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

我们先来看一个例子。

101116gr944pr21oug8lro.png

       这是什么?是一个图?不对,确切的说这是一棵树。这哪里像树呢?不要着急我们来变换一下。

100835alobvkhlozlk3ula.png

       是不是很像一棵倒挂的树,也就是说它是根朝上,而叶子朝下的。不像?哈哈,看完下面这幅图你就会觉得像啦。

100836yof5r93sf99coer5.png

       你可能会问:树和图有什么区别?这个称之为树的东西貌似和无向图差不多嘛。不要着急,继续往下看。树其实就是不包含回路的连通无向图。你可能还是无法理解这其中的差异,举个例子,如下。


100837qvf7y7bb9uqrjuhq.png        100837piei9iwrvvvergh9.png


       上面这个例子中左边的是一棵树,而右边的是一个图。因为左边的没有回路,而右边的存在1->2->5->3->1这样的回路。
       1、正是因为树有着“不包含回路”这个特点,所以树就被赋予了很多特性。
       2、一棵树中的任意两个结点有且仅有唯一的一条路径连通。
       3、一棵树如果有n个结点,那么它一定恰好有n-1条边。

       在一棵树中加一条边将会构成一个回路。树这个特殊的数据结构在哪里会用到呢?比如足球世界杯的晋级图,家族的族谱图、公司的组织结构图、书的目录、我们 用的操作系统Windows、Liunx或者Mac中的“目录(文件夹)”都是一棵树。下面就是“啊哈C”这个软件的目录结构。

C:\啊哈C
├─codes
├─core
│ ├─bin
│ ├─include
│ │ ├─ddk
│ │ ├─gdb
│ │ ├─gdiplus
│ │ ├─GL
│ │ └─sys
│ ├─lib
│ │ └─gcc
│ │ └─mingw32
│ │ └─4.7.1
│ │ ├─finclude
│ │ ├─include
│ │ │ └─ssp
│ │ ├─include-fixed
│ │ └─install-tools
│ │ └─include
│ ├─libexec
│ │ └─gcc
│ │ └─mingw32
│ │ └─4.7.1
│ │ └─install-tools
│ └─mingw32
│ ├─bin
│ └─lib
│ └─ldscripts
└─skin

假如现在正处于libexec文件夹下,需要到gdiplus文件夹下。你必须先“向上”回到上层文件夹core,再进入include文件夹,最后才能进入gdiplus文件夹。因为一棵树中的任意两个结点(这里就是文件夹)有且仅有唯一的一条路径连通。

       为了之后讲解的方便,我们这里对树进行一些定义。
       首先,树是指任意两个结点间有且只有一条路径的无向图。 或者说,只要是没有回路的连通无向图就是树。

       喜欢思考的同学可能会发现同一棵树可以有多种形态,比如下面这个两棵树。

100837y34w3tt3t3ttkt3a.png        100838hwwwoqwt08w8tstw.png

       为了确定一棵树的形态,在一棵树中可以指定一个特殊的结点――根。我们在对一棵树进行讨论的时候,将树中的每个点称为结点,有的书中也称为节点。有一个 根的树叫做有根树(哎,这不是废话嘛)。比如上方左边这棵树的树根是1号结点,右边这棵树的树根是3号结点。

       根又叫做根结点,一棵树有且只有一个根结点。根结点有时候也称为祖先。既然有祖先,理所当然就有父亲和儿子。比如上图右边这棵树中3号结点是1、6和7 号结点的父亲,1、6和7号结点是3号结点的儿子。同时1号结点又是2号结点的父亲,2号结点是1号结点的儿子,2号结点与4、5号结点关系也显而易见 了。

       父亲结点简称为父结点,儿子结点简称为子结点。2号结点既是父结点也是子结点,它是1号结点的子结点,同时也是4和5号结点的父结点。另外如果一个结点 没有子结点(即没有儿子)那么这个结点称为叶结点,例如4、5、6和7号结点都是叶结点。没有父结点(即没有父亲)的结点称为根结点(祖先)。如果一个结 点既不是根结点也不是叶结点则称为内部结点。最后每个结点还有深度,比如5号结点的深度是4。哎,终于�嗦完了,写的我汗都流出来了,没有理解的请看下面 这幅插图吧。

101124ky0n8mlglwn3vvnx.png

       说了这么多你可能都没有感受到树究竟有什么好处。不要着急,请看下回――二叉树。


       欢迎转载,码字不容易啊,转载麻烦注明出处

     【啊哈!算法】算法9:开启“树”之旅  http://ahalei.blog.51cto.com/4767671/1403823



转载于:https://my.oschina.net/58812/blog/726882

这篇关于【坐在马桶上看算法】算法9:开启“树”之旅的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/379798

相关文章

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

Java进阶学习之如何开启远程调式

《Java进阶学习之如何开启远程调式》Java开发中的远程调试是一项至关重要的技能,特别是在处理生产环境的问题或者协作开发时,:本文主要介绍Java进阶学习之如何开启远程调式的相关资料,需要的朋友... 目录概述Java远程调试的开启与底层原理开启Java远程调试底层原理JVM参数总结&nbsMbKKXJx

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

一文详解kafka开启kerberos认证的完整步骤

《一文详解kafka开启kerberos认证的完整步骤》这篇文章主要为大家详细介绍了kafka开启kerberos认证的完整步骤,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、kerberos安装部署二、准备机器三、Kerberos Server 安装1、配置krb5.con

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为

通俗易懂的Java常见限流算法具体实现

《通俗易懂的Java常见限流算法具体实现》:本文主要介绍Java常见限流算法具体实现的相关资料,包括漏桶算法、令牌桶算法、Nginx限流和Redis+Lua限流的实现原理和具体步骤,并比较了它们的... 目录一、漏桶算法1.漏桶算法的思想和原理2.具体实现二、令牌桶算法1.令牌桶算法流程:2.具体实现2.1

开启mysql的binlog日志步骤详解

《开启mysql的binlog日志步骤详解》:本文主要介绍MySQL5.7版本中二进制日志(bin_log)的配置和使用,文中通过图文及代码介绍的非常详细,需要的朋友可以参考下... 目录1.查看是否开启bin_log2.数据库会把日志放进logs目录中3.查看log日志总结 mysql版本5.71.查看

Python中的随机森林算法与实战

《Python中的随机森林算法与实战》本文详细介绍了随机森林算法,包括其原理、实现步骤、分类和回归案例,并讨论了其优点和缺点,通过面向对象编程实现了一个简单的随机森林模型,并应用于鸢尾花分类和波士顿房... 目录1、随机森林算法概述2、随机森林的原理3、实现步骤4、分类案例:使用随机森林预测鸢尾花品种4.1

idea如何开启菜单栏

《idea如何开启菜单栏》文章介绍了如何通过修改IntelliJIDEA的样式文件`ui.lnf.xml`来重新显示被关闭的菜单栏,并分享了解决问题的步骤... 目录ijsdea开启菜单栏第一步第二步总结idea开启菜单栏手贱关闭了idea的js菜单栏,花费了半个小时终于解决,记录并分享一下第一步找