【算法】数据结构：树结构（引言）

一、引言

本文只是一个引子，来讲述树这种数据结构的一些入门点

对于刚接触树这种结构的小伙伴，我们需要思考几个问题（我当年也有这样的疑问）？

1、这种数据结构长什么样？

2、有哪些基础概念是需要了解的？

3、在编程中，用什么样的结构来存储树状结构？

4、如何增删改查和遍历数据？

5、既然已经有了看似万能的散列表+链表的数据结构，为什么还有树的结构出现，他解决了什么问题？

 

二、数据结构

以下这些制作精美的图片

来自于王争老师的《算法与数据结构之美》，我只是搬运工！！！

 

三、名词和概念

喜欢看文字的就看文字，喜欢看图的就看图

1、基础概念

节点的高度=节点到叶子节点的最长路径（边数）
节点的深度=跟节点到这个节点所经历的边的个数
节点的层数=节点的深度+1
树的高度=根节点的高度

2、树的分叉

二叉树特点是每个结点最多只能有两棵子树，且有左右之分

三叉树就是。。。最多三棵子树，以此类推

当然还有写变种，比如满二叉树，完全二叉树，b树，b+树，红黑树，堆等等，这一类其实都是在树的基础上，为了满足某些目的，加上了各种条件限制。

当然最经常出现的还是二叉树

 

四、编程中如何存储（二叉树）

首先我这里说的是二叉树，多叉树以此类推，其实关键就在于如何维护父子节点的关系

1、自己创建class，属性包括但不限于

该节点的值

该节点的左子节点的引用

该节点的右子节点的引用

2、通过数组存数据

那父子节点的关系如何知道呢？

如图，假设有一棵树，如下图，那么可以将数存入下面的数组！

任取一个节点，下标i（比如B，下标i=2）的位置，下标为2 * i （2*2=4）的位置存储的就是左子节点，下标为2 * i + 1（2*2+1=5）的位置存储的就是右子节点。反过来，下标 为i/2的位置存储就是它的父节点

你会发现数组i=0，没有存数据。当然，如果你不想浪费，也可以从0开始存，那么左子节点就为2 * i + 1，右子节点为2 * i  + 2，这样也就维护了父子节点的关系！

注意：完全二叉树

非常适合用数组存储，因为不会浪费空间！！

有一种二叉树，叶子节点都在最底下两层，最后一层叶子节都靠左排列，并且除了最后一层，其他层的节点个数都要达到最大，这种二叉树叫做完全二叉树

 

 

五、增删改查和遍历数据

1、遍历数据

树的遍历方式，有如下四种，他们各有适用的场景

前序遍历是指，对于树中的任意节点来说，先打印这个节点，然后再打印它的左子树，最后打印它的右子树。

中序遍历是指，对于树中的任意节点来说，先打印它的左子树，然后再打印它本身，最后打印它的右子树。

后序遍历是指，对于树中的任意节点来说，先打印它的左子树，然后再打印它的右子树，最后打印这个节点本身。

层级遍历是指，从根目录开始一层一层往下遍历，结果应该是ABCDEFG

不好记？其实前中后，是相对于父节点打印的顺序定义的，比如图中的ABC，如果是前序遍历，就是ABC，中序就是BAC，后序就是BCA

当然大家可以去百度一下遍历的代码（大多数是递归写的，你看看他是如何跑的，就能理解）

在我的红黑树的文章中我有说过这几种遍历的具体应用，大家也可以自行百度

 

2、查找数据和修改数据

其实二叉树的出现有很大一部分原因，就是为了解决快速的查找！（当然二叉树本身是解决不了，但是他的变形就可以解决这样的问题）

如果树上的节点对应的值按照一定规律排序，比如：任意节点，左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大 于这个节点的值（二叉查找树）

这样，我要查找某个值X，只需要拿该值与根比较，X小于根，就与根的左子节点比较，X大于根，就与根的右子节点比较，以此类推，时间复杂度：O(logn)

修改数据，本质也是查到了数据，然后替换值而已，所以是一样的

3、增加和删除

二叉树的增删改查操作的时间复杂度基本都维持在O(logn)，但是在经过一番增删之后，树可能会退化成O(n)！

同样是9个数据，你会发现，上图三棵树的时间复杂度不一样！第一个直接退化成链表了

所以对于不同的二叉树变种，增删的操作可能都不太一样

但是不管什么样的操作，都是为了平衡增加和删除数据对树状结构带来的破坏（比如红黑树，是通过旋转来平衡）

 

 

六、树结构的优势

这里我直接引用王争老师的《算法与数据结构之美》里面的结论，我觉得他说的太好了，完全没有可修改的空间，哈哈哈~

我们在散列表那节中讲过，散列表的插入、删除、查找操作的时间复杂度可以做到常量级的O(1)，非常高效。而二叉查找树在比较平衡的情况下，插入、删除、 查找操作时间复杂度才是O(logn)，相对散列表，好像并没有什么优势，那我们为什么还要用二叉查找树呢？

我认为有下面几个原因：

第一，散列表中的数据是无序存储的，如果要输出有序的数据，需要先进行排序。而对于二叉查找树来说，我们只需要中序遍历，就可以在O(n)的时间复杂度 内，输出有序的数据序列。

第二，散列表扩容耗时很多，而且当遇到散列冲突时，性能不稳定，尽管二叉查找树的性能不稳定，但是在工程中，我们最常用的平衡二叉查找树的性能非常稳 定，时间复杂度稳定在O(logn)。

第三，笼统地来说，尽管散列表的查找等操作的时间复杂度是常量级的，但因为哈希冲突的存在，这个常量不一定比logn小，所以实际的查找速度可能不一定 比O(logn)快。加上哈希函数的耗时，也不一定就比平衡二叉查找树的效率高。

第四，散列表的构造比二叉查找树要复杂，需要考虑的东西很多。比如散列函数的设计、冲突解决办法、扩容、缩容等。平衡二叉查找树只需要考虑平衡性这一 个问题，而且这个问题的解决方案比较成熟、固定。

最后，为了避免过多的散列冲突，散列表装载因子不能太大，特别是基于开放寻址法解决冲突的散列表，不然会浪费一定的存储空间。

综合这几点，平衡二叉查找树在某些方面还是优于散列表的，所以，这两者的存在并不冲突。我们在实际的开发过程中，需要结合具体的需求来选择使用哪一 个。

 

菜鸡一只，如果有什么写的不对的，还请大家批评指出！坚决改正~

我还写了红黑树的系列文章（已经完结，欢迎大家检阅）：

【算法】红黑树（二叉树）概念与查询（一）：https://blog.csdn.net/lsr40/article/details/85230703

时隔了一个月，我又回来写文章了，这一个月还是发生了很多事情的，好兄弟结婚了（兰州牛肉面特别好吃！），换了个团队（去哪里不是打杂呢），坚持每天背单词（我知道很多背了就忘，但是不背，连忘的权利都没有，铁了心多背几轮就好了），买了健身环锻炼身体（给女朋友也买了一个），希望人生能继续朝着positive方向前进！