早教吧 育儿知识 作业答案 考试题库 百科 知识分享

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

题目详情
已知一棵树深为8的完全二叉树最下层有4个结点,计算其叶子结点数和总结点数(写出计算过程)
▼优质解答
答案和解析
设根结点层次为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