【数据结构与算法】树和二叉树课后习题

这篇具有很好参考价值的文章主要介绍了【数据结构与算法】树和二叉树课后习题。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目

题目1

知一棵树边的集合为
< I , M > , < I , N > , < E , I > , < B , E > , < B , D > , < A , B > , < G , J > , < G , K > , < C , G > , < C , F > , < H , L > , < C , H > , < A , C > {<I,M>,<I,N>,<E,I>,<B,E>,<B,D>,<A,B>,<G,J>, <G,K>,<C,G>,<C,F>,<H,L>,<C,H>,<A,C>} <I,M>,<I,N>,<E,I>,<B,E>,<B,D>,<A,B>,<G,J>,<G,K>,<C,G>,<C,F>,<H,L>,<C,H>,<A,C>
请画出这棵树并回答下列问题:

  1. 哪个是根结点?
  2. 哪些是叶子结点?
  3. 哪个是结点G的双亲?
  4. 哪些是结点G的祖先?
  5. 哪些是结点G的孩子?
  6. 哪些是结点E的子孙?
  7. 哪些是结点E的兄弟?哪些是结点F的兄弟?
  8. 结点B和N的层次号分别是什么?
  9. 树的深度是多少?
  10. 以结点C为根的子树的深度是多少?

该树形状

【数据结构与算法】树和二叉树课后习题,算法与数据结构,C/C++,数据结构,算法,c++,c语言

题目1答案

(1) 根结点:A
(2) 叶子节点:M、N、J、K
(3) 结点G的双亲:C
(4) 结点G的祖先:A、C
(5) 节点G的孩子:J、K
(6) 节点E的子孙:I、M、N
(7) 节点E的兄弟:D;节点F的兄弟:H、G
(8) 结点B和N的层次号分别是:2、5
(9) 树的深度:5
(10) 以结点C为根的子树的深度:2


题目2

一棵度为2的树与一棵二叉树有何区别?


题目2答案

  • 结构方面:一棵度为2的树的结点之间没有严格的父子关系,但二叉树中每个结点都有明确的父结点和左右结点。
  • 遍历方式:二叉树常用前序、中序、后序遍历,而度为2的树可以用更特殊的遍历方式来遍历,如:从根结点开始,先遍历左子结点、再遍历右子结点、最后递归遍历子树。

题目3

已知一棵度为k的树中有n1个度为1的结点,n2个度为2的结点,…,nk个度为k的结点,问该树中有多少个叶子结点?


题目3答案

度之和: n − 1 ① 度之和:n-1 ① 度之和:n1①
度之和: n 1 + n 2 ∗ 2 + n 3 ∗ 3.. + n m ∗ m ② 度之和:n1+n2*2+n3*3 ..+ nm*m ② 度之和:n1+n22+n33..+nmm
联立解得: n 0 = n 2 + . . . + ( k − 1 ) ∗ n k + 1 联立解得:n0=n2+...+(k-1)*nk+1 联立解得:n0=n2+...+(k1)nk+1


题目4

已知一棵含有n个结点的树中,只有度为k的分支结点和度为0的叶子结点,求该树含有的叶子结点的数目


题目4答案

设叶子结点为 x 个,度为 k 的分支结点为 n − x 个 设叶子结点为x个,度为k的分支结点为n-x个 设叶子结点为x个,度为k的分支结点为nx
【数据结构与算法】树和二叉树课后习题,算法与数据结构,C/C++,数据结构,算法,c++,c语言
故一共有 1 + ( n − k ) ∗ k 1+(n-k)*k 1+(nk)k个结点(其中1为最顶上的结点也就是根结点)
解: x = n − ( n − 1 ) / k 解: x= n-(n-1)/k 解:x=n(n1)/k


题目5

证明:一棵满k叉树上的叶子结点数n0和非叶子结点数n1之间满足下列关系: n 0 = ( k − 1 ) n 1 + 1 n_0=(k-1)n_1+1 n0=k1n1+1


题目5答案

由于是满k叉树,故只有叶子结点和度为k的非叶子结点,假设一共有n + 1层
n 1 = ( 1 − k n ) / ( 1 − k ) n_1=(1-k^n)/(1-k) n1=(1kn)/(1k)
n 0 = k n n_0=k^n n0=kn
故得证
n 0 = ( k − 1 ) n 1 + 1 n_0=(k-1)n1+1 n0=k1n1+1


结束语

  因为是算法小菜,所以提供的方法和思路可能不是很好,请多多包涵~如果有疑问欢迎大家留言讨论,你如果觉得这篇文章对你有帮助可以给我一个免费的赞吗?我们之间的交流是我最大的动力!文章来源地址https://www.toymoban.com/news/detail-524107.html

