Question

一棵深度为6的满二叉树有 个分支结点和 个叶子,请问应该怎么看呢?

Answer 1

求空指针域即求先孩子结点个数×2再+1（此处的1就是单分支结点的空指针域）9的完全二叉树前8层是满二叉树，共2-1＝255个结点

第9层有500-255＝245个结点（245为奇数可知其父结点一定有单分支），其父结点个数为244/2+1＝123（其中有一个单分支结点）第8层有2＝128个结点，其中叶子结点个数128-123＝5。

扩展资料：

1、完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。

2、完全二叉树特点

叶子结点只可能在最大的两层上出现,对任意结点，若其右分支下的子孙最大层次为L，则其左分支下的子孙的最大层次必为L 或 L+1；

（1）只允许最后一层有空缺结点且空缺在右边，即叶子结点只能在层次最大的两层上出现；

（2）对任一结点，如果其右子树的深度为j，则其左子树的深度必为j或j+1。 即度为1的点只有1个或0个。