定义：假设高度为h，那么前h-1层都是满的，最后一层，从左向右，连续集中在最左边；k层的完全二叉树总节点个数最小为2^k-1，最大节点个数为2^(k-1)
可以从数组形式存储的方面来考虑，数组形式存储的完全二叉树，如果元素下标为i，那么其左子树在2i+1，右子树在2i+2，父节点在floor((i-1)/2)
如下图所示：
1
/ \
2 3
/ \ / \
4 5 6 7
/ \ / \
8 9 10 11
这是一颗完全二叉树，如果去掉7、8、9，数组形式的存储约束就被破坏了：
1
/ \
2 3
/ \ /
4 5 6
/ \ / \
8 9 10 11
1
/ \
2 3
/ \ / \
4 5 6 7
/ / \
8 10 11
用一个例题来解释：
设一棵完全二叉树共有699个结点，则在该二叉树中的叶子结点数为多少？
(13) 设一棵完全二叉树共有699个结点，则在该二叉树中的叶子结点数为______。() A. 349 B. 350 C. 255 D. 351
满意回答 B：350
首先你得知道什么叫完全二叉树！ 完全二叉树(Complete Binary Tree)
若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的节点都连续集中在最左边，这就是完全二叉树。 完全二叉树是由满二叉树而引出来的。对于深度为K的，有N个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。
做这种题目你要知道二叉树的两个特点！第k层的节点个数最多2^(k-1)个，高度为k层的二叉树，最多2^k-1个节点！
则在本题目中，共699个节点，因为是完全二叉树，2^k-1>699>2^(k-1)，所以高度为10，可以确定1到9层全满，节点总算为511，剩下的188个肯定为叶子节点！第10层上的188个节点挂在第九层的188/2=94个节点上，则第九层剩下的2^（9-1）-94=162个也为叶子节点，最后总共188+162=350个叶子节点！
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
