完全二叉树

更新时间:2024-05-03 08:29

一棵深度为k的有n个结点的二叉树,对树中的结点按从上至下、从左到右的顺序进行编号,如果编号为i(1≤i≤n)的结点与满二叉树中编号为i的结点在二叉树中的位置相同,则这棵二叉树称为完全二叉树。

定义

一棵深度为k且有 个结点的二叉树称为满二叉树。

根据二叉树的性质2, 满二叉树每一层的结点个数都达到了最大值, 即满二叉树的第i层上有 个结点 (i≥1) 。

如果对满二叉树的结点进行编号, 约定编号从根结点起, 自上而下, 自左而右。则深度为k的, 有n个结点的二叉树, 当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时, 称之为完全二叉树。

满二叉树和完全二叉树的定义可以看出, 满二叉树是完全二叉树的特殊形态, 即如果一棵二叉树是满二叉树, 则它必定是完全二叉树。

性质

1、具有n个结点的完全二叉树的深度(注:[ ]表示向下取整)

2、如果对一棵有n个结点的完全二叉树的结点按层序编号, 则对任一结点i (1≤i≤n) 有:

特点

完全二叉树的特点:叶子结点只能出现在最下层和次下层,且最下层的叶子结点集中在树的左部。需要注意的是,满二叉树肯定是完全二叉树,而完全二叉树不一定是满二叉树。

完全二叉树判定

算法思路

判断一棵树是否是完全二叉树的思路

1>如果树为空,则直接返回错

2>如果树不为空:层序遍历二叉树

2.1>如果一个结点左右孩子都不为空,则pop该节点,将其左右孩子入队列;

2.1>如果遇到一个结点,左孩子为空,右孩子不为空,则该树一定不是完全二叉树;

2.2>如果遇到一个结点,左孩子不为空,右孩子为空;或者左右孩子都为空,且则该节点之后的队列中的结点都为叶子节点,该树才是完全二叉树,否则就不是完全二叉树;

代码实现

免责声明
隐私政策
用户协议
目录 22
0{{catalogNumber[index]}}. {{item.title}}
{{item.title}}