到了这里,关于【数据结构与算法】树和二叉树课后习题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 数据结构--树和二叉树

    树是一种 非线性 的数据结构,它是由n(n=0)个有限结点组成一个具有层次关系的集合。把 它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。 有一个 特殊的结点,称为根结点 ,根节点没有前驱结点。 除根节点外,其余结点被分成M(M0)个互不相交

    2024年02月12日
    浏览(41)
  • 【数据结构】树和二叉树——堆

    目录 🍉一.树的概念及结构🍉 1.树的概念 2.树的相关术语 3.树的表示 4.树在实际中的应用 🍊二.二叉树的概念和结构🍊 1.二叉树的概念  2.特殊的二叉树 2.1.满二叉树 2..2.完全二叉树 3.二叉树的性质 4.二叉树的存储结构          4.1.顺序存储 4.2.链式存储 🍎三.堆的顺序结构

    2023年04月14日
    浏览(47)
  • 数据结构-树和二叉树篇

    思维导图(基于教材) 错题复盘+计算题(基于习题解析) 课后习题 从这章开始,要是上课听不懂的话,推荐去看B站青岛大学王卓王卓老师讲解的很细节,基本上每个知识点十几二十分钟,刚开始看的时候,可能会不习惯王老师的语气词,别退出,视频重要的是老师讲解的

    2024年01月17日
    浏览(47)
  • 【Java 数据结构】树和二叉树

    篮球哥温馨提示:编程的同时不要忘记锻炼哦! 目录 1、什么是树? 1.1 简单认识树  1.2 树的概念  1.3 树的表示形式 2、二叉树 2.1 二叉树的概念 2.2 特殊的二叉树 2.3 二叉树的性质 2.4 二叉树性质相关习题 3、实现二叉树的基本操作 3.1 了解二叉树的存储结构 3.2 简单构造一棵

    2024年01月16日
    浏览(45)
  • 【数据结构之树和二叉树】

    前言: 前篇学习了 数据结构的栈和队列,那么这篇继续学习树及其相关内容基础内容。 / 知识点汇总 / 概念 :树是一种非线性结构,是由有限个节点组成的具有层次关系的集合。倒立的树模样。 有一个特殊的结点,称为根节点,根节点没有前驱。 另外的子树有且只有一个

    2024年01月16日
    浏览(55)
  • 【数据结构】树和二叉树概念

    树是一种 非线性 的数据结构,它是由n(n=0)个有限结点组成一个具有层次关系的集合。 把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。 有一个 特殊的结点,称为根结点 ,根节点没有前驱结点 除根节点外, 其余结点被分成M(M0)个互不相交

    2024年02月09日
    浏览(39)
  • 数据结构之树和二叉树

    目录 一、树简介 二、二叉树 1、简介 2、二叉树的性质 3、满二叉树和完全二叉树  三、二叉树的遍历 四、二叉树遍历代码实现 五、二叉搜索树(Binary Search Tree) 1、简介 2、二插搜索树的局限性 六、平衡二叉搜索树(AVL树) 七、红黑树(Red-Black Tree) 1、简介 2、性质 3、使

    2024年02月05日
    浏览(40)
  • 【数据结构】树和二叉树的概念及结构

      树是一种非线性的数据结构,它是由n(n=0)个有限结点组成一个具有层次关系的集合。 把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。 有一个 特殊的结点,称为根结点 ,根节点没有前驱结点。 除根节点外, 其余结点被分成M(M0)个互不相

    2024年02月13日
    浏览(38)
  • 【数据结构】——树和二叉树的相关习题

    1、设高度为h的二叉树上只有度为0和度为2的结点,则该二叉树中所包含的结点数至少为(),最多为()。 A、h ;2 h -1 B、2h-1 ; 2 h -1 C、2h+1; 2 h-1 -1 D、h+1;2 h -1 解析: (B) 最少的情况下,除了根结点该层为1个结点以外,其余h-1层都有2个结点,得2(h-1),即2(h-1)+1=2h-1。

    2024年02月03日
    浏览(43)
  • 数据结构期末复习(4)串 树和二叉树

    在数据结构中,串是由零个或多个字符组成的有限序列。它是一种线性数据结构,常用于表示和处理文本、字符串等信息。 串的特点包括: 顺序性:串中的字符按照一定的先后顺序排列,每个字符都有一个唯一的位置。 有限性:串的长度是有限的,它由字符的个数决定。

    2024年01月17日
    浏览(47)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包