树(2)
一.二叉树的性质和存储结构
性质1
在二叉树的第i层上至多有 2^(i-1) 个结点(i>=1)
至少有一个结点
性质2
深度为k的二叉树至多有 2^k - 1 个结点
至少有k个结点
性质3
对任何一棵二叉树T,如果其叶子数为n0,度为2的结点数为n2,则n0=n2+1
证明:
二.两种特殊形式的二叉树
1.满二叉树
一棵深度为k且有 2^k -1 个结点的二叉树称为满二叉树
特点:
①每一层上的结点数都是最大结点数(即每层都满)
②叶子结点全部在最底层
地位:
①满二叉树在同样深度的二叉树中结点个数最多
②满二叉树在同样深度的二叉树中叶子结点个数最多
2.完全二叉树
技巧:在满二叉树中,从最后一个结点开始,连续去掉任意个结点,即是一棵完全二叉树(注意:一定是连续的去掉)
特点:
①叶子只可能分布在层次最大的两层上。
②对任一结点,如果其右子树的最大层次为i,则其左子树的最大层次必为i或i+1
三.完全二叉树的两个性质
性质1
性质2
四.二叉树的顺序存储
1.代码表示
按满二叉树的节点层次编号,依次存放二叉树中的数据元素。
2.特点
结点间关系蕴含在其存储位置当中。但是有时候可能会过多的浪费空间,适用于存满二叉树和完全二叉树。