赞
踩
满二叉树是指二叉树中每一层的结点都达到了最大值,且当二叉树有k层时,结点的总数为2^k - 1个。
完全二叉树是指当二叉树有k层时,除了最后一层外,其他层的结点个数都达到了最大值,且最后一层中结点与节点之间没有空子树,这样的二叉树称之为完全二叉树。
注意:满二叉树是一种特殊的完全二叉树。
1. 若i>0,i位置结点的双亲序号:(i-1)/2;i=0,i为根结点编号,无双亲结点
2. 若2i+1<n,左孩子序号:2i+1,2i+1>=n否则无左孩子
3. 若2i+2<n,右孩子序号:2i+2,2i+2>=n否则无右孩子
从边的角度考虑,N个结点的任意二叉树,总共有N-1条边
因为二叉树中每个结点都有双亲,根结点没有双亲,每个节点向上与其双亲之间存在一条边
因此N个结点的二叉树总共有N-1条边
因为度为0的结点没有孩子,故度为0的结点不产生边; 度为1的结点只有一个孩子,故每个度为1的结点
产生一条边; 度为2的结点有2个孩子,故每个度为2的结点产生两条边,所以总边数为:n1+2*n2
故从边的角度考虑:N-1 = n1 + 2*n2 ②
结合① 和 ②得:n0 + n1 + n2 = n1 + 2*n2 - 1
即:n0 = n2 + 1
)
十分感谢您观看我的原创文章。
本文主要用于个人学习和知识分享,学习路漫漫,如有错误,感谢指正。
如需引用,注明地址。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。