二叉树的性质 (4)深度为K的满二叉树,结点个数为2k-1 ◆满二叉树:所有的结点有两个孩子,所有的叶结点 都位于同一层。 ◆满二叉树:“装满”节点的二叉树 ◆半满二叉树:深度为K的二叉树,K-1层是满二 叉树,K层节点个数不足2K-1个
二叉树的性质 ◼ （4）深度为K的满二叉树，结点个数为2 k -1 ◆满二叉树：所有的结点有两个孩子, 所有的叶结点 都位于同一层。 ◆满二叉树：“装满”节点的二叉树 ◆半满二叉树：深度为K的二叉树，K－1层是满二 叉树，K层节点个数不足2 K－1个
二叉树的性质 (5)具有n个节点的完全二叉树,深度为 [log2n]+1 ◆完全二叉树:特殊的半满二叉树,最后一层节点 从左至右依次排列,没有间断 ◆如果对节点数为n的完全二叉树自上而下,从左至 右依次编号,则节点的父结点为[i/2] ◆若2≤n,则 “若2+1 的左后继是2i; 则的右后继是 若2i>n,则话 2i+1;若2i>n 左后继 则无右后继 4)(5)(6
二叉树的性质 ◼ （5）具有n个节点的完全二叉树，深度为 [log2n]+1 ◆完全二叉树：特殊的半满二叉树，最后一层节点 从左至右依次排列，没有间断。 ◆如果对节点数为n的完全二叉树自上而下，从左至 右依次编号，则节点i的父结点为[ i / 2 ] 1 2 3 4 5 6 ◆若2i≤n，则i 的左后继是2i； 若2i>n,则i无 左后继 ◆若2i＋1≤n， 则i的右后继是 2i＋1；若2i>n, 则i无右后继
完全二叉树 关于完全二叉树的其他描述形式 ◆如果对满二叉树的节点从上至下,从左至右连续 编号,具有n个节点的完全二叉树各节点与同样深 度的满二叉树的前n个节点一一对应 ◆叶节点仅位于下两层,对任一节点,若其右子树 的深度为1,则其左子树的深度不小于1
完全二叉树 ◼ 关于完全二叉树的其他描述形式 ◆如果对满二叉树的节点从上至下，从左至右连续 编号，具有n个节点的完全二叉树各节点与同样深 度的满二叉树的前n个节点一一对应 ◆叶节点仅位于下两层，对任一节点，若其右子树 的深度为1，则其左子树的深度不小于1
二叉树 满二叉树d 半满二叉树 完全二又树 非完全二叉树Ood
二叉树 满二叉树 半满二叉树 完全二叉树 非完全二叉树