数据结构:二叉树经典例题(单选题)-->你真的掌握二叉树了吗?(第一弹)

这篇具有很好参考价值的文章主要介绍了数据结构:二叉树经典例题(单选题)-->你真的掌握二叉树了吗?(第一弹)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

朋友们、伙计们,我们又见面了,本期来给大家解读一下有关二叉树的经典例题,如果看完之后对你有一定的启发,那么请留下你的三连,祝大家心想事成!

C 语 言 专 栏:C语言:从入门到精通

数据结构专栏:数据结构

个  人  主  页 :stackY、

数据结构:二叉树经典例题(单选题)-->你真的掌握二叉树了吗?(第一弹)

目录

前言:

一、

二、

三、 

四、

五、

六、

七、

八、

九、 


前言:

前面我们讲了二叉树的顺序结构 和 二叉树的链式结构,将二叉树的基本知识和实现过程都了解了一遍,那么本期我们来看看关于二叉树的经典例题都有哪些,在此之前,我们需要了解二叉树的性质,那么话不多说,我们直接开始!!!

 一、

1. 在用树表示的目录结构中,从根目录到任何数据文件,有( )通道

A.唯一一条

B.二条

C.三条

D.不一定

题解:   A

树的特点是不相交,所以不可能有多个路径同时到达一个点。

二、

2. 在一颗度为3的树中,度为3的结点有2个,度为2的结点有1个,度为1的结点有2个,则叶子结点有( )个 

A.4

B.5

C.6

D.7

题解:  C

设度为i的节点个数为ni, 该树总共有n个节点,则n=n0+n1+n2+n3. 

有n个节点的树的总边数为n-1条.

根据度的定义,总边数与度之间的关系为:n-1=0*n0+1*n1+2*n2+3*n3.

联立两个方程求解,可以得到n0 = n2 + 2n3 + 1,  n0=6

或者可以通过画图来解答:

数据结构:二叉树经典例题(单选题)-->你真的掌握二叉树了吗?(第一弹)

三、 

3. 一颗拥有1000个结点的树度为4,则它的最小深度是(  )

A.5

B.6

C.7

D.8

题解:  B

如果这棵树每一层都是满的,则它的深度最小,树的度为4,那么假设它为一个四叉树,高度为h,则这个树的节点个数为(4^h - 1) / 3,当h = 5, 最大节点数为341, 当h = 6, 最大节点数为1365,所以最小深度应该为6。

四、

4. 下列关于二叉树的叙述错误的是(   )

A.二叉树指的是深度为 2 的树

B.一个 n 个结点的二叉树将拥有 n-1 条边

C.一颗深度为 h 的满二叉树拥有 2^h-1 个结点(根结点深度为1)

D.二叉树有二叉链和三叉链两种表示方式

题解:

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

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

C正确:  正确,参照二叉树的性质

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

五、

5. 一颗完全二叉树有1001个结点,其叶子结点的个数是( ) 

A.251

B.500

C.501

D.不能确定

题解: C

该题需要用到二叉树性质:在任意二叉树中,度为0的节点都比度为2的节点多1个,即 n0 = n2 + 1另外,在完全二叉树中,如果节点总个数为奇数,则没有度为1的节点,如果节点总个数为偶数,只有一个度为1的节点。

因此:n0 + n1 + n2 = 1001 节点总数为奇数,没有度为1的节点

n0 + 0 + n2 = 2*n0-1 = 1001 n0 = 501

六、

6. 在一颗完全二叉树中,某一个结点没有其左孩子,则该结点一定(  )

A.是根结点

B.是叶结点

C.是分支结点

D.在倒数第二层

题解:

完全二叉树中如果一个节点没有左孩子,则一定没有右孩子,必定为一个叶子节点,最后一层一定为叶子节点,但是倒数第二层也可能存在叶子节点。

 七、

7. 设一棵二叉树中有3个叶子结点,有8个度为1的结点,则该二叉树中总的结点数为(  )个

A.11

B.12​

C.13

D.14

题解:

设Ni表示度为i的节点个数,则节点总数 N = N0 + N1 + N2

节点个数于节点边的关系: N个节点的树有N-1个边

边与度的关系:N - 1 = N1 + 2 * N2

故:N0 + N1 + N2 - 1 = N1 + 2 * N2

因此,得:N0 = N2 + 1

回到原题,N0 = 3,N1 = 8,可得N2 = 2。

因此答案是 3 + 8 + 2 = 13。

八、

8. 已知某二叉树的前序遍历序列为5 7 4 9 6 2 1,中序遍历序列为4 7 5 6 9 1 2,则其后序遍历序列为(  ) 

A.4 2 5 7 6 9 1

B.4 2 7 5 6 9 1

C.4 7 6 1 2 9 5

D.4 7 2 9 5 6 1

题解: C

要知道后序遍历首先得将二叉树的结构还原出来,由于前序遍历首先访问的是根节点,所以5是根节点,然后在中序遍历的结果中找到5,5的左边就是一根节点为5的一颗左子树,右边就是一颗右子树,然后再找7,7的右边和左边又是两颗树,依次类推:

故:根为: 5

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

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

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

故这棵树的结构为:

数据结构:二叉树经典例题(单选题)-->你真的掌握二叉树了吗?(第一弹)

