必须懂的⼆叉树公式
1、⼀般⼆叉树的性质
性质1、在⾮空⼆叉树的i层上，⾄多有2^i个结点。
性质2、⾼度为K的⼆叉树中，最多有2^(k+1)-1个结点。
性质3、对于任何⼀棵⾮空的⼆叉树，如果叶结点的个数为n0，度为2的结点个数为n2，则有n0=n2+1。二叉树公式
2、完全⼆叉树
定义：如果⼀棵⼆叉树中，只有最下⾯的两层结点度数⼩于2，其余各层结点度数都等于2，并且最下⾯⼀层的结点，都集中在该层最左边的若⼲位置上，则此⼆叉树称为完全⼆叉树。
性质1、具有n个结点的完全⼆叉树的⾼度k为[log^2n]。
性质2、对于具有n个结点的完全⼆叉树，如果按照从上（根结点）到下(叶结点)和从左到右的顺序对⼆叉树中的所有结点从0开始到n-1进⾏编号，则对于任意的下标为i的结点，有：
（1）如果i=0，则它是根结点，它没有⽗结点；如果i>0，则它的⽗结点的下标为（i-1）/2。
（2）如果2i+1<=n-1，则下标为i的结点的左⼦结点的下标为2i+1；否则，下标为i的结点没有左⼦结点。
（3）如果2i+2<=n-1，则下标为i的结点的右⼦结点的下标为2i+2；否则，下标为i的结点没有右⼦结点。
3、满⼆叉树
定义：如果⼀棵⼆叉的任何结点或者是树叶，或有两棵⾮空⼦树，则此⼆叉树称作满⼆叉树。
性质、在满⼆叉树中，叶结点的个数⽐分⽀结点个数多1。
4、扩充⼆叉树
定义：扩充⼆叉树是对⼀个已有⼆叉树的扩充，扩充后原⼆叉树的结点都变为度数为2的分⽀结点。也是就是说，如果原结点的度数为2，则不变；度数为1，则增加⼀个分⽀；度数为0，则增加两个分⽀。
性质1、在扩充⼆叉树中，外部结点的个数⽐内部结点的个数多1。
性质2、对任意扩充⼆叉树，外部路径长度E和内部路径长度I之间满⾜以下关系：E=I+2n，其中n是内部结点个数。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。