二叉树（Binary Tree）类型特点

在上一篇《树（Tree）的基本概念》 中我们了解了树中常用的一些概念名词。这一篇呢注重说一下二叉树的特点和一些概念。

二叉树的类型

附图1

binary_tree.jpg

真二叉树

真二叉树的每个节点的度要么是0，要么是2 。

以 「附图1」 为例：图中第一行的：空树、只有一个节点的树、最右侧的二叉树；第三行的二叉树都是真二叉树

满二叉树

满二叉树的每个节点的度要么是0，要么是2 ，并且所有的叶子节点都在最后一层。

以 「附图1」 为例：图中 第三行的二叉树即是真二叉树 ，又是满二叉树

完全二叉树

所有的叶子节点都在最后两层，并且叶子节点都靠左对齐。（如下：「附图A」）

附图A

tree_four.jpg

二叉树的特点

• 每个节点的度只有三中情况：0、1、2
• 每个节点的度最大为2（即最多有2颗子树）
• 每个节点的左子树和右子树是有顺序的
• 即使某一个节点只有一棵树，也要区分左子树和右子树的
• 二叉树是有序树
• 同样高度的二叉树中满二叉树的总节点数量是最多的，叶子节点数量是最多的
• 满二叉树一定是真二叉树 ，真二叉树不一定是满二叉树
• 完全二叉树从根节点到倒数第二层是一颗满二叉树
• 满二叉树一定是完全二叉树 ，完全二叉树不一定是满二叉树

附图2

tree_two.jpg

非空二叉树的第n层(n ≥ 1)，最多有 个节点

以 「附图2」 中右侧的 满二叉树为例, 推导非空二叉树的第n层最多有多少个节点：
规律为：
第一层（ n = 1 ）： = 1 个节点 ；
第二层（ n = 2 ）： = 2 个节点 ；
第三层（ n = 3 ）： = 4 个节点 ；
第四层（ n = 4 ）： = 8 个节点 ；
…………

高度为h的非空二叉树，最多有 个节点(h ≥ 1)

推导： 当 h= 4, 即非空二叉树有4层，这时的二叉树就是 「附图2」 中右侧的 满二叉树；
这时二叉树的总节点数为：
第一层1个 + 第二层2个 + 第三层4个 + 第四层8个 = 15个；
即：1+ 2 + 4 + 8 = + + + = = 15

附图3

tree_three.jpg

对于任何一个非空二叉树，如果叶子节点数量为 , 度为 2 的节点数量为 ，则有： = +

假设度为1 的节点数量为 ，二叉树的节点总数为： = + +

二叉树的边数 T = （度为1 的节点数量 + 度为 2 的节点数量的 2 倍） = （二叉树的节点总数 - 1） = （叶子节点数量 + 度为1 的节点数量 +度为2的节点数量 ）即：T = （ + * 2 ） = （ - 1） = （ + + ）

以「附图3」 中的二叉树为例推导：
A二叉树：度为1的节点数量= 0， 度为2的节点数量= 0，叶子节点数量 = 1 = 0 + 1 ；二叉树的节点总数为 1 = 1 + 0 + 0
B二叉树：度为1的节点数量= 0，度为2的节点数量= 1，叶子节点数量 = 2 = 1 + 1 ；二叉树的节点总数为 3 = 2 + 0 + 1
C二叉树：度为1的节点数量= 0，度为2的节点数量= 3 ，叶子节点数量 = 4 = 3 + 1 ；二叉树的节点总数为 7 = 4 + 0 + 3
D二叉树：度为1的节点数量= 2，度为2的节点数量= 5 ，叶子节点数量 = 6 = 7 + 1；二叉树的节点总数为 13 = 6 + 2 + 5
E二叉树：度为1的节点数量= 0，度为2的节点数量= 7 ，叶子节点数量 = 8 = 7 + 1 ；二叉树的节点总数为 15 = 8 + 0 + 7
……

假设一个满二叉树的高度为h (h ≥1 ) , 那么第n层的节点数量为 ； 叶子节点数量为 ；总节点数量为 n = = + + + ..... + ;高度 h =