- **节点的高度**：节点到叶子节点的最长路径。高度是从下往上度量。

- **节点的深度**：根节点到该节点的最长路径。深度是从上往下度量。

- **节点的层次**：节点的深度 + 1。

- **树的高度**：根节点的高度。

- 度为 m 的树中第 `i` 层上至多有 $$m^{i-1}$$ 个节点（$$i ≥ 1$$）。

二叉树中的每个节点最多有两个子节点，分别是**左子节点**和**右子节点**。

除了叶子节点之外，每个节点都有左右两个子节点，这种二叉树就叫作**满二叉树**。

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

存储一棵二叉树，有两种方法，一种是基于指针或者引用的二叉链式存储法，一种是基于数组的顺序存储法。

**二叉链式存储法**

每个节点有三个字段，其中一个存储数据，另外两个是指向左右子节点的指针。

**顺序存储法**

如果节点 X 存储在数组中下标为 i 的位置，下标为 2 _ i 的位置存储的就是左子节点，下标为 2 _ i + 1 的位置存储的就是右子节点。反过来，下标为 i/2 的位置存储就是它的父节点。通过这种方式，我们只要知道根节点存储的位置（一般情况下，为了方便计算子节点，根节点会存储在下标为 1 的位置），这样就可以通过下标计算，把整棵树都串起来。

如果是非完全二叉树，其实会浪费比较多的数组存储空间。所以，如果某棵二叉树是一棵完全二叉树，那用数组存储无疑是最节省内存的一种方式。因为数组的存储方式并不需要像链式存储法那样，要存储额外的左右子节点的指针。这也是 为什么完全二叉树要求最后一层的子节点都靠左的原因。

二叉树的遍历有三种方式：

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

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

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

第一种情况是，如果要删除的节点没有子节点，我们只需要直接将父节点中，指向要删除节点的指针置为 null。

第二种情况是，如果要删除的节点只有一个子节点（只有左子节点或者右子节点），我们只需要更新父节点中，指向要删除节点的指针，让它指向要删除节点的子节点就可以了。

第三种情况是，如果要删除的节点有两个子节点，这就比较复杂了。我们需要找到这个节点的右子树中的最小节点，把它替换到要删除的节点上。然后再删除掉这个最小节点，因为最小节点肯定没有左子节点（如果有左子结点，那就不是最小节点了），所以，我们可以应用上面两条规则来删除这个最小节点。

不管操作是插入、删除还是查找，**时间复杂度其实都跟树的高度成正比，也就是 O(log n)**。