【数据结构】二叉树性质巩固

ゝ一纸荒年。 2024-04-26 10:58 74阅读 0赞

![在这里插入图片描述][6ac7346dc5944908b5dd227e55fab217.gif_pic_center]

> ?write in front?  
> ?所属专栏：[初阶数据结构][Link 1]  
> ?️博客主页：[睿睿的博客主页][Link 2]  
> ?️代码仓库：?[VS2022\_C语言仓库][VS2022_C]  
> ?您的点赞、关注、收藏、评论，是对我最大的激励和支持！！！  
> **关注我，关注我，关注我**，你们将会看到更多的优质内容！！

![在这里插入图片描述][85d8f838a7524c8bb8bed80b7ac059c1.gif_pic_center]

#### 文章目录 ####

*  前言
 *  例题1.
 *  例题2.
 *  例题3.
 *  例题4.
 *  例题5.
 *  例题6.
 *  例题7.
 *  例题8.
 *  例题9.
 *  总结

## 前言 ##

在学习完二叉树以后，我们需要通过一些选择题来验收自己的学习成果。本篇博客将通过一些经典选择题带你巩固二叉树的相关性质。

## 例题1. ##

![在这里插入图片描述][d2a13ec2a91c4d8cb718082a133ea46b.png]

**答案：A**

解析：

A错误: 二叉树指最大孩子个数为2，即树的度为二的树。深度描述的为树的层数。

B正确: 对于任意的树都满足：边的条数比节点个数少1，因为每个节点都有双亲，但是根节点没有

C正确: 正确，参加二叉树性质

D正确: 二叉链一般指孩子表示法，三叉连指孩子双亲表示法，这两种方式是二叉树最常见的表示方式，虽然还有孩子兄弟表示法，该中表示方式本质也是二叉链

## 例题2. ##

![在这里插入图片描述][34a563cd3056433784d65c37411ec466.png]

**答案：D**

解析：

A: 树中的节点不能相交

B: 树的度为所有节点中度最大的节点的度

C: 树的深度为根节点到叶子节点的最大深度

## 例题3. ##

![在这里插入图片描述][33c1a8e721864c66aadcd8c90f356b91.png]  
**答案：C**

解析：

通过前序遍历找到子树的根，在中序遍历中找到根的位置，然后确定根左右子树的区间，即根的左侧为左子树中所有节点，根的右侧为右子树中所有节点。

故：根为： 5

5的左子树：4 7 5的右子树： 6 9 1 2

5的左子树的根为: 7 5的右子树的根为：9

7的左子树: 4 7的右：空 9的左子树：6 9的右子树：2

故这棵树的结构为：  
![在这里插入图片描述][90e72120e3664eeea7a5d314b399bcfb.png]

## 例题4. ##

![在这里插入图片描述][4ef5396e00ed462cae84c1d68b2f0f71.png]  
**答案：B**

解析：

由后序遍历确定子树的根，后序遍历从后向前看，最后一个元素为根，和前序遍历刚好相反，从后向前看后序遍历，应该是根，右，左，根据中序遍历确定子树的左右区间

故：根为: A

A的左子树：JGDHKB A的右子树：ELIMCF

A的左子树的根：B A的右子树的根：C

B的左子树：JGDHK B的右子树：空 C的左子树：ELIM C的右子树：F

B的左子树的根：D C的左子树根：E

D的左子树的根：G D的右子树的根：H E的右子树的根:I

故树的结构为：  
![在这里插入图片描述][ec36ab9b93b641c08c52519d78c21036.png]

## 例题5. ##

![在这里插入图片描述][c0f95787693441c18f013f1a7cc7b291.png]  
**答案：C**

解析：

前序确定根，中序找到根确定根的左右子树，最后还原二叉树为：  
![在这里插入图片描述][3ab64a7805624885897933e60a895270.png]  
前： ABDEC 中：BDEAC

所以既不是满二叉树，也不是完全二叉树

## 例题6. ##

![在这里插入图片描述][8fdacbb0b79c46ed9b34dbecfe2d569d.png]  
**答案：A**

解析：

最大深度： 即每次只有一个节点，次数二叉树的高度为n，为最高的高度

最小深度： 此树为完全二叉树， 如果是完全二叉树

根据二叉树性质，完全二叉树的高低为 h = log(n+1)向上取整

故选择A

## 例题7. ##

![在这里插入图片描述][c22f47b8361140bb9ee6b2db65e131d4.png]  
**答案：D**

解析：

**BFS:**  
**广度优先**需要把**下一步所有可能的位置全部遍历**完，才会进行**更深层次的遍历**，**广度优先一般使用队列**。**层序遍历**就是一种广度优先遍历。

