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

请先
  • 游客 下载了资源 爱普生Epson Stylus SX525WD 驱动
  • u******* 下载了资源 2026年春江苏开放大学西方经济学060936计分作业1(占形考总成绩的20%):案例分析:大众汽车如何做到了提价多销
  • u******* 下载了资源 2026年春江苏开放大学西方经济学060936计分作业1(占形考总成绩的20%):案例分析:大众汽车如何做到了提价多销
  • 游客 下载了资源 佳能Canon PIXMA G4000 驱动
  • u******* 签到打卡,获得1元奖励
  • u******* 下载了资源 2025年春江苏开放大学知识产权总论061116第二次过程性考核作业
  • u******* 下载了资源 2024年春江苏开放大学学前教育学060516形考作业1:制定1份完整的儿童游戏记录表
  • u******* 下载了资源 2025年秋江苏开放大学学前教育学060516过程性考核作业2:以”美丽的幼儿园”为主题进行一次综合教育课程设计
  • 1******* 下载了资源 2024年春江苏开放大学污染治理设施运营与管理060124形考作业4
  • 游客 下载了资源 爱普生Epson Stylus N11 驱动
  • u******* 下载了资源 2024年春江苏开放大学学前教育学060516形考作业1:制定1份完整的儿童游戏记录表
  • 游客 下载了资源 2022 年广东省公务员考试申论真题及答案(县级卷)
  • u******* 登录了本站
  • 游客 下载了资源 爱普生Epson STYLUS PHOTO R350 打印机驱动
  • 游客 下载了资源 2014年北京市公务员考试申论真题及参考解析
  • 游客 下载了资源 爱普生Epson WorkForce WF-2850 驱动
点击浏览器地址栏的⭐图标收藏本页
需要托管,代写作业,论文扫码加微信
显示验证码

社交账号快速登录

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