写点什么

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

发布于: 2021 年 11 月 07 日



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




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

双亲孩子表示法:


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

孩子兄弟表示法:

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


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



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


森林:


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



分类

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



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


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


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


![](h


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


ttps://user-gold-cdn.xitu.io/2018/5/4/16329ce7958a7399?imageView2/0/w/1280/h/960/ignore-error/1)


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


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


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


二叉树:

基本形态:

二叉树性质:


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

遍历二叉树:

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

前序遍历:


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


伪代码:


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


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

中序遍历:


伪代码:


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


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


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

后序遍历:


伪代码:


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


}


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

二叉树分类:

斜树:
完全二叉树与满二叉树:

一棵深度为 k,且有 2^(k+1) - 1 个节点的二叉树称为满二叉树,这种树的特点是每一层上的节点数都是最大节点数。


而在一棵二叉树中,除最后一层外,若其余层都是满的,并且最后一层或者是满的,或者是在右边缺少连续若干节点,则此二叉树为完全二叉树。



满二叉树



完全二叉树

平衡二叉树:

这块知识很多,后期补上。

排序二叉树:

这块知识很多,后期补上。

线索二叉树:

n 个结点的二叉链表中含有 n+1(2n-(n-1)=n+1)个空指针域。利用二叉链表中的空指针域,存放指向结点在某种遍历次序下的前驱和后继结点的指针(这种附加的指针称为"线索")。


这里一定要说明一个知识点:什么是前驱和后继。


网上很多人都是对这个解释太过于简单以至于很多人理解错误,比如:



假设我们现在有这个一个二叉树:



我现在问 I 的前驱是谁,后继是谁,很多人就单纯的从树的形状上来看,也就是看 I 的上一个结点是 D,所以前驱是 D, I 没有后面的子结点,所以后驱为空。这种回答是错误的。我们在 Android技能树 — 数组,链表,散列表基础小结文中提到过前驱和后继:



比如双向链表就是有前驱和后继。那我们单纯看这棵树是看不出来的,我们要先把树按照某个遍历方式的时候,把它用这种链表形式摆列,然后才能知道某个结点的前驱和后继是什么,比如上面的图我们用中序遍历,我们得到的是:HDIBJEAFCG,这时候 I 的前继是 D,后继是 B。


我们在二叉树存储结构中,有二个指针指向它的二个子结点。



但是可能只有一个子结点,或者没有子结点,这样这个空的指针存储就浪费了,我们可以在这个指针里面存这个结点的前驱或者后继结点的指针。


但是这时候又有一个问题,就是我们不知道这个点目前到底放的是前驱的还是左子结点的指针,所以我们还需要一个参数来说明当前这个位置放的是哪个的指针。



  1. 当 ltag 为 0 的时候,说明 lchild 是该结点的左孩子的指针,为 1 的时候说明 lchild 是该结点的前驱。

  2. 当 rtag 为 0 的时候,说明 rchild 是该结点的右孩子的指针,为 1 的时候说明 rchild 是该结点的后继。

存储结构:

二叉树顺序存储结构:

我们把二叉树补充为一个满二叉树,然后相应的填入一个一维数组即可。


二叉链表:

二叉树每个结点最多又二个孩子,所以为它设计一个数据域和二个指针域。


三叉链表:

改进于二叉链表,增加父节点的指引,能更好地实现节点间的访问

结语:




本文并没有写完,内容太多,后面再陆续补上去。哪里写错了,欢迎指出。。。谢谢。参考:《大话数据结构》《维基百科》

评论

发布
暂无评论
Android技能树 — 树基础知识小结(一)