文章详情

短信预约软件设计师 报名、考试、查分时间动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

2021下半年软件设计师考点分析:树与二叉树

代码小侠客

代码小侠客

2024-04-18 22:45

关注

  很多考生在备考2021下半年软件设计师考试,今天编程学习网小编为大家整理了软考软件设计师考点分析:树与二叉树,供大家备考复习。

  【考法分析】

  本知识点的主要考查形式有:对数与二叉树的一些概念和特性的描述,判断其正误;对于特殊的二叉树(平衡树、哈弗曼树、满二叉树、排序树等)定义、特性的描述判断正误、或根据题干描述构造特殊的二叉树,找到对应的选项;考查二叉树的遍历结果,或根据遍历序列,找到对应的二叉树。

  【要点分析】

  1、树与二叉树的特性:

  (1)树的概念:

  双亲、孩子和兄弟:结点的子树的根称为该结点的孩子;相应地,该结点称为其子结点的双亲。具有相同双亲的结点互为兄弟

  结点的度:一个结点的子树的个数记为该结点的度

  叶子节点:也称为终端结点,指度为0的结点

  内部结点:指度不为0的结点称为分支节点或非终端节点。除根结点之外,分支结点也称为内部结点

  结点的层次:根为第一层,根的孩子为第二层,依次类推,若某节点在第i层,则其孩子结点在第i+1层

  树的高度:一颗树的最大层次数记为树的高度(深度)

  (2)二叉树的重要特性:

  1、在二叉树的第i层上最多有2i-1个结点(i≥1);

  2、深度为k的二叉树最多有2k -1个结点(k≥1);

  3、对任何一棵二叉树,如果其叶子结点数为n0,度为2的结点数为n2,则n0=n2+1。

  4、如果对一棵有n个结点的完全二叉树的结点按层序编号(从第1层到

  L log2n ˩+1层,每层从左到右),则对任一结点i(1≤i≤n),有:

  如果i=1,则结点i无父结点,是二叉树的根;如果i>1,则父结点是L i/2 ˩ ;

  如果2i>n,则结点i为叶子结点,无左子结点;否则,其左子结点是结点2i;

  如果2i+1>n,则结点i无右子叶点,否则,其右子结点是结点2i+1。

  2、特殊的树

  二叉树:二叉树是每个结点最多有两个孩子的有序数,可以为空树,可以只有一个结点。

  满二叉树:任何结点,或者是树叶,或者恰有两棵非空子树。

  完全二叉树:最多只有最小面的两层结点的度可以小于2,并且最下面一层的结点全都集中在该层左侧的若干位置。

  平衡二叉树:树中任一结点的左右子树高度之差不超过1。

  查找二叉树:又称之为排序二叉树。任一结点的权值,大于其左孩子结点,小于其右孩子结点。

  线索二叉树:在每个结点中增加两个指针域来存放遍历时得到的前驱和后继信息。

  最优二叉树:又称为哈弗曼树,它是一类带权路径长度最短的树。

  路径是从树中一个结点到另一个结点之间的通路,路径上的分支数目称为路径长度。

  树的路径长度是从树根到每一个叶子之间的路径长度之和。结点的带权路径长度为从该结点到树根之间的路径长度与该结点权值的乘积。

  树的带权路径长度为树中所有叶子结点的带权路径长度之和。

  哈弗曼树的构造:(1)根据给定的权值集合,找出最小的两个权值,构造一棵子树最为其孩子结点,二者权值之和作为根结点;(2)在原集合中删除这两个结点的权值,并引入根节点的权值;(3)重复步骤(1)和步骤(2),直到原权值集合为空。

  哈夫曼编码:根据哈夫曼树进行边长编码,编码长度与路径长度相关,左侧分支编码为0(或1),右侧分支编码为1(或0),从根结点到对应叶子结点所有路径分支上的编码记录下来,即为该叶子结点的编码。

  3、树的遍历操作:遍历是按某种策略访问树中的每个结点,且仅访问一次的过程。

  前序遍历:又称为先序遍历,按根左右的顺序进行遍历。

  后序遍历:按左右根的顺序进行遍历。

  中序遍历:按左根右的顺序进行遍历。

  层次遍历:按层次顺序进行遍历。

  【备考点拨】

  1、掌握树相关的概念和特性;

  2、掌握一些特殊的树的定义和特性;

  3、掌握哈夫曼树的构造过程,哈夫曼编码的构造。

  4、掌握树的遍历,能够根据树的遍历序列反向构造二叉树的过程。

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-考试认证-考试信息-考试报考
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