数据结构与算法笔记(三)

数据结构中的树(Tree)与生活中常见的树?有些类似,可以类比为生活中的树?倒过来。示意图:

相关概念

每个元素称为「节点」,用来连线相邻节点之间的关系叫作「父子关系」。示意图:

其中,A 节点是 B 节点的「父节点」,B 节点是 A 节点的「子节点」。BCD 节点有同一个父节点 A,它们互称为「兄弟节点」。没有父节点的节点(E)称为「根节点」,没有子节点的节点(GHIJ)称为「叶子节点」或「叶节点」。

高度、深度和层

1. 节点的高度(Height):节点到叶子节点的最长路径;

2. 节点的深度(Depth):根节点到这个节点所经历的边的个数;

3. 节点的层数(Level):节点的深度 + 1;

4. 树的高度:根节点的高度。

示意图:

二叉树

树的结构有多种,其中最常用的是二叉树(Binary Tree)。

二叉树的每个节点最多有两个“叉”,也就是两个节点,分别为「左子节点」和「右子节点」。如图所示:

1. 左边的二叉树:一棵普通的二叉树;

2. 中间的二叉树:叶子节点全都在最底层,而且除了叶子节点外,每个节点都有左右两个子节点,称为「满二叉树」;

3. 右边的二叉树:叶子节点都在最底下两层,且最后一层的叶子节点都靠左排列,除了最后一层,其他层的节点个数都达到最大,称为「完全二叉树」。

二叉树的存储

两种方式:基于指针(或引用)的链式存储法,基于数组的顺序存储法

链式存储法:每个节点有三个字段,其中一个存数据,另外两个分别为指向左右子节点的指针。如图所示:

顺序存储法:根节点存储在下标为 i = 1 的位置,左子节点下标为 2 * i = 2, 右子节点下标为 2 * i + 1 = 3,以此类推。如图所示:

值得注意的是,这里存储的是一颗完全二叉树,因此它在数组中只有第一个位置为空。若不是完全二叉树,则其存储结构如下:

数组中为空的位置就很多,这样会浪费很多存储空间。

二叉树的遍历

二叉的遍历就是循环打印出二叉树中的所有节点。经典的方法有三种,分别为:前序遍历、中序遍历和后序遍历。其中的前、中、后指的是节点与它的左右子节点遍历打印的先后顺序,即:

1. 前序遍历:本节点 --> 左子节点 --> 右子节点;

2. 中序遍历:左子节点 --> 本节点 --> 右子节点;

3. 后序遍历:左子节点 --> 右子节点 --> 本节点。

可以看到,前、中、后就是本节点在遍历中的顺序。示意图:

二叉查找树

二叉查找树(Binary Search Tree)是二叉树中最常用的一种类型,又称「二叉搜索树」,它支持快速查找、插入、删除一个数据。

结构特点

二叉树中的任一节点,其左子树中每个节点的值,都小于该节点的值;右子树中每个节点的值都大于该节点的值。示意图:

查找

查找步骤:

1. 先将要查找元素的值与根节点的值比较,若相等则返回;

2. 若小于根节点的值,则在左子树中递归查找;

3. 若大于根节点的值,则在右子树中递归查找。

查找过程示意图:

插入

插入过程与查找的比较过程有些类似,操作示意图如下:

删除

相比查找和插入,删除过程略微复杂一些。主要分为三种情况:

1. 待删除的节点无子节点:直接删除(下图的节点 55);

2. 待删除的节点有一个子节点:将待删除节点的父节点指向待删除节点的子节点(下图的节点 13);

3. 待删除的结点有两个子节点:需要先找到待删除节点的右子树中的最小节点,用它替换要删除的节点,然后再删除该最小节点(下图的节点 18)。

这三种情况的删除操作示意图如下:

二叉树&散列表

1. 散列表中的数据是无序的;二叉查找树中序遍历可在 O(n) 时间复杂度内输出有序的数据序列;

2. 散列表的扩容比较耗时,散列冲突时性能不稳定;平衡二叉查找树的性能稳定在 O(logn)

3. 散列表构造比二叉树复杂不少(散列函数设计、冲突解决、扩容等);二叉树只需考虑平衡性问题,且解决方案比较成熟、固定。

堆(Heap)是一种特殊的树,它满足以下结构特征:

1. 堆是一个完全二叉树;

