Question

已知完全二叉树第8层有8个叶子结点则完全二叉树的叶子结点数是多少说明计算过程

xiang xi bu zhou

Answer 1

有7层,那8个在6层的叶节点是因为没有孩子才成为叶结点的.6层是满的,前24个节点都有孩子,因此这棵树每一层的节点数分别为1,2,4,8,16,32,48.所以最多有111个
设二叉树根结点层次为1
按照题意，该完全二叉树高度为8，且第8层的8个都是叶子
因此第7层的双亲数为上取整(8/2) = 4
第7层有结点数为2^(7-1) = 64，这样第7层还有64-4 = 60个结点都是叶子
因此叶子结点总数为60+8 = 68个
完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树

Answer 2

如果是七层满二叉树，叶子结点有2^7，第八层又有8个，用了七层的4个结点，所以，总共有2^7+4个结点

Answer 3

第8层8个叶节点使第7层少了4个叶节点，第7层有2^6个结点，所以2^6-4+8 = 68个叶节点

Answer 4

叶子结点计算公式是2^n-2。这个题第八层有八个节点说明前七层是满二叉树有2^7-2。所以总节点个数是2^7-2+8=134。

Answer 5

2^8+8=264