前言
数（据结构）算（法）再回顾，加深记忆抗遗忘。
基本性质
- 非空二叉树的叶子节点数，等于度为 2 的节点数加 1；
- 第 k 层至多有
2^(k − 1)个节点（每层节点数可构成公比为 2 的等比数列）； - 高度为 h，至多有
2^ℎ − 1； - n 个节点的二叉链表，有 n+1 个空链域（左或右孩子指针为 NULL）；
[注]：节点的度就是节点的子节点个数，或称分支个数，考研爱考，算法题没见过。
满、完全二叉树性质
前提：根节点为 1，逐层从左到右编号，当前节点为 i；
（一）父子节点间的关系：
- 父节点：
⌊i / 2⌋； - 左子：
2 * i； - 右子：
2 * i + 1；
（二）若i ≤ ⌊n / 2⌋，则节点 i 为分支节点，否则为叶子节点。
（三）对于完全二叉树，从 1 往后遍历，若找到第一个没有右孩子的节点 i，则大于 i 的节点都是叶子节点。
[注]:数学符号⌊ x ⌋意思是向下取整；
二叉树的顺序存储
满、完全二叉树按照从根到叶，从左到右的顺序，依次存入一维数组（从数组下标 1 开始存，舍弃 0，则直接照搬前述父子编号关系式即可）。
其他二叉树添加空节点，构造成完全二叉树，再按上述顺序存入一维数组。