树包括一组有限的元素,称为节点(或顶点),同时包括一组有限的有向线段,用来连接节点,称为弧。如果树是非空的,其中有一个节点没有进入的弧,该节点称为根。树中的其他节点都可以沿着从根开始的唯一路径到达,该路径是指一系列相邻连接的节点序列。树的结构通常被画成上下颠倒,根在顶部(见图12-20)。

根在顶部(见图12-20)。

我们可以把树中的顶点分成三类:根、叶子和内部节点。
表12-1显示了每种节点允许的外出弧和进入弧的数目。

从一给定节点可以直接到达(通过一个弧)的节点称为子节点;从其出发子节点可以直接到达的节点称为双亲。具有相同双亲的节点称为兄弟节点。节点的子孙是指从该节点出发可以到达的所有节点,而从其出发所有的子孙都可以到达的节点称为祖先。树中每个节点都有可能有子树。
1. 二叉树
树中的一种特殊形式的树。二叉树是一棵树,且其中没有一个节点所含有的子树的个数超过两个。换句话说,任一个节点只能有0、1或是2棵子树。这些子树被描述为左子树和右子树。图12-22给出了一棵有两棵子树的二叉树的结构。注意每一棵子树本身也是一棵二叉树。

1. 二叉树的遍历
二叉树遍历要求按照预定的顺序处理每一个节点且仅处理一次。两种常用的遍历次序是深度优先和广度优先。
(1)深度优先遍历
给定一棵由根、左子树、右子树构成的二叉树,我们可以定义6种不同的深度优先次序。计算机科学家已经在文献定义了其中三种的标准名称。另外三种没有名称但很容易导出。图12-24中给出了标准遍历。

●前序遍历。在前序遍历中,根被首先访问,接着是左子树,最后是右子树。前缀pre表示根在子树前面被处理。
●中序遍历。在中序遍历中,先处理左子树,然后是根,最后是右子树。前缀in表示根在子树之间被处理。
●后序遍历。在后序遍历中,根在左右子树都处理完后才处理。前缀post表示根在子树之后被处理。
例12.10图12-25显示了我们使用前序遍历访问树中的每个节点。图中还显示了行走次序。在前序遍历中,当我们从左边经过这个节点时,访问该节点。节点被访问的顺序是:A、B、C、D、E、F。

问题:针对上图写出中序遍历和后序遍历的节点访问顺序。

内容查看
查看价格2
点点赞赏,手留余香 给TA打赏

评论0

请先
  • a******* 登录了本站
  • u******* 加入了本站
  • 1******* 登录了本站
  • 1******* 投稿收入增加1块钱
  • 游客 购买了资源 2021年8月初,在众多目光都在关注手机、无人机等高科技领域时,世界权威调研机构欧睿的一份报告认证称“波司登羽绒服规模全球领先”。波司登2020/2021财年业绩数据显示,截至2021张某是某知名软件公司开发部的高级工程师,自2005年进入公司以来,表现十分出色,每每接到任务时总能在规定时间内按要求完成,并时常受到客户的表扬。在项目进行时还常常主动提出建议,调整计划,缩短开发周期,节约开发成本。但在最近的几个月里情况发生了变化,他不再精神饱满地接受任务了,同时几个他负责的开发项目均未能按客户要求完成,工作绩效明显下降。开发部新任经理方某根据经验判断,导致张某业绩下降的原因是知识结构老化,不再能胜任现在的工作岗位了。他立即向人力资源部提交了《关于部门人员培训需求的申请》,希望人力资源部能尽快安排张某参加相关的业务知识培训,让张某开阔一下思路。人力资源部接到申请后,在当月即安排张某参加了一个为期一周的关于编程方面的培训、研讨会。一周培训结束回到公司后,张某的状况没有出现任何改变。人力资源部主动与张某进行了面对面的沟通,发现了问题的关键。张某工作绩效下降的关键是对新上任的方经理的领导方法不满意,同时认为自己是公司的老员工,不论是工作能力还是技术能力都可以胜任部门经理的工作,但公司却没有给他晋升的机会。其实导致张某工作绩效下降的真正原因,一是与新任经理的关系不太融洽;二是因为自己没有得到晋升的机会,而不是因为知识结构的老化。
  • u******* 签到打卡,获得1元奖励
  • u******* 签到打卡,获得1元奖励
  • u******* 签到打卡,获得1元奖励
  • a******* 购买了资源 新建电大一体化公共政策概论随堂测试
  • a******* 登录了本站
  • 游客 下载了资源 国开学习网《现代汉语专题》形考任务5答案
  • u******* 签到打卡,获得1元奖励
  • 游客 购买了资源 国开学习网《现代汉语专题》形考任务5答案
  • 1******* 投稿收入增加2.5块钱
  • u******* 签到打卡,获得1元奖励
  • u******* 签到打卡,获得1元奖励
点击浏览器地址栏的⭐图标收藏本页
开放大学作业代写,需要扫码加微信
显示验证码

社交账号快速登录

微信扫一扫关注
扫码关注后会自动登录