题目:
已知一颗有2011个结点的树,其叶结点个数为116,该树对应的二叉树中无右结点的结点数是?
答案为1896,但是我不是很明白答案得出的过程,题目的解析说用特殊值法,我还是没看懂,希望能有一个较为详细的思路过程
题目:
已知一颗有2011个结点的树,其叶结点个数为116,该树对应的二叉树中无右结点的结点数是?
答案为1896,但是我不是很明白答案得出的过程,题目的解析说用特殊值法,我还是没看懂,希望能有一个较为详细的思路过程
根据题目的信息,这棵树共有2011个结点,116个叶结点。
可以用树的性质来推导结论。
二叉树的性质:
二叉树的结点数为n(n>0)时,度数为2的结点有n/2个,度数为1的结点有(n-1)/2个,度数为0的结点有(n-2)/2个。
结合题目中给出的信息,可以得到:
度数为2的结点个数为2011/2=1005.5个
度数为1的结点个数为(2011-1)/2=1005个
度数为0的结点个数为(2011-2)/2=1004个
因此二叉树中无右结点的结点数就是度数为1的结点数,即1005个。
所以答案为:1896。
望采纳。