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