408考研逐题详解：2009年第3题

2009年第3题

给定二叉树如图所示。设 N 代表二叉树的根，L 代表根结点的左子树，R 代表根结点的右子树。若遍历后的结点序列是 3，1，7，5，6，2，4，则其遍历方式是（ ）

A. LRN \qquad B. NRL \qquad C. RLN \qquad D.RNL

知识点提炼及解释

1. 二叉树遍历：二叉树是一种常见的数据结构，其中每个节点最多有两个子节点，通常称为左子节点和右子节点。二叉树的遍历是指按照某种顺序访问树中所有节点的过程。

2. 遍历方式：二叉树的遍历方式主要有三种：前序遍历（NLR）、中序遍历（LNR）和后序遍历（LRN），以及一种非递归的层次遍历（也称宽度优先遍历）。每种遍历方式都有特定的访问顺序。

3. RNL遍历：这是一种特殊的遍历方式，即先访问右子树，然后访问根节点，最后访问左子树。这种遍历方式在标准的二叉树遍历中不常见，但在某些特定场景下可能会用到。

详解

题目描述了一棵二叉树，并给出了一个遍历后的结点序列：3，1，7，5，6，2，4。对照此序列和二叉树，可知其遍历方式是递归遍历右子树，访问根结点，最后递归遍历左子树。故遍历方式是 RNL。

本题答案：D