介绍树之特立：二叉树

概念

二叉树（binary tree）是一种有序树结构，其特征在于每个节点的度数不超过2，属于树结构中最基础且关键的一种形式。从递归的角度定义，二叉树可以表现为两种情况：一种是空树，另一种则是由一个根节点以及两个互不重叠的子树构成的非空树，这两个子树分别被称为根节点的左子树和右子树；而左子树与右子树本身同样遵循二叉树的定义。

特殊二叉树

1.满二叉树：当二叉树的每一层节点数量均达到最大值时，该树被称为满二叉树。换句话说，若某二叉树的高度为K，并且其包含的节点总数等于(2^k) -1，则可判定其为满二叉树。如下图所示：

2.完全二叉树：需符合以下条件：所有叶节点必须位于第k层或第k-1层，同时从第1层至第k-1层的节点数量应达到最大值；第k层虽可不为满，但其包含的所有节点需排列于最左侧。需要注意的是：满二叉树属于完全二叉树的一种，但完全二叉树未必是满二叉树。

![]