Android技能树 — 树基础知识小结(一)
前言:
现在安卓面试,对于数据结构的问题也越来越多了,也经常看到别人发的面试题都是问什么红黑树,二叉树查找等,所以我们虽然不会马上就会各种难的面试题,但起码树的基础知识还是要会的,这样才能去进一步学。
贴上最近看到的一个介绍图片:
![Android技能树 — 树基础知识小结(一)](https://img.blogweb.cn/article/182435d87c7a4ea7966d21e0dbcf947e.webp)
Android技能书系列:
Android基础知识
数据结构基础知识
算法基础知识
本文主要讲关于树的基础知识。
![Android技能树 — 树基础知识小结(一)](https://img.blogweb.cn/article/7de5edda21624f2eabd5f1977e67a1cf.webp)
树(Tree)是n(n>=0)个结点的有限集。n=0时称为空树。在任意一棵非空树中:(1)有且仅有一个特定的称为根(Root)的结点;(2)当n>1时,其余结点可分为m(m>O)个互不相交的有限集T1、T2、……、 Tm,其中每一个集合本身又是一棵树,并且称为根的子树(SubTree)
![Android技能树 — 树基础知识小结(一)](https://img.blogweb.cn/article/4204351776384cf495000378366fe199.webp)
基础知识
结点
![Android技能树 — 树基础知识小结(一)](https://img.blogweb.cn/article/f3623e98b6f643589e6d64af64574a7d.webp)
根据上面的基础知识我画了一个归总的图(这样我就不需要写文字介绍了,啊哈哈):
![Android技能树 — 树基础知识小结(一)](https://img.blogweb.cn/article/533778a9faf440c4943fadbd223d444a.webp)
树结构特点
![Android技能树 — 树基础知识小结(一)](https://img.blogweb.cn/article/bc9e97dde56f473db9bd136f30892ec8.webp)
还是用自己画的图来说明:
![Android技能树 — 树基础知识小结(一)](https://img.blogweb.cn/article/00d8aaa971de41608073cbbe1b8f8531.webp)
存储结构
![Android技能树 — 树基础知识小结(一)](https://img.blogweb.cn/article/74d80fec499541ee88c7cf0378e5507f.webp)
我们统一来用上面各种方式来表示下面这个树的存储结构:
![Android技能树 — 树基础知识小结(一)](https://img.blogweb.cn/article/6c0d73c63ef546aea2205718c623a804.webp)
双亲表示法:
在每个结点中,附设一个指示器指示其双亲结点在数组中的位置。
![Android技能树 — 树基础知识小结(一)](https://img.blogweb.cn/article/2d43e44d70b8489ab258e04636169c2b.webp)
因为有十一个结点,所以我们的index为0-10,然后index位置中存储(data + parent的index值),结果如下图所示:
![Android技能树 — 树基础知识小结(一)](https://img.blogweb.cn/article/1b71867ecf9749cdb13df99eaf35cc66.webp)
这里我们发现根据index里面的parent指针,很容易知道父结点,但是比如我问知道了E结点,想知道它的子结点是哪几个,就不知道了,只能通过整个结构的遍历。
当然我们可以变相的 多加一个指针:
![Android技能树 — 树基础知识小结(一)](https://img.blogweb.cn/article/70400838e0b9446d9e13e7f9989ee210.webp)
如果我们又比较关注兄弟结点之间的关系,可以增加一个右兄弟域来体现兄弟关系:
![Android技能树 — 树基础知识小结(一)](https://img.blogweb.cn/article/41fe8da823a14d4097fe078f9ef502d1.webp)
孩子链表表示法:
把每个结点的孩子结点排列起来,以单链表作存储结构,则n 个结点有n个孩子链表,如果是叶子结点,则此单链表为空。然后n个头指针又组成一个线性表,采用顺序存储结构,存放进一个一维数组中。
用孩子表示法表示我们上面的树,结构如下:
![Android技能树 — 树基础知识小结(一)](https://img.blogweb.cn/article/179157e5fc8c481a8563a1923e8e5e85.webp)
所以我们的结点结构有二种: 1.表头数组的表头结点:
![Android技能树 — 树基础知识小结(一)](https://img.blogweb.cn/article/8126fdbdee514b7bae17991354f4c9a8.webp)
![Android技能树 — 树基础知识小结(一)](https://img.blogweb.cn/article/3e21ffda56324432847ab3d3fcd968e5.webp)
- 孩子链表的孩子结点:
但是这样子对于查找某个结点的孩子,或者找某个结点的兄弟都方便,但似乎如果要找某个结点的双亲结点就麻烦了。所以我们可以结合上面讲过的《双亲表示法》
双亲孩子表示法:
![Android技能树 — 树基础知识小结(一)](https://img.blogweb.cn/article/e9edfe64cb6249b1a02607f9c1aa304e.webp)
把上面二个方法结合就可以了。
孩子兄弟表示法:
任意一棵树,它的结点的第一个孩子如果存在就是唯一的,它的右兄弟如果存在也是唯一的。 所以设置二个指针,分别指向该结点的第一个孩子和此结点的右兄弟
所以和上面类似,只是我们存了不同的二个指针(从方法名字就知道,<孩子><兄弟>法,一个孩子,一个兄弟,二个指针)。
![Android技能树 — 树基础知识小结(一)](https://img.blogweb.cn/article/c9ad422b742a4640aa55d98b43c84aaa.webp)
我们把上面的树按照这种方式实现:
![Android技能树 — 树基础知识小结(一)](https://img.blogweb.cn/article/9197c44926c049e4ba34d66cba67e074.webp)
森林:
![Android技能树 — 树基础知识小结(一)](https://img.blogweb.cn/article/0d86af9f5e1b4dd3932dedb9c2de78f0.webp)
继续画个图来说明,省得打字了,嘿嘿:
![Android技能树 — 树基础知识小结(一)](https://img.blogweb.cn/article/8da50cc4faf04d8ab1e8e020cdc95f93.webp)
![Android技能树 — 树基础知识小结(一)](https://img.blogweb.cn/article/27c9ad20d4c9432a9c469cce35833a62.webp)
分类
树也是会根据不同条件,做了分类,我们来了解一下。
![Android技能树 — 树基础知识小结(一)](https://img.blogweb.cn/article/32fbec1a13fc41d6be8bad9bb42d85b3.webp)
那有序树和无序数的区别在于哪里呢?
如果将树中结点的各子树看成从左至右是有次序的,不能互换,则成为有序树,否则就是无序树
比如我们只是单纯的表示一个家族的关系:
![Android技能树 — 树基础知识小结(一)](https://img.blogweb.cn/article/dfb62e98be2146a680d76a7441f76628.webp)
比如只是说明A的孩子有B跟C,这时候B和C换了位置叶 没关系,这时候就是无序树。
但是如果我们这个家族谱是按照年龄来排序(长子,次子),那这时候B和C就不能换位置了,这时候就是有序树。
但是我们平常说的树通常都是指的有序树,而有序树有很多分类,比较多的就是二叉树。
![Android技能树 — 树基础知识小结(一)](https://img.blogweb.cn/article/5753da8961834fcdae36c26e857f5d20.webp)
二叉树:
![Android技能树 — 树基础知识小结(一)](https://img.blogweb.cn/article/a312be52bf4d42b88fa7ba09990643e9.webp)
基本形态:
![Android技能树 — 树基础知识小结(一)](https://img.blogweb.cn/article/dca0b6aff4894877b0433fdbd83099c1.webp)
二叉树性质:
![Android技能树 — 树基础知识小结(一)](https://img.blogweb.cn/article/2af7fdec0b65443986d9ceb6bf8e00ec.webp)
其实这个类似与我们以前数学课上要背的数学公式,大家可以自己画个二叉树,然后试着上面的公式比对下,是不是正确。
遍历二叉树:
二叉树的遍历是指从根结点出发,按照某种次序依次访问二叉树中所有结点,使得每个结点被访问依次且仅被访问一次。
前序遍历:
![Android技能树 — 树基础知识小结(一)](https://img.blogweb.cn/article/5080821655b745d2bc073385c3f1cd47.webp)
单单看这个图,其实换成我,我也看不懂规律,但是我们只需要懂得其中的规则就行。
伪代码:
遍历(结点对象 t){
if( t == null){
return;
}
//第一步,实现某个业务操作,比如我们是打印结点字符串。
print(t)
//第二步,递归方式继续调用该方法遍历左孩子
遍历(t.左孩子)
//第三步,递归方式继续调用该方法遍历右孩子
遍历(t.右孩子)
}
我们看到因为print在其他方法的前面,所以叫前序遍历。我们现在传入根结点到这个方法,然后依次打印并且递归,就会发现,就是图上的顺序。
中序遍历:
![Android技能树 — 树基础知识小结(一)](https://img.blogweb.cn/article/21439e0499744cae8ff7d01334382a0c.webp)
伪代码:
遍历(结点对象 t){
if( t == null){
return;
}
//第一步,递归方式继续调用该方法遍历左孩子
遍历(t.左孩子)
//第二步,实现某个业务操作,比如我们是打印结点字符串。
print(t)
//第三步,递归方式继续调用该方法遍历右孩子
遍历(t.右孩子)
}
我们发现只要把我们的打印语句放在中间,就是中序遍历了。
后序遍历:
![Android技能树 — 树基础知识小结(一)](https://img.blogweb.cn/article/7fc96d224a4444adb673446560f6cc76.webp)
伪代码:
遍历(结点对象 t){
if( t == null){
return;
}
//第一步,递归方式继续调用该方法遍历左孩子
遍历(t.左孩子)
//第二步,递归方式继续调用该方法遍历右孩子
遍历(t.右孩子)
//第三步,实现某个业务操作,比如我们是打印结点字符串。
print(t)
}
我们发现只要把我们的打印语句放在最后,就是后序遍历了。
二叉树分类:
![Android技能树 — 树基础知识小结(一)](https://img.blogweb.cn/article/a083ec643a6341fabb3b4efd24d2665e.webp)
斜树:
![Android技能树 — 树基础知识小结(一)](https://img.blogweb.cn/article/636025ab77a64c168fe8c2f1e63e8aa5.webp)
完全二叉树与满二叉树:
一棵深度为k,且有 2^(k+1) - 1 个节点的二叉树称为满二叉树,这种树的特点是每一层上的节点数都是最大节点数。
而在一棵二叉树中,除最后一层外,若其余层都是满的,并且最后一层或者是满的,或者是在右边缺少连续若干节点,则此二叉树为完全二叉树。
![Android技能树 — 树基础知识小结(一)](https://img.blogweb.cn/article/ce089630af1c439e8978d8d2d5a67ae2.webp)
![Android技能树 — 树基础知识小结(一)](https://img.blogweb.cn/article/a755cc3a38e642f7bd395c252c3b726c.webp)
平衡二叉树:
这块知识很多,后期补上。
排序二叉树:
这块知识很多,后期补上。
线索二叉树:
n个结点的二叉链表中含有n+1(2n-(n-1)=n+1)个空指针域。利用二叉链表中的空指针域,存放指向结点在某种遍历次序下的前驱和后继结点的指针(这种附加的指针称为"线索")。
这里一定要说明一个知识点:什么是前驱和后继。
网上很多人都是对这个解释太过于简单以至于很多人理解错误,比如:
![Android技能树 — 树基础知识小结(一)](https://img.blogweb.cn/article/83d576f1bb4a4016b35c35d2dfb9e082.webp)
假设我们现在有这个一个二叉树:
![Android技能树 — 树基础知识小结(一)](https://img.blogweb.cn/article/4680dcb9732e4619872eb6d6e435d4ef.webp)
![Android技能树 — 树基础知识小结(一)](https://img.blogweb.cn/article/056ee270905b47c0bca4cf8edee7df24.webp)
比如双向链表就是有前驱和后继。那我们单纯看这棵树是看不出来的,我们要先把树按照某个遍历方式的时候,把它用这种链表形式摆列,然后才能知道某个结点的前驱和后继是什么,比如上面的图我们用中序遍历,我们得到的是:HDIBJEAFCG,这时候 I 的前继是D,后继是B。
我们在二叉树存储结构中,有二个指针指向它的二个子结点。
![Android技能树 — 树基础知识小结(一)](https://img.blogweb.cn/article/fc33e91ecab04923997b87a1680f339e.webp)
但是可能只有一个子结点,或者没有子结点,这样这个空的指针存储就浪费了,我们可以在这个指针里面存这个结点的前驱或者后继结点的指针。
但是这时候又有一个问题,就是我们不知道这个点目前到底放的是前驱的还是左子结点的指针,所以我们还需要一个参数来说明当前这个位置放的是哪个的指针。
![Android技能树 — 树基础知识小结(一)](https://img.blogweb.cn/article/6d17f6f3a4e84ec090d053383ed00058.webp)
- 当ltag为0的时候,说明lchild是该结点的左孩子的指针,为1的时候说明lchild是该结点的前驱。
- 当rtag为0的时候,说明rchild是该结点的右孩子的指针,为1的时候说明rchild是该结点的后继。
存储结构:
![Android技能树 — 树基础知识小结(一)](https://img.blogweb.cn/article/b495da3a3224432792af2a25aa348718.webp)
二叉树顺序存储结构:
我们把二叉树补充为一个满二叉树,然后相应的填入一个一维数组即可。
![Android技能树 — 树基础知识小结(一)](https://img.blogweb.cn/article/dc42ccd4aa8c403189f17a6073f18f11.webp)
二叉链表:
二叉树每个结点最多又二个孩子,所以为它设计一个数据域和二个指针域。
![Android技能树 — 树基础知识小结(一)](https://img.blogweb.cn/article/eee62bf0302e4203983a4b975e7442b4.webp)
三叉链表:
改进于二叉链表,增加父节点的指引,能更好地实现节点间的访问
![Android技能树 — 树基础知识小结(一)](https://img.blogweb.cn/article/00b0500012854a3d8251c55c59e5418e.webp)
结语:
本文并没有写完,内容太多,后面再陆续补上去。哪里写错了,欢迎指出。。。谢谢。
参考:
《大话数据结构》
《维基百科》
转载自:https://juejin.cn/post/6844903601794449415