Page 111 - 高中 信息技术 选择性必修1 数据与数据结构

 4.3 用抽象数据类型表示二叉树

②前序遍历左子树；
③前序遍历右子树。
（2）中序遍历的操作步骤为：

若二叉树为空，则结束操作；
否则：①中序遍历左子树；
②访问根结点；
③中序遍历右子树。

（3）后序遍历的操作步骤为：
若二叉树为空，则结束操作；

否则：①后序遍历左子树；
广东教育出版社
②后序遍历右子树；
③访问根结点。
图4-9二叉树（a）的前序遍历为：ABDECFG；中序遍历为：DBEACGF；后序遍历

为：DEBGFCA。

思 考

1. 篮球淘汰赛赛制编排。小白是学生会的体育部部长，他正在组织校际篮球赛，比赛
在本校八个班（编号1A~1H）和 学校八个班（编号2A~2H）之间进行。为了缩短赛
程，小白采用淘汰赛赛制，并绘制了如图4-12所示的篮球赛冠军产生过程。这幅图是一棵
二叉树吗？它具有二叉树的特征吗？

图4-12 篮球淘汰赛赛制

2. 算术表达式树。小白上数据结构课的时候，发现可以把一个算术表达式表示成一棵
二叉树：运算符作为根结点，运算符的前后两个运算对象分别作为根的左、右两棵子树。

如把算术表达式(a+b)*(c-d/e)/f表示成二叉树，结果如图4-13所示。

103103

21X2204.indd 103 2019/9/26 13:53:28