二叉树

如果在有向树中，每个节点的出度小于或等于 2，则该树称为二叉树。 由节点（空树）组成的树也是二叉树。 二叉树如图所示

基本术语

根: 二叉树有一个唯一的节点，称为树的根。

左子节点: 根节点左边的节点称为其左子节点。

右子节点: 根节点右边的节点称为其右子节点。

父节点: 具有左子节点或右子节点或两者的节点称为节点的父节点。

兄弟节点: 具有相同父节点的两个节点称为兄弟节点。

叶子节点: 没有子节点的节点称为叶子节点。 二叉树中叶子节点的数量可以从一个（最小值）到树中顶点数的一半（最大值）不等。

后代: 如果一个节点是另一个节点的子节点，或者该节点是某个其他后代的子节点，则该节点称为另一个节点的后代。 树中的所有节点都是根的后代。

左子树: 根是某个节点的左子节点的子树称为该节点的左子树。

示例: 对于如图所示的树

• 哪个节点是根？
• 哪些节点是叶子节点？
• 说出每个节点的父节点

解决方案: (i) 节点 A 是根节点。
(ii) 节点 G、H、I、L、M、N、O 是叶子节点。
(iii) 节点             父节点
        B, C                 A
        D, E                 B
        F                      C
        G, H                 D
        I, J                    E
        K                      F
        L, M                 J
        N, O                 K

右子树: 根是某个节点的右子节点的子树称为该节点的右子树。

节点的层级: 节点的层级是它与根的距离。 根的层级定义为零。 所有其他节点的层级比其父节点多一级。 任何层级 N 的最大节点数为 2^N。

树的深度或高度: 树的深度或高度定义为树的一个分支中的最大节点数。 这大于树的最大层级，即根的深度为 1。 深度为 d 的二叉树中的最大节点数为 2^d-1，其中 d ≥1。

外部节点: 没有子节点的节点称为外部节点或终端节点。

内部节点: 具有一个或多个子节点的节点称为内部节点或非终端节点。

二叉表达式树

代数表达式可以方便地用其表达式树表示。 具有二元运算符的表达式可以分解为
      <左操作数或表达式> (运算符) <右操作数或表达式>

取决于评估的优先级。

表达式树是一棵二叉树，其根包含运算符，其左子树包含左表达式，右子树包含右表达式。

示例: 构造表达式 (a+b)*(d/c) 的二叉表达式树

解决方案: 表达式 (a+b)*(d/c) 的二叉表达式树如图所示

完全二叉树: 如果完全二叉树除了最后一层外，所有层都具有尽可能多的可能节点，并且尽可能靠左，则称为完全二叉树。 具有 n 个节点的完全二叉树的深度为 log₂ n+1。

示例: 图中所示的树是一棵完全二叉树。

满二叉树: 满二叉树是一棵二叉树，其中所有叶子节点都位于同一层级，并且每个非叶子节点都有两个子节点。

区分通用树和二叉树

通用树	二叉树
1. 不存在具有零个节点或空通用树的树。	1. 可能存在空二叉树。
2. 如果某个节点有子节点，则没有这样的区别。	2. 如果某个节点有子节点，则它被区分为左子节点或右子节点。
3. 图中所示的树是相同的，当我们将其视为通用树时。	3. 图中所示的树是不同的，当我们将其视为二叉树时，因为在 (4) 中是 2 的右子节点，而在 (ii) 中 4 是 2 的左子节点。