Question

数据结构题目（森林与二叉树）

Answer 1

森林与二叉树转换图

如上图中，有A、E、H、G四个非终端节点，我们知道森林转换成二叉树的规则是：兄弟相连，长兄为父，孩子靠左。而每个非终端节点在转换前都有孩子，A有BCD，E有F，H有J，G有HI，按照规则兄弟相连，长兄为父，一个结点会成为前面兄弟的右节点，如：BCD本来是兄弟，转换成二叉树后C成为B右孩子结点，D成为C右孩子结点。

但是，重点来了，每个非终端节点（这里指森林中不是二叉树中）的孩子中总有一个倒霉孩子（即最后一个孩子）他是没有弟弟的，所以没有人成为他的右孩子。如：A的倒霉孩子是D，E的倒霉孩子是F，H的倒霉孩子是J，G的倒霉孩子是I。那么有N个非终端节点，共有N个倒霉孩子没有右孩子结点。

另外，以上我们讨论的是非终端节点的孩子的事，现在我们再讨论二叉树整体的事。以上图中森林里一共可转换成三个二叉树，后面的二叉树的根节点在转换的时候他们的孩子只能成为他们的左孩子，右孩子都是空的，（步骤一中的AEG），这是因为就像我上面说的，右孩子只能由兄弟节点的弟弟转换，那么E是A的弟弟，G是E的弟弟，但是G没有弟弟，所以转换到最后，G的右孩子结点是空的。所以右指针域为空的一共有N+1个。

综上：有指针域为空的由N个非终端结点的最后一个孩子以及最后一个二叉树的根节点构成。这N+1个结点没有右指针域。

注意事项：以上说的N个非终端结点说的是在森里中，不要以为是二叉树的N个非终端结点。