信息学奥赛初赛天天练-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