🏷️ 知识点：二叉树遍历
设有一个双向链表 L，结构为 [p2, p1]，头结点为 head。初始时 head = cu。现要将每个结点的 p2 指向 p1 指向结点的直接后继，应该进行的操作是（ ）。
A. while(cu!=NULL) {cu->p2=cu->p1->p1; cu=cu->p1;}
B. while(cu!=NULL && cu->p2!=NULL) {cu->p2 = cu->p1->p1; cu = cu->p1;}
C. while(cu!=NULL) {if(cu->p1!=NULL) {cu->p2=cu->p1->p1; cu=cu->p1;}}
D. while(cu!=NULL) {if(cu->p1!=NULL) {cu->p2=cu->p1->p1;} else {cu->p2=NULL;} cu=cu->p1;}
[tag_link]
正确答案：D
**【解析】**题意澄清
双向链表结点结构为
[p2, p1]p1：后继指针（next）p2：需要被重新设置目标：让每个结点的
p2指向“p1所指结点的直接后继”，即：cu->p2 = cu->p1->p1若
cu->p1 == NULL（尾结点），则不存在“p1所指结点的直接后继”，此时应令：cu->p2 = NULL同时，遍历过程中必须始终推进
cu，否则会产生死循环。
逐项分析❌ A
- 问题 1：
cu->p2正是要被重新设置的指针，用它作为循环条件不合适。 - 问题 2：仍然没有判断
cu->p1 == NULL，尾结点处依然可能发生非法访问。❌ C
cu->p1 == NULL
- 对于非尾结点，令：
cu->p2 = cu->p1->p1 - 对于尾结点，令：
cu->p2 = NULL - 每轮循环最后都执行
cu=cu->p1，保证遍历能够继续向后推进，不会死循环。因此，正确答案为 D。
已知二叉树T的中序遍历为 b, e, d, f, c, a, g。层序遍历为 a, b, g, c, d, e, f。则其后序遍历序列为多少？
A. c, e, d, f, b, g, a B. c, e, f, d, b, g, a C. e, f, d, c, b, g, a D. e, g, f, d, b, c, a
[tag_link]
正确答案：C
**【解析】**首先，根据层序遍历序列a,b,g,c,d,e,f可知根节点为a。结合中序遍历b,e,d,f,c,a,g，确定左子树包含节点b,e,d,f,c，右子树仅包含g。左子树的层序序列为b,c,d,e,f，中序序列为b,e,d,f,c，因此左子树的根为b。由于b在中序中为首，故无左子树，其右子树的根为层序中下一个节点c。对于以c为根的子树，中序为e,d,f,c，故c无右子树，其左子树的根为层序中的d。对于以d为根的子树，中序为e,d,f，故d的左子节点为e，右子节点为f。因此树的结构为：
- a的左子节点为b，右子节点为g；
- b的左子节点为空，右子节点为c；
- c的左子节点为d，右子节点为空；
- d的左子节点为e，右子节点为f。后序遍历顺序为：左子树的后序、右子树的后序、根节点。左子树的后序依次为e,f,d,c,b，右子树的后序为g，根为a，故后序遍历序列为e,f,d,c,b,g,a，对应选项 C。
一棵二叉树的前序遍历序列为 1234567，它的中序遍历序列可能是（ ）。
A. 3124567 B. 1234567 C. 4135627 D. 2153647
[tag_link]
正确答案：B
前序遍历序列为 1234567，因此根节点是 1。
中序遍历的顺序是左子树、根、右子树。 对于根节点 1，在中序遍历中，所有在 1 左侧的节点构成左子树，在 1 右侧的节点构成右子树。 同时，前序遍历中根 1 之后应首先遍历左子树（如果存在），然后遍历右子树。
选项 A 的中序为 3124567，即序列 3,1,2,4,5,6,7。 此时根 1 左侧有节点 3，说明左子树非空。 但前序序列中根 1 之后是 2，而不是左子树的节点 3，这导致矛盾，因此不可能。
选项 C 的中序为 4135627，即序列 4,1,3,5,6,2,7。 根 1 左侧有节点 4，左子树非空。 但前序序列中根 1 之后是 2，而不是左子树的节点 4，同样矛盾，因此不可能。
选项 D 的中序为 2153647，即序列 2,1,5,3,6,4,7。 根 1 左侧有节点 2，左子树非空。 前序序列中根 1 之后是 2，这符合左子树根为 2 的情况。 然而，右子树的中序为 5,3,6,4,7，其根应为前序中 2 之后的 3。 但根据右子树的结构，根 3 应有左子树节点 5，因此在前序中 3 之后应先出现 5，而实际前序序列中 3 之后是 4，导致矛盾，因此不可能。
选项 B 的中序为 1234567，即序列 1,2,3,4,5,6,7。 此时根 1 左侧无节点，左子树为空，所有节点都在右子树。 右子树的结构类似：根 2 左子树为空，右子树根 3，依此类推，形成每个节点只有右孩子的向右倾斜二叉树。 这种情况下，前序遍历和中序遍历序列均为 1234567，完全匹配，因此是可能的。
综上，只有选项 B 的中序遍历序列可能对应前序遍历序列为 1234567 的二叉树。
若结点 p 与 q 在二叉树 T 的中序遍历序列中相邻，且 p 在 q 之前，则下列 p 与 q 的关系中， 不可能的是()。
|.q 是 p 的双亲
l|.q 是 p 的右孩子
q 是 p 的右兄弟
IV.q 是 p 的双亲的双亲
A. 仅| B.仅 Ⅲ
C. 仅 I 、 Ⅲ D. 仅 Ⅱ、IV
[tag_link]
正确答案：B
对于此类题，每种情况只需举出一个反例即可。如图 1 所示，q 是 p 的双亲，中 序遍历序列为 {p, q}，I 可能。如图 2 所示，q 是 p 的右孩子，中序遍历序列为 {p, q}，Ⅱ可能。如图 4 所示，q 是 p 的双亲的双亲，中序遍历序列为 {x, p, q}，IV 可能。如图 3 所示，q 是 p 的右兄弟，F 是 q 和 p 的父结点，中序遍历要求先遍历左子树，再访问根结点，最后遍历右 子树，因此一定先访问 p，再访问 F，最后访问 q，p 和 q 不可能相邻出现，II 不可能。
给定二叉树如右图所示。设 N 代表二叉树的根，L 代表根结点的左子树，R 代表根结点的右子树。若 遍历后的结点序列是3,1,7,5,6,2,4,则其遍历方式是()。
A.LRN
B.NRL
C.RLN
D.RNL
[tag_link]
正确答案：D
分析遍历后的结点序列，可以看出根结点是在中间访问，而右子树结点在左子树之前，即遍历的方式是 RNL。
本题考查的遍历方法并不是二叉树的 3 种基本 遍历方式 ，对于考生而言，重要的是要掌握遍历的思想。
在一棵非空二叉树的中序遍历序列中，根结点的右边（ ）。
A. 只有右子树上的所有结点 B. 只有右子树上的部分结点 C. 只有左子树上的部分结点 D. 只有左子树上的所有结点
[tag_link]
正确答案：A
中序遍历二叉树的顺序是：先遍历左子树，然后访问根结点，最后遍历右子树。 因此，在中序遍历序列中，根结点的左边包含左子树上的所有结点，而根结点的右边包含右子树上的所有结点。 选项 A 正确描述了根结点右边只有右子树上的所有结点； 其他选项不符合中序遍历的定义。
前序遍历和中序遍历结果相同的二叉树为（ ）。 I. 只有根结点的二叉树 II. 根结点无右孩子的二叉树 III. 所有结点只有左子树的二叉树 IV. 所有结点只有右子树的二叉树
A. 仅有 I B. I、II 和 IV C. I 和 III D. I 和 IV
[tag_link]
正确答案：D
前序遍历的顺序是根节点、左子树、右子树； 中序遍历的顺序是左子树、根节点、右子树。 要使两者结果相同，需满足序列的对应关系。
对于只有根结点的二叉树，前序和中序都仅包含根节点，序列相同，因此 I 正确。
对于根结点无右孩子的二叉树，若根结点有左孩子，则前序以根节点开头，中序以左子树节点开头，序列不同； 若左孩子也为空（即只有根结点），则与 I 相同。 因此 II 不一定成立。
对于所有结点只有左子树的二叉树（即左斜树），前序从根节点开始向下访问左孩子，中序从最左叶子开始向上访问，两者序列相反，因此 III 错误。
对于所有结点只有右子树的二叉树（即右斜树），每个节点的左子树为空，中序遍历中节点在左子树之后访问，由于左子树为空，节点立即被访问，然后访问右子树，递归地使得整个树的前序和中序序列一致，因此 IV 正确。
综上所述，I 和 IV 正确，对应选项 D。
已知一棵二叉树的树形如图，若其后序遍历为 f,d,b,e,c,a，则其先序序列为（ ）。
A. aedfbc B. acebdf C. cabefd D. dfebac
[tag_link]
正确答案：A
如下图所示。对于后序序列 fdbeca，a 为树节点的根，因此在序号 1 中，a 首先进行绘制。同时，a 节点的左子树有 4 个节点，右子树有 1 个节点，因此 fdbe 属于左子树，c 节点属于右子树，所以我们在序号 2 的树中，填充 c。a 结点左子树的后序遍历序列为 fdbe，代表 e 为左子树的根节点，因此在序号 3 的树中，填充 e。同理 e 节点的左子树有两个节点，右子树有一个节点，因此 fdb 属于左子树，e 属于右子树，在序号 4 的树中，我们填写 b。e 的左子树的后序遍历序列为 fd，则 d 为子树的根节点，因此在序号 5 的树中，我们填充 d，最后在序号 6 的图中，填充 f。先序序列为 a，e，d，f，b，c。本题答案选 A。
（本题满分 13 分）假定二叉搜索树使用二叉链表存储，存储结构如下：typedef struct BSTNode{int data;struct BSTNode *left,*right;} BSTNode;typedef BSTNode BTNode;给一棵二叉搜索树 T 和整数 K，查找树中关键字与 K 之差的绝对值最小的所有结点，并输出该绝对值与结点中的关键字。
（1）给出算法的基本思想。（4 分）
（2）使用 C/C++ 描述算法思想。（8 分）
[tag_link]
【答案】
(1)算法设计思想：由于二叉搜索树的中序遍历序列为递增序列，本算法采用中序递归遍历二叉树，并记录当前找到的最小绝对值差值 min。遍历过程中，每访问一个结点时计算目标值与当前结点值之差的绝对值：
- 若该值小于
min，则更新min； - 若该值大于或等于
min，说明后续结点的差值会更大，此时可停止查找（可通过标志变量flag控制递归终止）。最后输出所有差值为min的结点。注意：题目要求输出与目标值差的绝对值最小的所有结点，可能不止一个结点。例如下图中：结点 5、15 与目标值 10 的差的绝对值均为 5，此时应全部输出。满足条件的结点最多只可能有两个。
10
/ \
5 15
(2) 算法实现：
// 当前的绝对值差值最小值
int min = INT_MAX;
// 最小绝对值差值是否已经找到
int flag = 0;
// 存储待输出的结点关键字
int min_data[2];
int min_idx = 0;
void searchMinDiff(BTNode *root, int K) {
if (!root) return;
if (flag) return;
searchMinDiff(root->left, K);
// 中序遍历
int diff = abs(K - root->data);
if (diff < min) {
min = diff;
min_data[0] = root->data;
min_idx = 1;
} else if (diff == min) {
min_data[min_idx++] = root->data;
} else {
flag = 1;
}
searchMinDiff(root->right, K);
}
void solve(BTNode *root, int K) {
searchMinDiff(root, K);
printf("min diff: %d\n", min);
for (int i = 0; i < min_idx; i++) {
printf("min element: %d\n", min_data[i]);
}
}
(10分)二叉树的带权路径长度( WPL) 是二叉树中所有叶结点的带权路径长度之和。给定一棵二叉 树T, 采用二叉链表存储，结点结构为：
| left | weight | right |
|---|
其中叶结点的weight 域保存该结点的非负权值。设root为指向T 的根结点的指针，请设计求T的 WPL 的算法，要求：
(1)给出算法的基本设计思想；
(2)使用C 或 C++语言，给出二叉树结点的数据类型定义；
(3)根据设计思想，采用C 或 C++语言描述算法，关键之处给出注释。
[tag_link]
算法的基本设计思想： ①基于先序递归遍历的算法思想是用一个 static 变量记录 wpl，把每个结点的深度作为递归函数的一个参数传递，算法步骤如下： 若该结点是叶子结点，则变量 wpl 加上该结点的深度与权值之积； 若该结点非叶子结点，则若左子树不为空，对左子树调用递归算法，若右子树不为空，对右子树调用递归算法，深度参数均为本结点的深度参数加 1； 最后返回计算出的 wpl 即可。 ② 若考生给出能够满足题目要求的其他算法且正确，可同样给分。 ②考生答案无论使用 C 或者 C++ 语言，只要答案正确同样给分。 ③ 的标准给分。 ④若考生给出的二叉树结点的数据类型定义和算法实现中，使用的是除整型之外的其他数值，可视同使用整型类型。 ⑤若考生给出的答案中算法主要设计思想或算法中部分正确，可酌情给分。
请设计一个算法，将给定的表达式树（二叉树）转换为等价的中缀表达式（通过括号反映操作符的计算次序）并输出。例如，当下列两棵表达式树作为算法输入时：
输出的中缀表达式分别为 (a+b)*(c*(−d)) 和 (a*b)+(−(c−d)) 。
二叉树结点的定义如下：
typedef struct node{
char data[10]; // 存储操作数或操作符
struct node *left, *right;
} BTree;
要求：
(1) 给出算法的基本设计思想。
(2) 根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释。
[tag_link]
1）算法的基本设计思想表达式树的中序序列加上必要的括号即为等价的中缀表达式。可以基于二叉树的中序遍历策略得到所需的表达式。（3 分）表达式树中分支结点所对应的子表达式的计算次序，由该分支结点所处的位置决定。为得到正确的中缀表达式，需要在生成遍历序列的同时，在适当位置增加必要的括号。显然，表达式的最外层（对应根结点）及操作数（对应叶结点）不需要添加括号。（2 分）
2）算法实现（10 分）
void preorder(node *root, int depth) {
if (!root) {
return;
}
bool isRoot = (depth == 1);
bool isLeaf = (!root->left && !root->right);
if (!isRoot && !isLeaf) {
printf("(");
}
preorder(root->left, depth+1);
printf("%s", root->data);
preorder(root->right, depth+1);
if (!isRoot && !isLeaf) {
printf(")");
}
}
void solve(node *root) {
preorder(root, 1);
}
将二叉树的中序遍历递归算法稍加改造即可得本题答案。除根结点和叶结点外，遍历到其他结点时在遍历其左子树之前加上左括号，在遍历完右子树后加上右括号。【评分说明】①若考生设计的算法满足题目的功能要求，则（1)、(2) 根据所实现算法的策略及输出结果给分，评分标准见下表。
| 分数 | 备注 |
|---|---|
| 15 | 采用中序遍历算法且正确，括号嵌套正确，层数适当 |
| 14 | 采用中序遍历算法且正确，括号嵌套正确，但括号嵌套层数过多。例如，表达式最外层加上括号，或操作数加括号，如 (a) |
| 11 | 采用中序遍历算法，但括号嵌套层数不完全正确。例如，左右括号数量不匹配 |
| 9 | 采用中序遍历算法，但没有考虑括号 |
| ≤7 | 其他 |
②若考生采用其他方法得到正确结果，可参照①的评分标准给分。③如果程序中使用了求结点深度等辅助函数，但没有给出相应的实现过程，只要考生进行了必要的说明，可不扣分。④若在算法的基本设计思想描述中因文字表达没有清晰反映出算法思路，但在算法实现中能够表达出算法思想且正确的，则可参照①的标准给分。⑤若算法的基本设计思想描述或算法实现中部分正确，可参照①中各种情况的相应给分标准酌情给分。
(13分)已知非空二叉树 T 的结点值均为正整数，采用顺序存储方式保存，数据结构定义如下：
typedef struct {
Elemtype SqBiTNode[MAX_SIZE]; int ElemNum;
}SqBiTree;
//MAX_SIZE为已定义常量
// 保存二叉树结点值的数组 // 实际占用的数组元素个数
T中不存在的结点在数组SqB|TNode中用-1表示。例如，对于下图所示的两棵非空二叉树T1 和T2:
T1的存储结果如下：
T2的存储结果如下：
请设计一个尽可能高效的算法，判定一棵采用这种方式存储的二叉树是否为二叉搜索树，若是，则返回 true, 否则，返回false, 要求：
(1)给出算法的基本设计思想。
(2)根据设计思想，采用C 或C++语言描述算法，关键之处给出注释。
[tag_link]
[tag_link]
1）算法的基本设计思想 对于采用顺序存储方式保存的二叉树，根结点保存在 SqBiTNode[0] 中：当某结点保存在 SqBiTNode[i] 中时，若有左孩子，则其值保存在 SqBiTNode[2i+1] 中；若有右孩子，则其值保存在 SqBiTNode[2i+2] 中；若有双亲结点，则其值保存在 SqBiTNode[(i-1)/2] 中。 二叉搜索树需要满足的条件是：任一结点值大于其左子树中的全部结点值，小于其右子树中的全部结点值。中序遍历二叉搜索树得到一个升序序列。 使用整型变量 val 记录中序遍历过程中已遍历结点的最大值，初值为一个负整数，对二叉树进行 中序遍历 。若当前遍历的结点值小于等于 val ，则算法返回 false，否则，将 val 的值更新为当前结点的值。 2）算法实现 // val 存储中序遍历中访问到的最大值 // 返回值：当前子树是否为 BST bool solve ( SqBiTree * tree , int k , int * val ) { if ( k >= tree -> ElemNum ) { // 空结点 return true ; } // 判断左子树是否为 BST bool ret = solve ( tree , 2 * k + 1 , val ); if ( ! ret ) { return false ; } int cur_val = tree -> SqbiTNode [ k ]; if ( cur_val == - 1 ) { // 空结点 return true ; } // 判断中序序列是否递增 if ( cur_val > * val ) { * val = cur_val ; } else { return false ; } // 判断右子树是否为 BST ret = solve ( tree , 2 * k + 2 , val ); if ( ! ret ) { return false ; } return true ; }
（13 分）假设二叉树采用二叉链表存储结构存储，设计一个算法，求先序遍历序列中第 k（1≤k≤二叉树中结点个数）个结点的值，要求：
（1）给出算法的基本设计思想。
（2）写出二叉树采用的存储结构代码。
（3）根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释。
[tag_link]
【答案】
（1）算法的基本设计思想： 采用递归先序遍历二叉树，设置一个计数器记录已访问的结点数。遍历时，每访问一个结点，计数器加 1。当计数器等于 k 时，当前结点即为所求，记录其值并终止遍历；若计数器小于 k，则继续递归遍历左子树和右子树。通过递归和计数器控制，可在找到第 k 个结点后提前结束遍历，提高效率。
（2）二叉树采用的存储结构代码： // 二叉链表存储结构 typedef struct BiTNode { int data ; // 结点数据域，假设为整型 struct BiTNode * lchild ; // 左孩子指针 struct BiTNode * rchild ; // 右孩子指针 } BiTNode , * BiTree ;
（3）算法描述（C++ 语言）： // 辅助递归函数：在先序遍历中查找第 k 个结点 // 参数：node-当前结点指针，k-目标序号，count-计数器（引用传递），result-存储结果（引用传递），found-是否找到标志（引用传递） void PreOrderKthHelper ( BiTree node , int k , int & count , int & result , bool & found ) { if ( node == nullptr || found ) { return ; // 结点为空或已找到目标，直接返回 } count ++ ; // 访问当前结点，计数器加 1 if ( count == k ) { result = node -> data ; // 找到第 k 个结点，记录其值 found = true ; // 设置找到标志，提前终止遍历 return ; } PreOrderKthHelper ( node -> lchild , k , count , result , found ); // 递归遍历左子树 PreOrderKthHelper ( node -> rchild , k , count , result , found ); // 递归遍历右子树 } // 主函数：求先序遍历中第 k 个结点的值 // 参数：root-二叉树根节点指针，k-要查找的序号（1≤k≤结点总数） // 返回值：第 k 个结点的值，如果 k 无效或未找到，返回 -1（假设结点值非负） int PreOrderKth ( BiTree root , int k ) { int count = 0 ; // 计数器，初始化为 0 int result = - 1 ; // 存储结果，初始化为 -1 表示未找到 bool found = false ; // 标志位，初始为 false PreOrderKthHelper ( root , k , count , result , found ); return result ; // 返回结果 } 【解析】 算法基于递归先序遍历实现，先序遍历顺序为根结点、左子树、右子树。通过计数器 count 记录访问结点的次序，当 count 等于 k 时，当前结点即为所求。使用引用参数传递 count、result 和 found，使得递归过程中能共享和修改这些变量，并通过 found 标志提前终止遍历，避免不必要的递归调用。 二叉链表存储结构是二叉树常用的链式存储方式，每个结点包含数据域和指向左右子树的指针，便于动态管理二叉树。 算法的时间复杂度为 O(n)，其中 n 为二叉树结点数，最坏情况下需遍历所有结点（当 k 大于结点总数或为最后一个结点时），但平均情况下若 k 较小可提前结束。空间复杂度为 O(h)，h 为二叉树高度，主要由递归栈空间占用。算法简洁高效，符合先序遍历特性。