一道二叉树的题，在线等，请详细一点，谢谢~~

深度为h的二叉树上只有度为o和度为2的结点，则此二叉树中所包含的结点数至少为？答案是2h-1

请详细写一下过程，说明一下思路，谢谢！~

度为二叉树的分支数目;

如果只有0度(没有节点),二度(两个节点)

那么:

我来构造一颗深度为h的二叉树

度为0就表示这个结点没有子节点,那么,所以为0的度不能构成深度;

要构成深度那么节点必须度为2!

所以根据这个原理,设计为h深度的二叉树(节点只有0度和2度);

而只有度为2的时候才能构造成为深度,那么下面我给你设计了一个图;

因为楼主好看,我直接竖着画!因为算的是最少的节点数目,在设计的时候只是考虑一条线使它充满2个节点,其他的节点就度为0(这样以便计算最少)

见下图:

由上面的图可知:

h=6

节电数目为:2*6-1=11

仔细看上面的图形和我的文字,相信你能明白这个2h-1的道理;

度为o 即是没有子节点   度为2  则表示必为2个子节点

如此  h=1  则节点为1

 h 每增加1 节点至少增加2  最多增加2^(h-1)   因此 节点至少为  2h-1

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息