**DFS：**  
**深度优先**是**先遍历完一条完整的路径**（从根到叶子的完整路径），才会向上层折返，再去遍历下一个路径，**深度优先一般使用递归**。**前序遍历**就是一种深度优先遍历。

## 例题8. ##

![在这里插入图片描述][2d5678669cc94ed1817dbb474f6d2e16.png]  
**答案：B**

解析：

首先这棵二叉树的高度一定在3~4层之间:

三层：

A(B(C,D),()), A((),B(C,D)), A(B(C,()),D), A(B((),C),D),

A(B,C(D,())), A(B,C((),D))

四层：

如果为四层，就是单边树，每一层只有一个节点，除过根节点，其他节点都有两种选择，在上层节点的左边还是右边，所以2 \* 2 \* 2共8种

总共为14种。

## 例题9. ##

![在这里插入图片描述][c694f7f2b1134d90bdfafd8741d1f73b.png]  
答案：C

解析：

前序遍历：根 左 右

后序遍历：左 右 根

从二叉树 前序 和 后序遍历结果规则中可以看出，如果树中每个节点只有一个孩子时，遍历结果肯定是反的

比如下面这前序和中序序列所构成的树的结构:

12345

54321  
![在这里插入图片描述][f59f4bab54134f58bfbb530dc164a2b7.png]

## 总结 ##

更新不易，辛苦各位小伙伴们动动小手，?三连走一走?? ~ ~ ~ 你们真的对我很重要！最后，本文仍有许多不足之处，欢迎各位认真读完文章的小伙伴们随时私信交流、批评指正！

> **专栏订阅：**  
> [每日一题][Link 3]  
> [c语言学习][c]  
> [算法][Link 4]  
> [智力题][Link 5]  
> [初阶数据结构][Link 1]  
> 更新不易，辛苦各位小伙伴们动动小手，?三连走一走?? ~ ~ ~ 你们真的对我很重要！最后，本文仍有许多不足之处，欢迎各位认真读完文章的小伙伴们随时私信交流、批评指正！

![在这里插入图片描述][55270e2552774a17a711aa978da84193.gif_pic_center]

[6ac7346dc5944908b5dd227e55fab217.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/02facf44c03b49dd8b5c7ffac4d7f977.gif
[Link 1]: https://blog.csdn.net/qq_74310471/category_12216969.html?spm=1001.2014.3001.5482
[Link 2]: https://blog.csdn.net/qq_74310471?spm=1000.2115.3001.5343
[VS2022_C]: https://gitee.com/zhangxuruihhhh/c-language-learning
[85d8f838a7524c8bb8bed80b7ac059c1.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/8b35148fff1d4a72a0425dbf42d81ca6.gif
[d2a13ec2a91c4d8cb718082a133ea46b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/099c76dcc26a4fbca3fb758ed0309bed.png
[34a563cd3056433784d65c37411ec466.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/b8b49619f8af4f76ae3549181d96a1b2.png
[33c1a8e721864c66aadcd8c90f356b91.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/5506118e2b4e436a9d3ceb4a015b3cc1.png
[90e72120e3664eeea7a5d314b399bcfb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/c5423f15387149f7b15822dcc39bbd76.png
[4ef5396e00ed462cae84c1d68b2f0f71.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/6fb1445f358245ea914f053ff0f5d577.png
[ec36ab9b93b641c08c52519d78c21036.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/58de5b1828354d03bcb37ac697845a4c.png
[c0f95787693441c18f013f1a7cc7b291.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/08ebaeefe8384820a0869fbf9975cff6.png
[3ab64a7805624885897933e60a895270.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/59f309f3e4c94ced8de2458b914a7704.png
[8fdacbb0b79c46ed9b34dbecfe2d569d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/98585a8491524e908a3bac7a1bcf2833.png
[c22f47b8361140bb9ee6b2db65e131d4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/43c76feb81b14bcbb564eb8a0f39b3ca.png
[2d5678669cc94ed1817dbb474f6d2e16.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/c4462b52bd7843e98168c646325be3fa.png
[c694f7f2b1134d90bdfafd8741d1f73b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/2b4cd70107e646b2a086ae88153aed1c.png
[f59f4bab54134f58bfbb530dc164a2b7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/5ebf88e310434cef9139812e397c9199.png
[Link 3]: https://blog.csdn.net/qq_74310471/category_12166401.html?spm=1001.2014.3001.5482
[c]: https://blog.csdn.net/qq_74310471/category_12157207.html?spm=1001.2014.3001.5482
[Link 4]: https://blog.csdn.net/qq_74310471/category_12144452.html?spm=1001.2014.3001.5482
[Link 5]: https://blog.csdn.net/qq_74310471/category_12166402.html
[55270e2552774a17a711aa978da84193.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/f2ff8432cdc043dcbbdc86b732df2507.gif