数据结构完全二叉树问题

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

chiconysun · 2018-4-30 01:13:05

楼上不准确，得出的是最少结点数
完全二叉树叶子结点可以出现在最下两层
设根结点层次为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

木卫29 · 2018-4-30 01:13:06

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

数据结构完全二叉树问题

2 个回复