【坐在马桶上看算法】算法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项目如何开启https服务

《springboot项目如何开启https服务》:本文主要介绍springboot项目如何开启https服务方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录springboot项目开启https服务1. 生成SSL证书密钥库使用keytool生成自签名证书将

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库,它提供了各

springboot+dubbo实现时间轮算法

《springboot+dubbo实现时间轮算法》时间轮是一种高效利用线程资源进行批量化调度的算法,本文主要介绍了springboot+dubbo实现时间轮算法,文中通过示例代码介绍的非常详细,对大家... 目录前言一、参数说明二、具体实现1、HashedwheelTimer2、createWheel3、n

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