图解：数据结构中的6种「树」，你心中有数吗？
数据结构这门课程是计算机相关专业的基础课 ， 数据结构指的是数据在计算机中的存储、组织方式 。
我们在学习数据结构时候 ， 会遇到各种各样的基础数据结构 ， 比如堆栈、队列、数组、链表、树...这些基本的数据结构类型有各自的特点 ， 不同数据结构适用于解决不同场景下的问题 。
树形结构相比数组、链表、堆栈这些数据结构来说 ， 稍微复杂一点点 ， 但树形结构可以用于解决很多实际问题 ， 因为现实世界事物之间的关系往往不是线性关联的 ， 而「树」恰好适合描述这种非线性关系 。
今天就带大家一起学习下 ， 数据结构中的各种「树」 ， 这也是面试中经常考察的内容 ， 手撕二叉树是常规套路 ， 对候选人也很有区分度 ， 学完这篇文章 ， 相信大家都会心中有「树」了 。
文章插图
从树说起什么是树？现实中的树大家都见过 ， 在数据结构中也有树 ， 此树非彼树 ， 不过数据结构的树和现实中的树在形态上确实有点相像 。
树是非线性的数据结构 ， 用来模拟具有树状结构性质的数据集合 ， 它是由n个有限节点组成的具有层次关系的集合 。 在数据结构中树是非线性数据结构 ， 那我们先来了解下 ， 什么是线性与非线性数据结构？
线性结构「线性结构」是一个有序数据元素的集合 。 其中数据元素之间的关系是一对一的关系 ， 即除了第一个和最后一个数据元素之外 ， 其它数据元素都是首尾相接的 ， 常用的线性结构有：线性表 ， 栈 ， 队列 ， 双端队列 ， 数组 ， 串 。
文章插图
文章插图
可以想象 ， 所谓的线性结构数据组织形式 ， 就像一条线段一样笔直 ， 元素之间首尾相接 。 比如现实中的火车进站、食堂打饭排队的队列 。
文章插图
非线性结构简而言之 ， 线性结构的对立面就是「非线性结构」 。
树线性结构中节点是首位相接一对一关系 ， 在树结构中节点之间不再是简单的一对一关系 ， 而是较为复杂的一对多的关系 ， 一个节点可以与多个节点发生关联 ， 树是一种层次化的数据组织形式 ， 树在现实中是可以找到例子的 ， 比如现实中的族谱 ， 亲戚之间的关系是层次关联的树形关系 。
数据结构中的「树」的名字由来 ， 是因为如果把节点之间的关系直观展示出来 ， 由于长得和现实世界中的树很像 ， 由此得名 。 如图：
文章插图
树的关键概念人们对树形结构的研究比较深入 ， 为了方便研究树的各种性质 ， 抽象出了一些树相关的概念 ， 以便清晰简介的描述一颗树 。 下面几个基础概念必须了解 ， 否则你当你刷LeetCode树相关题目时候 ， 或者面试官向你描述问题时 ， 你会连题目都看不懂事什么意思 。
先来上一个图解 ， 下面的术语和概念对照着看 ， 更容易理解 。
文章插图
?
什么是节点的度？
?
度很好理解 ， 直观来说 ， 数一下节点有几个分叉就说这个节点的度是多少 。
?
什么是根节点？
?
在一颗树形结构中 ， 最顶层的那个节点就是根节点了 ， 所有的子节点都源自它发散开来 。
?
什么是父节点？
【图解：数据结构中的6种「树」，你心中有数吗？】?
树的父子关系和现实中很相似 ， 若一个节点含有子节点 ， 则这个节点称为其子节点的父节点 。
?
什么是叶子节点？
?
直观来看叶子节点都位于树的最底层 ， 就是没有分叉的节点 ， 严格的定义是度为 0 的节点叫叶子节点 。
?
什么是节点的高度？
?
高度是从叶子节点开始「自底向上」逐层累加的路径长度 ， 树叶的高度为 0（有些书上也说是 0 ， 不用纠结）
?
什么是节点的深度？
?
深度是从根节点开始「自顶向下」逐层累加的路径长度 ， 根的深度为1（有些书上也说是 0 ， 问题不大）
小技巧：高度和深度 ， 一个从下往上数 ， 一个从上往下数 。
树的特点树形数据结构 ， 具有以下的结构特点：