2. 堆中每个节点的值都必须大于等于(或小于等于)其子树中每个节点的值。

其中,每个节点值都大于等于子树中每个节点值的堆称为「大顶堆」,小于等于树中每个节点值的堆称为「小顶堆」。示意图:

其中 1、2 为大顶堆,3 为小顶堆,4 不是堆(不是完全二叉树)。

存储

前面分析了二叉树的存储方法有两种:链式存储和顺序存储,而顺序存储比较适合完全二叉树。堆的顺序存储示例如下:

堆化

当向堆中插入元素、或从堆中删除元素时,可能会导致堆不满足其结构特点。因此需要对其进行调整使其重新满足堆的特性,该过程称为堆化(heapify)。

堆化有两种方式:从下往上从上往下

从下往上堆化示意图(插入节点 22):

从上往下堆化示意图(删除节点 33):

注意:这样操作会使堆不满足完全二叉树的特性。

如果转换思路,把最后一个节点放到堆顶,然后再进行从上到下堆化,如图所示:

这样就不会出现“数组空洞”,又能满足完全二叉树的特性。

应用场景

堆的几个非常重要的应用场景:优先级队列、Top K 问题、求中位数。

小结

1. 数据结构中的树可以类比生活中常见的树?倒过来。其中二叉树最常用,二叉树有两种特殊的情况:满二叉树和完全二叉树;

2. 二叉树的遍历方式有三种:前序、中序和后序遍历;在二叉树中,二叉查找树最常用,可以快速查找、插入、删除一个元素;

3. 堆是一种特殊的树:它是完全二叉树;且每个节点的值都大于等于(或小于等于)子树中每个节点的值(分别为大顶堆和小顶堆)。

相关阅读:

数据结构与算法笔记(二)

Stay hungry, stay foolish.

本文分享自微信公众号 - WriteOnRead(WriteOnRead)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-03-14

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏测试技术圈

这些Python库真的很“冷”,但是却很强大

Python是一种很棒的编程语言。事实上,它还是世界上发展最快的编程语言之一。它一次又一次证明了它在数据科学职位中的实用性。整个Python及其库的生态系统使其...

10230
来自专栏测试技术圈

持续交付之基于Git Flow代码分支策略实践

高效的持续交付体系,必定需要一个合适的代码分支策略。采用不同的代码分支策略,意味着实施不同的代码集成与发布流程,这会影响整个研发团队每日的协作方式,因此研发团队...

8720
来自专栏测试技术圈

【文章】Java应用程序运行时监控方法之JVMTI的应用

The JVM Tool Interface (JVMTI) 是一个由JVM提供的用于开发针对Java程序开发与监控工具的编程接口,通过JVMTI接口(Nati...

20230
来自专栏北京马哥教育

加密传输原理

数字签名,就是通过在数据单元上附加数据,或对数据单元进行秘密变换,从而使接收者可以确认数据来源和完整性。简单说来,数字签名是防止他人对传输的文件进行破坏,以及确...

12240
来自专栏Java架构沉思录

线程本地变量,你只会ThreadLocal吗?

代码@3:如果线程对象的threadLocals属性不为空,则从该Map结构中,用threadLocal对象为键去查找值,如果能找到,则返回其value值,否则...

24030
来自专栏Kiba518

WPF滑块控件(Slider)的自定义样式

点击确定后,我们的页面的Resources中,增加了一系列样式代码,而滑块代码会被修改为如下样子:

30530
来自专栏服务化进程

Maven经验分享(一)安装部署

在安装Maven之前,首先要确认你已经正确安装了JDK。Maven可以运行在JDK 1.4及以上的版本上。本书的所有样例都基于JDK 5及以上版本

7320
来自专栏AI科技评论

一文带你了解视觉目标跟踪

视觉目标跟踪(Visual Object Tracking)是计算机视觉领域的一个重要问题。尽管近年来受到了广泛研究,目标跟踪问题由于本身的高难度、高质量数据的...

43020
来自专栏测试技术圈

窥视WebSocket传输的内容(Fiddler抓取)

Fiddler(中文名称:小提琴)是一个HTTP的调试代理,以代理服务器的方式,监听系统的Http网络数据流动,Fiddler可以也可以让你检查所有的HTTP通...

38450
来自专栏测试技术圈

Fiddler抓取websocket的包

51230

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励