先说结论

  • 结论：一棵分支结点（非终端结点）个数为n的树，该树对应的二叉树中无右孩子的结点（或右指针域为空的结点）个数为 n + 1。【森林对应二叉树时也适用，上述过程推导主要涉及对应后的二叉树】
  • 原始树(或森林)的叶结点个数 = 转换的二叉树中左指针域为空的个数
  • 非空指针域个数 = 总结点个数 - 1
  • 空指针域个数 = 总结点个数 + 1

🌲 一、树和二叉树的转换

我们这里讨论的是把一棵普通树（或森林）转换成一个二叉树的过程，叫做左孩子右兄弟表示法：

  • 原树的每个结点的第一个孩子，变成对应二叉树的左孩子；

  • 原树中这个结点的兄弟，变成对应二叉树的右孩子；

  • 所以在转换后的二叉树中，每个结点最多只有两个指针：一个指向第一个孩子（左），一个指向下一个兄弟（右）。

🧠 二、理解“无右孩子的结点 = 分支结点数 + 1”

我们要证明的是：

一棵有 n 个分支结点（非叶子结点）的树，转换成二叉树后，“没有右孩子”的结点个数 = n + 1。

这个怎么来的呢？我们来推导一下。

🧱 第一步：理清二叉树中左右指针的含义

在转换后的二叉树中：

  • 左指针 → 指向原树的第一个孩子；

  • 右指针 → 指向原树中同一层的下一个兄弟。

🧩 第二步：统计“无右孩子”的结点

也就是说，我们现在要数一数：

在转换后的二叉树中，右指针是空（即没有右孩子）的结点有多少个？

可以理解成：一个兄弟链中的最后一个人，因为他右边没有兄弟了。

假设你有这样的兄弟关系：

1
A ——> B ——> C ——> D

这是原树中的兄弟序列，转换成二叉树后变成：

1
2
3
4
A（右 -> B）
B（右 -> C）
C（右 -> D）
D（右 -> 空） ← 没右孩子！

每一串兄弟链中，只有最后一个人没有右孩子。

那么，每有一串兄弟，就会有一个“没有右孩子”的结点。

🧮 第三步：有多少个兄弟链？

你可以发现，每一个父节点会产生一串兄弟（即多个孩子）。

比如说：

  • 一个父节点有3个孩子，那这3个孩子组成一个兄弟链；

  • 这个兄弟链会有1个“没有右孩子”的结点（即最后一个孩子）；

所以，每一个分支结点（有孩子的结点）会对应一个兄弟链，而这个链中有1个结点是“没有右孩子的”。

所以：

  • 有 n 个分支结点 → 有 n 个兄弟链；

  • 每个兄弟链最后一个人没有右孩子 → 有 n 个这样的结点。

💡但为什么是 n + 1 呢？

还有一个结点“没有右孩子”是从哪来的？

因为原树（或森林）可以有多个树根！

  • 如果是一棵树，那么它的根节点本身就没有兄弟；

  • 如果是森林，那么每棵树的根构成一个新的“兄弟链”。

所以：

森林中这些树根的兄弟链，也算一个兄弟链，它的最后一个根也“没有右孩子”。

👉 总结：

  • 每个分支结点 → 一个兄弟链 → 产生 1 个“没有右孩子”的结点；

  • 根结点的兄弟链（森林中）也算一个 → 再多 1 个“没有右孩子”的结点；

所以总数是：n + 1

✅ 其它结论解释：

1. 原始树（或森林）的叶结点个数 = 转换的二叉树中左指针为空的个数

  • 原始树中，叶子结点是没有孩子的；

  • 转换后，它们就没有左孩子；

  • 所以左指针是空的。

✅ 所以两者个数相同。

2. 非空指针域个数 = 总结点个数 - 1

这也是树结构的一个经典结论：

  • 一棵树有 n 个结点，就有 n - 1 条边；

  • 每条边对应一个“非空指针”（左或右指针）；

  • 所以非空指针个数就是 n - 1。

3. 空指针域个数 = 总结点个数 + 1

在一棵二叉树中，每个结点有两个指针（左、右）：

  • 总共有 2n 个指针域（n 个结点 × 2）；

  • 其中 n - 1 是非空的（上一条结论）；

  • 剩下的就是空指针了：2n - (n - 1) = n + 1

✅ 所以空指针域 = 总结点数 + 1。

📌 总结一句话：

一棵有 n 个分支结点的树（或森林），转换成二叉树后，“没有右孩子”的结点个数是 n + 1，这是因为每个分支结点的孩子兄弟链尾部 + 整个森林的根兄弟链尾部，一共 n + 1 个结点右指针为空。