23二叉树基础(上):什么样的二叉树适合用数组来存储?.pdf
《23二叉树基础(上):什么样的二叉树适合用数组来存储?.pdf》由会员分享,可在线阅读,更多相关《23二叉树基础(上):什么样的二叉树适合用数组来存储?.pdf(20页珍藏版)》请在三一文库上搜索。
1、23|二叉树基础(上):什么样的二叉树适合用数组来存储? file:/F/temp/geektime/数据结构与算法之美/23二叉树基础(上):什么样的二叉树适合用数组来存储?.html2019/1/15 15:35:52 23|二叉树基础(上):什么样的二叉树适合用数组来存储? 前面我们讲的都是线性表结构,栈、队列等等。今天我们讲一种非线性表结构,树。树这种数据结构比线性表的数据结构要复杂得多,内容也比较多,所以我会 分四节来讲解。 我反复强调过,带着问题学习,是最有效的学习方式之一,所以在正式的内容开始之前,我还是给你出一道思考题:二叉树有哪几种存储方式?什么样的二叉树 适合用数组来存储?
2、 带着这些问题,我们就来学习今天的内容,树! 树(Tree) 23|二叉树基础(上):什么样的二叉树适合用数组来存储? file:/F/temp/geektime/数据结构与算法之美/23二叉树基础(上):什么样的二叉树适合用数组来存储?.html2019/1/15 15:35:52 我们首先来看,什么是“树”?再完备的定义,都没有图直观。所以我在图中画了几棵“树”。你来看看,这些“树”都有什么特征? 你有没有发现,“树”这种数据结构真的很像我们现实生活中的“树”,这里面每个元素我们叫作“节点”;用来连线相邻节点之间的关系,我们叫作“父子关系”。 23|二叉树基础(上):什么样的二叉树适合用数
3、组来存储? file:/F/temp/geektime/数据结构与算法之美/23二叉树基础(上):什么样的二叉树适合用数组来存储?.html2019/1/15 15:35:52 比如下面这幅图,A节点就是B节点的父节点,B节点是A节点的子节点。B、C、D这三个节点的父节点是同一个节点,所以它们之间互称为兄弟节点。我们把没有 父节点的节点叫作根节点,也就是图中的节点E。我们把没有子节点的节点叫作叶子节点或者叶节点,比如图中的G、H、I、J、K、L都是叶子节点。 除此之外,关于“树”,还有三个比较相似的概念:高度(Height)、深度(Depth)、层(Level)。它们的定义是这样的: 23|二
4、叉树基础(上):什么样的二叉树适合用数组来存储? file:/F/temp/geektime/数据结构与算法之美/23二叉树基础(上):什么样的二叉树适合用数组来存储?.html2019/1/15 15:35:52 这三个概念的定义比较容易混淆,描述起来也比较空洞。我举个例子说明一下,你一看应该就能明白。 23|二叉树基础(上):什么样的二叉树适合用数组来存储? file:/F/temp/geektime/数据结构与算法之美/23二叉树基础(上):什么样的二叉树适合用数组来存储?.html2019/1/15 15:35:52 记这几个概念,我还有一个小窍门,就是类比“高度”“深度”“层”这几个
5、名词在生活中的含义。 在我们的生活中,“高度”这个概念,其实就是从下往上度量,比如我们要度量第10层楼的高度、第13层楼的高度,起点都是地面。所以,树这种数据结构的高度 也是一样,从最底层开始计数,并且计数的起点是0。 “深度”这个概念在生活中是从上往下度量的,比如水中鱼的深度,是从水平面开始度量的。所以,树这种数据结构的深度也是类似的,从根结点开始度量,并且 计数起点也是0。 “层数”跟深度的计算类似,不过,计数起点是1,也就是说根节点的位于第1层。 二叉树(Binary Tree) 23|二叉树基础(上):什么样的二叉树适合用数组来存储? file:/F/temp/geektime/数据结
6、构与算法之美/23二叉树基础(上):什么样的二叉树适合用数组来存储?.html2019/1/15 15:35:52 树结构多种多样,不过我们最常用还是二叉树。 二叉树,顾名思义,每个节点最多有两个“叉”,也就是两个子节点,分别是左子节点和右子节点。不过,二叉树并不要求每个节点都有两个子节点,有的节点只 有左子节点,有的节点只有右子节点。我画的这几个都是二叉树。以此类推,你可以想象一下四叉树、八叉树长什么样子。 这个图里面,有两个比较特殊的二叉树,分别是编号2和编号3这两个。 其中,编号2的二叉树中,叶子节点全都在最底层,除了叶子节点之外,每个节点都有左右两个子节点,这种二叉树就叫作满二叉树。
7、23|二叉树基础(上):什么样的二叉树适合用数组来存储? file:/F/temp/geektime/数据结构与算法之美/23二叉树基础(上):什么样的二叉树适合用数组来存储?.html2019/1/15 15:35:52 编号3的二叉树中,叶子节点都在最底下两层,最后一层的叶子节点都靠左排列,并且除了最后一层,其他层的节点个数都要达到最大,这种二叉树叫作完全二叉 树。 满二叉树很好理解,也很好识别,但是完全二叉树,有的人可能就分不清了。我画了几个完全二叉树和非完全二叉树的例子,你可以对比着看看。 23|二叉树基础(上):什么样的二叉树适合用数组来存储? file:/F/temp/geekti
8、me/数据结构与算法之美/23二叉树基础(上):什么样的二叉树适合用数组来存储?.html2019/1/15 15:35:52 23|二叉树基础(上):什么样的二叉树适合用数组来存储? file:/F/temp/geektime/数据结构与算法之美/23二叉树基础(上):什么样的二叉树适合用数组来存储?.html2019/1/15 15:35:52 你可能会说,满二叉树的特征非常明显,我们把它单独拎出来讲,这个可以理解。但是完全二叉树的特征不怎么明显啊,单从长相上来看,完全二叉树并没有特 别特殊的地方啊,更像是“芸芸众树”中的一种。 那我们为什么还要特意把它拎出来讲呢?为什么偏偏把最后一层的叶
9、子节点靠左排列的叫完全二叉树?如果靠右排列就不能叫完全二叉树了吗?这个定义的由来 或者说目的在哪里? 要理解完全二叉树定义的由来,我们需要先了解,如何表示(或者存储)一棵二叉树? 想要存储一棵二叉树,我们有两种方法,一种是基于指针或者引用的二叉链式存储法,一种是基于数组的顺序存储法。 我们先来看比较简单、直观的链式存储法。从图中你应该可以很清楚地看到,每个节点有三个字段,其中一个存储数据,另外两个是指向左右子节点的指针。我 们只要拎住根节点,就可以通过左右子节点的指针,把整棵树都串起来。这种存储方式我们比较常用。大部分二叉树代码都是通过这种结构来实现的。 23|二叉树基础(上):什么样的二叉树
10、适合用数组来存储? file:/F/temp/geektime/数据结构与算法之美/23二叉树基础(上):什么样的二叉树适合用数组来存储?.html2019/1/15 15:35:52 我们再来看,基于数组的顺序存储法。我们把根节点存储在下标i = 1的位置,那左子节点存储在下标2 * i = 2的位置,右子节点存储在2 * i + 1 = 3的位置。以此类 推,B节点的左子节点存储在2 * i = 2 * 2 = 4的位置,右子节点存储在2 * i + 1 = 2 * 2 + 1 = 5的位置。 23|二叉树基础(上):什么样的二叉树适合用数组来存储? file:/F/temp/geekti
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 23 二叉 基础 什么样 适合 数组 存储
链接地址:https://www.31doc.com/p-5529981.html