已知一棵树深为8的完全二叉树最下层有4个结点,计算其叶子结点数和总结点数(写出计算过程)

2025-04-04 13:15:34
推荐回答(1个)
回答1:

设根结点层次为1

按照条件,最下层(第8层)有4个结点,于是上面7层为满二叉树,有结点2^7-1=127个
于是总结点数为127+4 = 131个
因为满二叉树第7层有2^(7-1)=64个结点,最下层为4个结点,因为是完全二叉树,因此4个结点占有双亲结点数= 4/2 = 2,因此,第7层有64-2 = 62个叶子
第8层4个结点均为叶子,因此叶子总数为62+ 4 = 66