2025-07-27-二叉树

重要性质

1. 若根节点的层数为 $1$，那么第 $i$ 层的节点个数最多为 $2^{i-1}$

2. 若只有根节点的深度为 $1$，那么深度为 $k$ 的总节点的个数最多为 $2^k-1$

3. 二叉树 叶子节点的个数 = 度为 2 的节点个数 + 1 即 $N_0=N_2+1$

   令 $N$ 为节点总个数，$E$ 是边的总数，$N_0$ 为度为 0 的节点, $N_1$ 为度为 1 的节点, $N_2$ 为度为 2 的节点

   由于 除了根节点以外的的节点都有且只有一个父节点，所以 $E=N-1$

   显然 $E=0\ast N_0+1\ast N_1+2\ast N_2$

   得出 $N_1+2\ast N_2=N-1=N_0+N_1+N_2-1$

   所以 $N_2=N_0-1$

4. 具有 $n$ 个节点的二叉树，它的深度 $k$ 为 ${\log }_{2}n+1$ 的向上取整

5. 具有 $n$ 个节点的二叉树，若从 $0$ 开始标记下标，从上到下，从左到右依次取下标，那么满足以下的性质

   • 如果父亲节点的下标是 $p$，那么左孩子节点的下标是 $2^p+1$，右孩子节点的下标是 $2^p+2$
   • 如果孩子节点的下标是 $c$, 那么父亲节点的下标是 $\frac{c-1}{2}$ （忽略小数，只保留整数）
   • 由于有效的下标 $i$ 是要满足 $i<n$ 这个条件，那么如果 $2^p+1⩾n$ 或者 $2^p+2⩾n$，就说明没有左/右孩子

问题

在具有 2n 个结点的完全二叉树中，叶⼦结点个数为（ ）

• 问题

  2.在具有 2n 个结点的完全⼆叉树中，叶⼦结点个数为（ ）
  A n
  B n+1
  C n-1
  D n/2

• 解释：

  1. 节点为偶数个的完全二叉树的 度为 1 的节点个数为 1

  2. 二叉树 叶子节点的个数 = 度为 2 的节点个数 + 1

  3. 计算出结果：

     $$\{\begin{array}{rl}{N}_0& =N_2+1\\ 2n& =N_0+N_1+N_2\end{array}⟹2n=2N_2+N_1+1$$

     答案选 A

• 总结：但凡要计算节点的都需要想到 $N_0=N_2+1$ 这个公式

判断⼀棵树是不是完全⼆叉树

思路： 可以借鉴二叉树的层序遍历的思想

1. 创建一个队列，存储二叉树的根节点
2. 获取并移除队头元素，存储这个元素的左右节点
3. 反复执行这个操作，直到获取到 null 这个元素
4. 遍历队列剩余节点，如果全是 null, 那么就返回 true，否则返回 false

---

代码：

public boolean isCompleteTree(TreeNode root) {
  Queue<TreeNode> queue = new LinkedList<TreeNode>();
  queue.add(root);

  // boolean isShowNull = false; // 是否出现 null
  while (!queue.isEmpty()) {
      TreeNode node = queue.poll();
      if (node != null) {
          queue.add(node.left);
          queue.add(node.right);
      } else {
          // 如果后面还有不为空的，那么就返回 false
          // isShowNull = true;
          break;
      }
  }

  // 判断是否还有不是 空的节点
  if (!queue.isEmpty()) {
      while (!queue.isEmpty()) {
          if (queue.poll() != null) {
              return false;
          }
      }
  }
  return true;
}