本篇博文将介绍满二叉树和完全二叉树,二叉树的性质,二叉树常见的相关练习题。
干货满满!
特殊的二叉树
满二叉树
一个二叉树,如果每一个层的结点数都达到最大值,则这个二叉树就是满二叉树。也就是说,如果一个二叉树的层数为K,且结点总数是(2^k)-1,则它就是满二叉树。
完全二叉树
完全二叉树是由满二叉树而引出来的,对于深度为K的,有n个结点的二叉树,当且仅当每一个结点都与深度K的满二叉树中编号从1至n的结点一 一对应时称之为完全二叉树。
即满二叉树是一种特殊的完全二叉树。
通俗点讲就是完全二叉树最后一层可满可不满,满了就叫满二叉树,不满就叫完全二叉树。
解析
①首先满二叉树的结点总数是怎么得来的可以看下图,包括我们可以根据结点总数求出满二叉树的高度log以2为底(N+1),这个要记住!
②完全二叉树:前h-1层都是满的,最后一层不满,但最后一层必须是从左往右连续的。
略微提一下搜索二叉树:这种树插入时,左子树都比根要小,右子树都比根要大。
在搜索二叉树中查找一个数,最多查找高度次。
时间复杂度:O(N),N为数的结点总数。
所以搜索二叉树可能会出现一边倒的情况,如果要使左右两边的结点数据比较均匀。就会引出平衡树。
平衡树包含两种树:AVL树,红黑树。
难度较大,在这只是提一嘴~
二叉树的性质
1.若规定根结点的层数为1,则一颗非空二叉树的第i层上最多有2^(i-1)个结点。
2.若规定根结点的层数为1,则深度为h的二叉树的最大结点数是2^h - 1。
3.对任何一颗二叉树,如果度为0的结点个数为n0,度为2结点个数为n2, 则n0 = n2 + 1
4.若规定根结点的层数为1,具有n个结点的满二叉树的深度,h=log2(N+1)
以上1,2,4三个性质都在上面讲过了。重点关注第三个。
二叉树练习题
叶结点就是度为0的结点,根据上面第3个性质,直接199+1,选B。
假设度为0的结点有X0个,度为1的结点有X1个,度为2的结点有X2个。
则 X0+X1+X2 = 2n ,根据性质三把X2换成X0,即X2 = X0 -1
化简后2X0 + X1 - 1 = 2n
重点来了:观察上面的完全二叉树,我们发现度为1的结点数要么为0要么为1,即X1=1或0
由于结点数必须是整数,如果X1=0,则X0 = n + 0.5不现实。所以X1 = 1。
最后算出X0 = n
其实完全二叉树我们不知道的就是最后一层缺了几个。
假设这棵树高度h,假设最后一层缺了x个。
按照满二叉树,所有结点数是2^h -1,那么现在就是 2^h -1-x
即2^h -1-x = 531
根据性质1,最后一层最多有2^(h-1)个结点,那么x的范围就是[0 ,2^(h-1) - 1 ],意思就是你最后一层要么都不缺,算满二叉树,要么就全缺完剩一个。
接下来就将选项代入到公式的h中,计算出x的值,看是否在x的范围内即可。