特殊的二叉树及练习题

简介: 特殊的二叉树及练习题

本篇博文将介绍满二叉树和完全二叉树,二叉树的性质,二叉树常见的相关练习题

干货满满!


特殊的二叉树

满二叉树

一个二叉树,如果每一个层的结点数都达到最大值,则这个二叉树就是满二叉树。也就是说,如果一个二叉树的层数为K,且结点总数是(2^k)-1,则它就是满二叉树。

完全二叉树

完全二叉树是由满二叉树而引出来的,对于深度为K的,有n个结点的二叉树,当且仅当每一个结点都与深度K的满二叉树中编号从1至n的结点一 一对应时称之为完全二叉树。

即满二叉树是一种特殊的完全二叉树。

通俗点讲就是完全二叉树最后一层可满可不满,满了就叫满二叉树,不满就叫完全二叉树。

图片.png


解析

①首先满二叉树的结点总数是怎么得来的可以看下图,包括我们可以根据结点总数求出满二叉树的高度log以2为底(N+1),这个要记住!

②完全二叉树:前h-1层都是满的,最后一层不满,但最后一层必须是从左往右连续的。

图片.png



略微提一下搜索二叉树:这种树插入时,左子树都比根要小,右子树都比根要大。

在搜索二叉树中查找一个数,最多查找高度次。

时间复杂度: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三个性质都在上面讲过了。重点关注第三个。


二叉树练习题

图片.png

叶结点就是度为0的结点,根据上面第3个性质,直接199+1,选B。


图片.png

假设度为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


图片.png

其实完全二叉树我们不知道的就是最后一层缺了几个。

假设这棵树高度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的范围内即可。


孤衫
+关注
目录
打赏
0
0
0
0
12
分享
相关文章
|
7月前
|
【Leetcode刷题Python】103. 二叉树的锯齿形层序遍历
LeetCode上103号问题"二叉树的锯齿形层序遍历"的Python实现,使用了双端队列来实现层与层之间交替的遍历顺序。
28 3
5.二叉树详解(附习题)
5.二叉树详解(附习题)
代码随想录 Day11 二叉树 LeetCode T144,145,94 前中后序遍历 (递归解法)
代码随想录 Day11 二叉树 LeetCode T144,145,94 前中后序遍历 (递归解法)
59 0
|
10月前
|
二叉树常见题目
二叉树常见题目
45 0
代码随想录算法训练营第十三天 | LeetCode 144. 二叉树的前序遍历、LeetCode 145. 二叉树的后序遍历、LeetCode 94. 二叉树的中序遍历
代码随想录算法训练营第十三天 | LeetCode 144. 二叉树的前序遍历、LeetCode 145. 二叉树的后序遍历、LeetCode 94. 二叉树的中序遍历
73 0
【C++】二叉树题目总结
一. 前序遍历类 1、二叉树的前序遍历(非递归) 题目连接
【数据结构与算法】第十二章:线索化二叉树
在二叉树的一些应用中,常常要求在数中查找具有某种特征的结点,或者是对树中的全部结点逐一进行处理,这就提出了一个遍历二叉树的问题。本章将详细介绍二叉树的存储和遍历。
202 0
NowCoder刷题(1)【树】二叉树的遍历(含图解)
NowCoder刷题(1)【树】二叉树的遍历(含图解)
NowCoder刷题(1)【树】二叉树的遍历(含图解)
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等