二叉树的分类很多,其中二叉树和完全二叉树比较特殊。 据说这两个二叉树效率很高,所以这里记录几个相关的性质。
首先,是满二叉树。 形象地说,二叉树是绝对的三角形。 也就是说,其最后一层全部是叶节点,其馀各层全部是非叶节点。 用数学公式表示,该节点数n=2^k-1中的k表示深度,即层数。 也就是说,二叉树中充满的节点数是一系列的定数。 例如,1、3、7、15 .如果节点的数量不是这个序列中的数量,那么他就肯定不会被二叉树填满。 当然,相反的情况是不成立的。
由于节点数量和形状是固定的,所以公式的性质很多。
首先节点数与深度的关系n=2^k-1
第三,对所有节点进行编号(从1开始,而不是从零开始)。对于编号为I的节点,根据I的大小,可以判断他是左节点还是右节点,父节点是谁,子节点是谁。 例如,给定编号13的节点,他是基数,所以他是右节点。 节点的左右变化和数据的偶性同步变化。 他的父节点是13/2=6。 从1开始。 他左边的子节点是13*2=26,右边的子节点是13*2 1=27。 同样,也可以求出他的兄弟节点、父节点的父节点。
一般来说,这是二叉树中只要有一个节点的编号,他在整个二叉树中的位置就可以确定。 因此,我们倾向于使用顺序结构而不是连锁结构来存储二叉树。
但是,由于二叉树的节点数必须是确定的数而不是任意数,所以他的使用受到了一些限制。 为了打破另一个限制,我们定义了特殊的满二叉树——完全二叉树。
完全二叉树的节点数是任意的,形式上是有可能缺少的三角形,但缺少的部分肯定是右下角的连续部分。 这样不整人,更确切地说,他和二叉树的区别在于,他的最后一行可能不完整,但绝对是右边的连续部分缺失了。 虽然听起来有点混乱,但是用数学公式来说,对于k层的完全二叉树,其节点数的范围是2^(k-1 )-1N2^k-1;
是n(n=0)个节点的有限集合,它要么是空树(n=0),要么是由一个根节点和两个互不相交的分别被称为左子树和右子树的二叉树构成。
深度为k且具有2^k-1个节点的二叉树被称为满二叉树。
除叶节点外,所有节点都有两个子节点。 节点数已达到最大值。 所有叶子的节点必须在同一层。
设二叉树的深度为h,则除第h层以外的其他各层(1(h-1 ) )的节点数都达到最大个数,第h层的所有节点连续集中在最左边的是完全二叉树。