九、 

9. 已知某二叉树的中序遍历序列为JGDHKBAELIMCF,后序遍历序列为JGKHDBLMIEFCA,则其前序遍历序列为(  )

A.ABDGHJKCEFILM

B.ABDGJHKCEILMF

C.ABDHKGJCEILMF

D.ABDGJHKCEIMLF

题解: 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

故树的结构为:

数据结构:二叉树经典例题(单选题)-->你真的掌握二叉树了吗?(第一弹)

朋友们、伙计们,美好的时光总是短暂的,我们本期的的分享就到此结束,预知后事如何请听下回分解~~~最后看完别忘了留下你们弥足珍贵的三连喔,感谢大家的支持!文章来源地址https://www.toymoban.com/news/detail-498796.html

到了这里,关于数据结构:二叉树经典例题(单选题)-->你真的掌握二叉树了吗?(第一弹)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构(八)下】二叉树经典习题

    ❣博主主页: 33的博客❣ ▶文章专栏分类: Java从入门到精通◀ 🚚我的代码仓库: 33的代码仓库🚚 🫵🫵🫵 关注我带你学更多数据结构的知识 在上一篇文章中,博主已经分享了部分二叉树的经典习题,在这篇文章中,博主将继续和大家分享二叉树的经典习题。 给定一个二叉树

    2024年04月27日
    浏览(33)
  • 二叉树经典OJ题——【数据结构】

    W...Y的主页  😊 代码仓库分享 💕  今天我们来进行二叉树的OJ练习,就是利用二叉树的前序、中序、后续以及晨序遍历的特性进行OJ训练。话不多说,来看我们的第一道题。 【leetcode 965.单值二叉树】 OJ链接  如果二叉树每个节点都具有相同的值,那么该二叉树就是 单值 二

    2024年02月07日
    浏览(45)
  • 【数据结构入门指南】二叉树顺序结构: 堆及实现(全程配图,非常经典)

    普通的二叉树是不适合用数组来存储的,因为可能会存在大量的空间浪费。 而完全二叉树更适合使用顺序结构存储。   现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储 ,需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事,一个是数据结构,一

    2024年02月12日
    浏览(36)
  • 【数据结构入门指南】二叉树链式结构的实现(保姆级代码思路解读,非常经典)

    其他数据结构不同,二叉树的增删查改接口实现的意义不大(后续搜索树的增删查改才有意义)。普通初阶二叉树更重要的是学习控制结构,为后续的AVL树、红黑树等高级数据结构打下基础。同时大部分OJ题也出在此处。 所谓二叉树遍历(Traversal)是按照某种特定的规则,依次

    2024年02月11日
    浏览(44)
  • 【数据结构-二叉树】二叉树

    💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:kuan 的首页,持续学习,不断总结,共同进步,活到老学到老 导航 檀越剑指大厂系列:全面总

    2024年02月07日
    浏览(47)
  • 数据结构:搜索二叉树 | 平衡二叉树

    博客写的代码都放在这里:gitee仓库链接 1.二叉搜索树 1.1.基本概念 二叉搜索树又称二叉排序树, 可以为空,如果不为空具有以下性质的二叉树 : 若它的左子树不为空,则左子树上所有节点的值都小于根节点的值 若它的右子树不为空,则右子树上所有节点的值都大于根节点的

    2024年01月23日
    浏览(57)
  • 【数据结构和算法】--- 二叉树(3)--二叉树链式结构的实现(1)

    在学习二叉树的基本操作前,需先要创建一棵二叉树,然后才能学习其相关的基本操作。由于现在大家对二叉树结构掌握还不够深入,且为了方便后面的介绍,此处手动快速创建一棵简单的二叉树,快速进入二叉树操作学习,等二叉树结构了解的差不多时,我们反过头再来研

    2024年01月25日
    浏览(59)
  • 【数据结构】二叉树——链式结构

    目录  一、前置声明 二、二叉树的遍历 2.1 前序、中序以及后序遍历 2.2 层序遍历 三、节点个数以及高度 3.1 节点个数 3.2 叶子节点个数 3.3 第k层节点个数 3.4 二叉树的高度/深度 3.5 查找值为x的节点 四、二叉树的创建和销毁 4.1 构建二叉树 4.2 二叉树销毁 4.3 判断二叉树

    2024年02月16日
    浏览(44)
  • 【数据结构】二叉树——顺序结构

    由于每个节点都 只有一个父节点 ,所以我们可通过双亲来表示一棵树。具体方式通过 数组的形式 实现。 根节点的下标为0 按照层序从上到下排序 每层从左向右递增 表示形式: 二维数组 数据的列标为0 ,只需确定行标,即可锁定位置 根节点的父节点下标为 -1 列标为1存父节

    2024年02月02日
    浏览(55)
  • 数据结构-二叉树-二叉树左右孩子交换(递归)

     注:本文采用队列和递归的算法进行创建和层次遍历。同时不能采用BFS和DFS,因为需要把当前根节点的左孩、右孩勾链并输入才能递归下一个根节点; 队列用于存储此时应该递归的根节点; 格式:每一行尾不能有空格; Description 根据输入利用二叉链表创建二叉树,并将所

    2024年02月04日
    浏览(50)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包