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

请先
  • 游客 下载了资源 2015年黑龙江公务员考试《行测》卷答案及解析
  • 游客 下载了资源 2020年1011新疆公务员考试《行测》真题参考答案及解析
  • 游客 下载了资源 2020年0822贵州公务员考试《行测》真题参考答案及解析
  • 游客 下载了资源 坐立不安的僵尸钥匙扣3d打印图纸
  • 游客 下载了资源 2009年广东公务员考试《行测》真题答案及解析
  • 游客 下载了资源 2004年广东公务员考试《行测》真题(下半年)答案及解析
  • 游客 下载了资源 2019年420联考《行测》真题(河南县级以上)答案及解析
  • 游客 下载了资源 2013年广东公务员考试《行测》三卷答案及解析
  • 游客 下载了资源 2015年黑龙江公务员考试《申论》及参考答案(公检法B)
  • u******* 签到打卡,获得1元奖励
  • u******* 签到打卡,获得1元奖励
  • u******* 签到打卡,获得1元奖励
  • 游客 下载了资源 2009年黑龙江省申论(A卷)真题及参考答案
  • u******* 签到打卡,获得1元奖励
  • u******* 签到打卡,获得1元奖励
  • 游客 下载了资源 2019年广东公务员考试《行测》真题(县级)答案及解析
点击浏览器地址栏的⭐图标收藏本页
需要托管,代写作业,论文可以扫码加微信
显示验证码

社交账号快速登录

微信扫一扫关注
如已关注,请回复“登录”二字获取验证码