Question

数据结构中二叉树的叶结点有右孩子节点吗？

这道题的解答中的“前 115 个叶结点有右孩子节点”是不是有误，叶结点不是没有孩子节点吗，这里为什么说有





Answer 1

这里问的是假设一颗树有2011个结点，其中叶子结点有116个，当它转换成二叉树后有多少结点没有右孩子结点。

根据树转换成二叉树的方法：左孩子右兄弟，以及那个图可知，所有没有兄弟的1895个结点转换成二叉树后都没有右孩子结点，加上最右边的那个叶子结点转换成二叉树后也没有右孩子结点(因为它的右边没有兄弟结点)，所以，转换成二叉树后没有右孩子结点的数量是1895+1=1896，选D。