数据结构_知识点_二叉树

1. 二叉树

(1) 可以为空，即n = 0
(2) 左右有序，颠倒后是不同的树

2.特殊二叉树

(1)满二叉树（每一层结点都是满的）
(2)完全二叉树（只有最后一层结点不是满的，但是结点从左排起的）
(3)二叉排序树
(4)二叉平衡树

3.二叉树性质（会推导，记忆并能用于计算）

(1) 非空二叉树上叶子结点数等于度为2的结点数加一，即n₀ = n₂ + 1

---

推导过程：

设度为0，1，2的结点个数分别为n₀,n₁,n₂，结点总数n = n₀ + n₁ + n₂
由于每个结点的一个度便代表有一个孩子结点，所以 n = n₁ + 2 × n₂ + 1 </br>
n₀ + n₁ + n₂ = n₁ + 2 × n₂ + 1</br>
化简得 n₀ = n₂ + 1

---

(2)非空二叉树上第k层上至多有2^{k - 1}个结点(k >= 1)

---

推导过程：
参考满二叉树，因为满二叉树是同样层次二叉树中结点最多的二叉树
第一层，1个结点
第二层，2个结点
第三次，4个结点
因此，可以理解为每次都是×2

---

(3)高度为H的二叉树至多有 2^2H - 1 个结点(H >= 1)

---

推导过程：
从(2)可知，满二叉树每层的结点数为 2^{k - 1}
因而，H层的二叉树的结点总数是所有层的结点数之和
用等比数列求和公式求解可得 2^2H - 1

---

(4) 具有N个结点的完全二叉树的高度为 log₂(N + 1)向上取整 或 log₂N向下取整 + 1

---

推导过程：
从(3)可得逆推导可得

---

(5)对完全而二叉树从上到下、从左到右的顺序依次编号则有以下关系

1. 第 i 个结点（i 为偶数）的是第 i / 2个结点的左孩子
2. 第 i 个结点（i 为奇数）的是第 (i - 1) / 2个结点的右孩子
3. 第 i 个结点的左孩子是 2 × i，右孩子是 2 × i + 1
4. 第 i 个结点深度为 log₂i向下取整 + 1

4. 二叉树存储方式

1. 顺序存储结构
   从上到下，从左到右存储结点，当结点为空则占据一个位置。
2. 链式存储结构
   每个结点有左右孩子指针域，分别指向左右孩子