Question

将一棵结点总数为n，且具有m个叶结点的树转换成一棵二叉树以后,该二叉树中右子树为空的结点有( )个。

答案是n-m+1，求解答过程，谢谢。

Answer 1

将树按照孩子兄弟方法
（左指针指向孩子，右指针指向兄弟）
转化为二叉树可知
在转化的二叉树中度为2的结点个数为n-m-1个（即总结点数去掉叶子和根）
此类结点必然对应一个右孩子为空的结点（即本层最后一个结点）
根结点因为没有兄弟，所以转化为二叉树后右子树为空，加1
原本树最后一层的第一个结点因为没有下一层所以在转化为二叉树时度也为1，但是它会对应一个没有右子树的结点（即最后一层的最后一个结点），加1。
结果为n-m+1，次题还可以提问新构建的二叉树有多少层？也是n-m+1，因为每一个右子树为空的结点就是本层最后一个结点。
其中新构建二叉树中：
度为2的结点个数为n-m-1
度为1的结点个数为2m-n+1
度为0的结点个数为n-m
所以本题也可以用这三类结点个数来求解，即度为0的结点个数+1（根结点），这样就代表了原来树的层数，也就求得了没有右子树的结点个数。

Answer 2

显然该二叉树为正则二叉树，没有度为1的结点，只有度为0的叶子和度为2的分支按二叉树性质n0 = n2 + 1，因此度为2结点数为n - 1 于是该二叉树有2n-1个结点