数据结构 如何理解树

树的定义

前面几篇文章讨论的都是一对一的线性结构，但是现实中还有很多是一对多的情况。这就进化出树这种数据结构。

树(Tree)是n(n>0)个结点的有限集。n=0 时称为空树。在任意一个非空树中：

(1) 有且仅有一个特定的称为根 (Root) 的结点。

(2) 当 n > 1 时，其余结点可分为 m (m > 0) 个互不相交的有限集 T1、T2、......Tm,其中每一个集合本身又是一棵树，并且称有根的子树 (SubTree)。

具体如图:

对于树的定义需要强调两点:

n > 0 时根结点是唯一的，不可能存在多个根结点，现实中的大树有多个根，但是数据结构中只能有一个根。

m > 0 时，子树的个数没有限制，但是它们一定是互不相交的。一旦两颗子树相交，则不是树。如图就是两颗错误的树。

结点的分类

树的结点包含一个数据元素及若干指向其子树的分支。结点拥有的子树数称为结点的度。

度为0的结点也就是叶节点或者称为终端结点。度不为0的结点称为非终端结点或分支结点。

除了根节点之外，分支结点也称为内部结点。树的度是树内各结点的度的最大值。

如图所示:

结点间关系

结点的子树的跟称为该结点的孩子，相应地，该结点称为孩子的双亲。

同一个双亲的孩子之间互称兄弟。

结点的祖先是从根到该结点所经分支上的所有结点。

反之，以某结点为根的子树中的任一结点都称为该结点的子孙。

家族关系如图所示：

树的其他相关概念

结点的层次从根结点开始，根为第一层，根的孩子为第二层。

如果两个结点的双亲在同一层，那么这两个结点互为堂兄弟。

树中结点的最大层次称为树的深度或者高度。

如果将树中结点的各子树看成从左到右是有次序的，不能互换的，则称该树为有序树，否则称为无序树。

森林是 m (m >= 0) 颗互不相交的树的集合。

树结构与线性结构的区别

树结构：

根结点：无双亲，唯一

叶节点：无孩子，可以有多个叶节点

中间结点：一个双亲多个孩子

线性结构：

第一个数据元素没有前驱

最后一个数据元素没有后继

中间元素：有一个前驱和一个后继

开工了

好像停更了好久了，上班族应该都开始上班了，学生党也陆陆续续地开始要上课了，我也要开始立 flag 更新我的公众号了哈哈哈，答应自己要把数据结构这个系列写完，自己一定要在今年三月份写完，由于写的都是干货，所以每一个字都值得各位读者深思，所以我建议想学数据结构的读者，建议大家只字不差的阅读我这个系列，同时我提供 Java 版的数据结构代码给大家参考，每一个代码都是能够直接运行了，所以大家有时间可以自己去写写这些代码，另外大家如果有什么好的建议可以在公众号后台留言呀，开设这个公众号的意义不在于我给大家普及一些知识，更重要的是共同学习，毕竟，学习，不仅是陪着自己成长，也是一个陪着他人成长的过程，谢谢大家。