Question

数据结构完全二叉树问题

一棵完全二叉树的第9层有200个叶结点，则该完全二叉树最多有【】个结点

Answer 1

楼上不准确，得出的是最少结点数
完全二叉树叶子结点可以出现在最下两层
设根结点层次为1，完全二叉树第9层有200个叶子，第9层结点个数最多就是满二叉树，共有2^(9-1)=256个结点，因此第9层并不都是叶子
考虑到是计算最多结点，因此，可以认为第9层不是最下层，也就是说该完全二叉树的高度为10，第9层剩下的256-200=56个结点都是度为2，这样第10层的结点个数是2*56=112
所以结点总数= 1 + 2 + 4 + 8 + 16 + 32 + 64 + 128 + 256 + 112 = (2 ^ 9 - 1) + 112 = 511 + 112 = 623

Answer 2

满2叉树第9层最多2^8个及256个叶节点，所以该完全二叉树一共1+2+4+8+16+32+64+128+200=455

追问

答案是这几个中的哦：A．256 B．511 C．623 D．1000