目录

• 转载声明
• 数据结构--树--二叉树
• • 定义
  • • 二叉树定义
    • 满二叉树定义 - 完全二叉树
    • 完全二叉树定义
  • 性质
  • • 非空二叉树 `叶节点 = 分支节点 + 1`
    • 非空二叉树第 `i` 层上最多有 2^i-1^ 个节点
    • 深度为 `h` 的二叉树, 最多有 2^h^ -1 个节点 ( 满二叉树 )
    • `n` 个节点的完全二叉树深度为 [log _2^n^_] + 1
    • n 节点的完全二叉树, 节点 `按照层次有序编号` , 则有

转载声明

————————————————
版权声明：本文为CSDN博主「Bee_Darker」的原创文章，遵循CC 4.0
BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/Bee_Darker/article/details/84503476

数据结构–树--二叉树

定义

二叉树定义

每个节点最多有两个子树

满二叉树定义 - 完全二叉树

• 深度为 k,且有 2^k - 1 个节点
• 叶节点除外的所有节点均含有两个子树的树
  • 除了最后一层其他都含有两个子节点

完全二叉树定义

• 除最后一层外, 所有层都是满节点
• 最后一层缺右边连续节点 ( 对应满二叉树删除其若干右节点 )

简便方法

• 将本树所有节点按一种规律编号

• 补齐为满二叉树后按同一种规律编号

如若本树所有节点与其满二叉树在节点上一 一 对应, 则为完全二叉树

性质

非空二叉树 叶节点 = 分支节点 + 1

非空二叉树第 i 层上最多有 2^i-1 个节点

深度为 h 的二叉树, 最多有 2^h -1 个节点 ( 满二叉树 )

n 个节点的完全二叉树深度为 [log 2ⁿ] + 1

假设深度为 k

如果是满二叉树则 n = 2^k -1

但可能不是完全二叉树,故 n <= 2^k -1

二叉树的中, 要想保证有 k 层, 则至少需要有 2^i-1 个节点才可满足

第 k 层上最多有 2^k-1 个节点, n >= 2^k-1

2^k-1 - 1 < n <= 2^k -1

推演得出结果

n 节点的完全二叉树, 节点 按照层次有序编号 , 则有

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-aRUJIt3t-1639901868292)(F:\tanjie_file\新建文件夹\typora\完全二叉树.png)]

根节点除外

i 双亲为 i/2

i 左孩子为 2i , 若 2i > n 则无左孩子

i 右孩子为 2i + 1 , 若 2i + 1 > n 则无右孩子

————————————————
版权声明：本文为CSDN博主「Bee_Darker」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/Bee_Darker/article/details/84503476