完全二叉树

x33g5p2x  于12个月前 转载在 其他  
字(0.3k)|赞(0)|评价(0)|浏览(115)
  • 定义: 一棵深度为k的有n个结点的二叉树,对树中的结点按从上至下、从左到右的顺序进行编号,如果编号为i(1≤i≤n)的结点与满二叉树中编号为i的结点在二叉树中的位置相同,则这棵二叉树称为完全二叉树。
  • 例子:如下,

在这里插入图片描述

  • 性质:

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

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

  • 如果i=0, 则结点i是二叉树的根, 无双亲;如果i>0, 则其双亲parent (i) 是结点[(i-1)/2].

  • 如果2i+1>n, 则结点i无左孩子, 否则其左孩子lchild (i) 是结点2i + 1

  • 如果2i+2>n, 则结点i无右孩子, 否则其右孩子rchild (i) 是结点2i+2.

  • 扩展:

  • 最大堆:父节点大于子节点

  • 最小堆:父节点小于子节点

相关文章