写点什么

Android 技能树 — 树基础知识小结 (一),阿里 P7 大牛整理

用户头像
Android架构
关注
发布于: 2 小时前

[Android 技能树 — 树基础知识小结(一)](


)


算法基础知识


[Android 技能树 — 排序算法基础小结](


)


本文主要讲关于树的基础知识。



树(Tree)是 n(n>=0)个结点的有限集。n=0 时称为空树。在任意一棵非空树中:(1)有且仅有一个特定的称为根(Root)的结点;(2)当 n>1 时,其余结点可分为 m(m>O)个互不相交的有限集 T1、T2、……、 Tm,其中每一个集合本身又是一棵树,并且称为根的子树(SubTree)


基础知识

结点


根据上面的基础知识我画了一个归总的图(这样我就不需要写文字介绍了,啊哈哈):


树结构特点


还是用自己画的图来说明:


存储结构

在[Android 技能树 — 数组,链表,散列表基础小结](


)中,我们介绍了线性存储,链式存储,我们的树可以充分用二者来结合表示。



我们统一来用上面各种方式来表示下面这个树的存储结构:


双亲表示法:

在每个结点中,附设一个指示器指示其双亲结点在数组中的位置。



因为有十一个结点,所以我们的 index 为 0-10,然后 index 位置中存储(data + parent 的 index 值),结果如下图所示:



这里我们发现根据 index 里面的 parent 指针,很容易知道父结点,但是比如我问知道了 E 结点,想知道它的子结点是哪几个,就不知道了,只能通过整个结构的遍历。


当然我们可以变相的 多加一个指针:



如果我们又比较关注兄弟结点之间的关系,可以增加一个右兄弟域来体现兄弟关系:


孩子链表表示法:

把每个结点的孩子结点排列起来,以单链表作存储结构,则 n 个结点有 n 个孩子链表,如果是叶子结点,则此单链表为空。然后 n 个头指针又组成一个线性表,采用顺序存储结构,存放进一个一维数组中。


用孩子表示法表示我们上面的树,结构如下:



所以我们的结点结构有二种: 1.表头数组的表头结点:




  1. 孩子链表的孩子结点:




但是这样子对于查找某个结点的孩子,或者找某个结点的兄弟都方便,但似乎如果要找某个结点的双亲结点就麻烦了。所以我们可以结合上面讲过的《双亲表示法》

双亲孩子表示法:


把上面二个方法结合就可以了。

孩子兄弟表示法:

任意一棵树,它的结点的第一个孩子如果存在就是唯一的,它的右兄弟如果存在也是唯一的。 所以设置二个指针,分别指向该结点的第一个孩子和此结点的右兄弟


所以和上面类似,只是我们存了不同的二个指针(从方法名字就知道,<孩子><兄弟>法,一个孩子,一个兄弟,二个指针)。



我们把上面的树按照这种方式实现:


森林:


继续画个图来说明,省得打字了,嘿嘿:



分类

树也是会根据不同条件,做了分类,我们来了解一下。



那有序树和无序数的区别在于哪里呢?


如果将树中结点的各子树看成从左至右是有次序的,不能互换,则成为有序树,否则就是无序树


比如我们只是单纯的表示一个家族的关系:



比如只是说明 A 的孩子有 B 跟 C,这时候 B 和 C 换了位置叶 没关系,这时候就是无序树。


但是如果我们这个家族谱是按照年龄来排序(长子,次子),那这时候 B 和 C 就不能换位置了,这时候就是有序树。


但是我们平常说的树通常都是指的有序树,而有序树有很多分类,比较多的就是二叉树。


二叉树:

基本形态:

二叉树性质:


其实这个类似与我们以前数学课上要背的数学公式,大家可以自己画个二叉树,然后试着上面的公式比对下,是不是正确。

遍历二叉树:

二叉树的遍历是指从根结点出发,按照某种次序依次访问二叉树中所有结点,使得每个结点被访问依次且仅被访问一次。

前序遍历:


单单看这个图,其实换成我,我也看不懂规律,但是我们只需要懂得其中的规则就行。


伪代码:


遍历(结点对象 t){if( t == null){return;}//第一步,实现某个业务操作,比如我们是打印结点字符串。print(t)//第二步,递归方式继续调用该方法遍历左孩子遍历(t.左孩子)//第三步,递归方式继续调用该方法遍历右孩子遍历(t.右孩子)}


我们看到因为 print 在其他方法的前面,所以叫前序遍历。我们现在传入根结点到这个方法,然后依次打印并且递归,就会发现,就是图上的顺序。

中序遍历:

![](https://user-gold-cdn.xitu.io/2018/5/4/16329ce7b6b232f4?imageVi


《Android学习笔记总结+最新移动架构视频+大厂安卓面试真题+项目实战源码讲义》
浏览器打开:qq.cn.hn/FTe 免费领取
复制代码


ew2/0/w/1280/h/960/ignore-error/1)


伪代码:


遍历(结点对象 t){if( t == null){return;}//第一步,递归方式继续调用该方法遍历左孩子遍历(t.左孩子)//第二步,实现某个业务操作,比如我们是打印结点字符串。print(t)


//第三步,递归方式继续调用该方法遍历右孩子遍历(t.右孩子)}


我们发现只要把我们的打印语句放在中间,就是中序遍历了。

后序遍历:


用户头像

Android架构

关注

还未添加个人签名 2021.10.31 加入

还未添加个人简介

评论

发布
暂无评论
Android技能树 — 树基础知识小结(一),阿里P7大牛整理