树

树是一种数据结构，它是由n（n>=1）个有限结点组成一个具有层次关系的集合。

它具有以下的特点：

1. 1.每个结点有零个或多个子结点；
2. 2.没有父结点的结点称为根结点；
3. 3.每一个非根结点有且只有一个父结点；
4. 4.除了根结点外，每个子结点可以分为多个不相交的子树；

树结构是一种非线性存储结构，存储的是具有“一对多”关系的数据元素的集合。

树的关键特性和重点概念：

• 树的层次计算规则：根结点所在的那一层记为第一层，其子结点所在的就是第二层，以此类推。
• 结点和树的“高度”计算规则：叶子结点高度记为1，每向上一层高度就加1，逐层向上累加至目标结点时，所得到的的值就是目标结点的高度。树中结点的最大高度，称为“树的高度”。
• “度”的概念：一个结点开叉出去多少个子树，被记为结点的“度”。比如我们上图中，根结点的“度”就是3。
• 叶子结点：叶子结点就是度为0的结点。在上图中，最后一层的结点的度全部为0，所以这一层的结点都是叶子结点。

二叉树

二叉树是指满足以下要求的树：

树可以有多个节点，但是二叉树必须要有两个节点

• 它可以没有根结点，作为一棵空树存在
• 如果它不是空树，那么必须由根结点、左子树和右子树组成，且左右子树都是二叉树。如下图：

在 JS 中，二叉树使用对象来定义。它的结构分为三块：

• 数据域
• 左侧子结点（左子树根结点）的引用
• 右侧子结点（右子树根结点）的引用

在定义二叉树构造函数时，我们需要把左侧子结点和右侧子结点都预置为空：

// 二叉树结点的构造函数 
function TreeNode(val) { 
    this.val = val; 
    this.left = null;
    this.right = null; 
}
// 当你需要新建一个二叉树结点时，直接调用构造函数、传入数据域的值就行了：\
const node  = new TreeNode(1)

如此便能得到一个值为 1 的二叉树结点，从结构上来说，它长这样：

以这个结点为根结点，我们可以通过给 left/right 赋值拓展其子树信息，延展出一棵二叉树。因此从更加细化的角度来看，一棵二叉树的形态实际是这样的：

了解这些基础知识，为下面二叉树的遍历做准备