数据结构之满二叉树和完全二叉树

数据结构之满二叉树和完全二叉树

引用

CSDN

1.

https://m.blog.csdn.net/m0_74811962/article/details/138346258

满二叉树和完全二叉树的概念

满二叉树

满二叉树是一种特殊的二叉树，其定义如下：

• 深度为k：即树的高度为k层
• 含有2^k - 1个结点：这是满二叉树的节点总数
• 每一层的节点数都是最大结点数：第i层的结点数为2^(i-1)
• 编号从根结点起，自上而下，从左至右：这种编号方式确保了每个节点的唯一性

完全二叉树

完全二叉树是另一种重要的二叉树类型，其定义如下：

• 深度为k：与满二叉树相同，树的高度为k层
• 含有n个结点：结点总数可以少于满二叉树
• 每个结点都与深度为k的满二叉树从编号1到n的结点一一对应：这意味着除了最后一层外，其他层的节点数都达到最大值，且最后一层的节点都集中在左侧

特征总结

• 满二叉树：每一层的节点数都达到最大值，即第i层有2^(i-1)个节点
• 完全二叉树：
• 叶子结点只可能在层级最大的两层上出现
• 对于任意结点，右分支下的最大子孙的最大层级为l，则左分支下的子孙的最大层级为l或l+1
• 从根节点开始编号，编号连续，且最后一层的节点都集中在左侧

图形示例分析

图1

• 判断：满二叉树
• 理由：满足满二叉树的基本条件，每一层的节点数都达到最大值

图2

• 判断：完全二叉树
• 理由：满足完全二叉树的条件，除了最后一层外，其他层的节点数都达到最大值，且最后一层的节点集中在左侧

图3

• 判断：非完全二叉树
• 理由：编号3下面没有子孙，但是同级的编号2下面编号5有子孙，不符合完全二叉树的从编号1到n的结点一一对应规则

图4

• 判断：非完全二叉树
• 理由：编号3下面的编号6属于右子树，虽然编号2，3它们的最大深度都为3，但是不满足从左至右的规则

图5

• 判断：非完全二叉树
• 理由：与图4类似，没有满足从左至右的条件

图6

• 判断：非完全二叉树
• 理由：与图4，5一样，都没有满足从左至右的条件

通过以上分析，我们可以清晰地理解满二叉树和完全二叉树的区别，并能够准确判断一个二叉树是否属于这两种类型。