二叉树分类很多,其中满二叉树哦和完全二叉树比较特殊,因为这两种二叉说效率很高,这里记录几条相关性质。
首先是满二叉树:从形象上来说满二叉树是一个绝对的三角形,也就是说它的最后一层全部是叶子节点,其余各层全部是非叶子节点,如果用数学公式表示那么其节点数n=2^k-1其中k表示深度,也就是层数。也就是说满二叉树的节点数是一系列固定的数,比如说,1,3,7,15...如果节点数不是这个序列中的数,那么他肯定不是满二叉树,当然了,反之,是不成立的。
由于它的节点数和形状固定,我们可以发现很多其数学公式性质。
首先是节点数和深度的关系 n=2^k-1
第二是第i层上的节点数为2^(i-1)
第三是给所有的节点编号(从1号开始而不是从零号开始)那没对于一个编号为i的节点我们可以根据i的大小,判断出他是左节点还是右节点,父节点是谁,子节点是谁。比如我们给一个编号13的节点,那么他是基数所以他是右节点,因为节点的左右变化和数据的基偶性是同步变化的。他的父节点是13/2=6(是从1好开始的)他的左子节点是13*2=26右子节点是13*2+1=27同理还可以求他的兄弟节点,父节点的父节点,
总而言这在满二叉树中只要有了一个节点的编号那么他在整个二叉树中的位置就确定了,正是由于这个原因,我们更倾向于使用顺序结构而不是链式结构来存储满二叉树。
然而由于满二叉树的节点数必须是一个确定的数,而非任意数,他的使用受到了某些限制,为了打破另一个限制,我们定义一种特殊的满二叉树——完全二叉树。
完全二叉树的节点个数是任意的,从形式上来说他是一个可能有缺失的三角形,但所缺部分肯定是右下角的某个连续部分。这样说不玩整,更准确来说,我们可以说他和满二叉树的区别是,他的最后一行可能不是完整的,但绝对是右方的连续部分缺失。可能听起来有点乱,用数学公式讲,对于K层的完全二叉树,其节点数的范围是2^(k-1)-1<N<2^k-1;
如果是创建完全二叉树或者满二叉树,你完全可以使用一个VECTOR或者数组来盛放。