信息学奥赛初赛天天练-24-二叉树、N叉树遍历技巧与前缀表达式、中缀表达式、后缀表达式应用实战演练

PDF文档公众号回复关键字:20240609

单项选择题（共15题，每题2分，共计30分：每题有且仅有一个正确选项）

5 根节点的高度为1，一根拥有2023个节点的三叉树高度至少为（ ）。

A 6

B 7

C 8

D 9

8 后缀表达式 6 2 3 + – 3 8 2 / + * 2 ^ 3 + 对应的中缀表达式是（ ）

A ((6 - (2 + 3)) * (3 + 8 / 2)) ^ 2 + 3

B 6 - 2 + 3 * 3 + 8 / 2 ^ 2 + 3

C (6 - (2 + 3)) * ((3 + 8 / 2) ^ 2) + 3

D 6 - ((2 + 3) * (3 + 8 / 2)) ^ 2 + 3

2 相关知识点

1) 树

线性结构(数组、链表等)中节点是首位相接一对一关系，在树结构中节点之间不再是简单的一对一关系，而是较为复杂的一对多的关系

数据结构中的 树 的名字由来，是因为如果把节点之间的关系直观展示出来，由于长得和现实世界中的树很像，由此得名

2) 二叉树

每个结点至多拥有两棵子树(即二叉树中不存在度大于2的结点)，并且，二叉树的子树有左右之分，其次序不能任意颠倒

例如下面是一棵二叉树

3) n叉树

每个结点至多拥有n棵子树(即n叉树中不存在度大于n的结点)

如下是1棵三叉树

4) 二叉树的遍历

常见的二叉树的遍历主要有3种，先序遍历，中序遍历，后序遍历，层序遍历

先序遍历

先序遍历又叫先根遍历，遍历的顺序为根，左孩子，右孩子

下面二叉树的前序遍历顺序为 ABDHIEJCFKG

中序遍历

中序遍历又叫中根遍历，遍历的顺序为左孩子，根，右孩子

下面二叉树的中序遍历顺序为 HDIBJEAFKCG

后序遍历

后序遍历又叫后根遍历，遍历的顺序为左孩子，右孩子，根

下面二叉树的后序遍历顺序为 HIDJEBKFGCA