【数据结构】「树」专题：树、森林与二叉树遍历之间的关系+408真题

一、树、森林与二叉树的核心关系在数据结构中树、森林、二叉树三者并非孤立存在而是可以通过左孩子 - 右兄弟表示法相互转换且遍历规则存在严格对应关系这是理解整个树结构的核心基础。1.1 树与二叉树的遍历对应树普通树森林二叉树先根遍历前序遍历前序遍历后根遍历中序遍历中序遍历核心结论树的先根遍历 对应二叉树的前序遍历树的后根遍历 对应二叉树的中序遍历森林的前序遍历 对应二叉树的前序遍历森林的中序遍历 对应二叉树的中序遍历1.2 基础遍历示例1普通树的遍历左图为普通树右图为其转换后的二叉树先根遍历ABEFCDG先访问根再依次遍历子树后根遍历EFBCGDA先依次遍历子树再访问根对应二叉树的前序遍历ABEFCDG中序遍历EFBCGDA完全符合上述对应关系。2森林的遍历下图为包含 3 棵树的森林森林前序遍历ABCDEFGHJI依次对每棵树做先根遍历森林中序遍历BCDAFEJHIG依次对每棵树做后根遍历对应二叉树的前序 / 中序遍历与森林完全一致验证了转换的正确性。二、考研真题深度解析树 / 森林 / 二叉树核心考点2.1 经典选择题逐题拆解【2009】森林转二叉树的结点关系题目将森林转换为对应的二叉树若在二叉树中结点 u 是结点 v 父结点的父结点则在原来的森林中u 和 v 可能具有的关系是______。Ⅰ. 父子关系Ⅱ. 兄弟关系Ⅲ.u 的父结点与 v 的父结点是兄弟关系A. 只有 Ⅱ B. Ⅰ 和 Ⅱ C. Ⅰ 和 Ⅲ D. Ⅰ、Ⅱ 和 Ⅲ解析方法1举个例子方法2二叉树的左孩子对应原树的第一个孩子右孩子对应原树的兄弟。情况 1父子关系u 是 v 的祖父二叉树中 u→父→v对应原树中 u 是 v 的祖父的兄弟v 的父是 u 的孩子因此 u 是 v 的祖先父子关系成立。情况 2兄弟关系u 的右孩子是 v 的父v 的父的左孩子是 v对应原树中 u 和 v 的父是兄弟v 是 v 父的孩子因此 u 和 v 是叔侄兄弟关系的延伸成立。情况 3 不成立若 u 的父与 v 的父是兄弟二叉树中 u 的父的右孩子是 v 的父无法满足 u 是 v 父的父的条件。答案B【2011】树转二叉树的无右孩子结点数题目已知一棵有 2011 个结点的树其叶结点个数为 116该树对应的二叉树中无右孩子的结点个数是______。A. 115 B. 116 C. 1895 D. 1896解析方法1特殊法方法2核心公式树中无右孩子的结点数 总结点数 - 非叶结点数 1总结点数n 2011叶结点数n0 116非叶结点数n1 2011 - 116 1895无右孩子结点数 2011 - 1895 1 1896原理树中每个非叶结点的最后一个孩子、根结点在转换为二叉树后均无右孩子总数为(n - n0) 1。答案D【2014】森林转二叉树的叶结点对应关系题目将森林 F 转换为对应的二叉树 TF 中叶结点的个数等于______。A. T 中叶结点的个数B. T 中度为 1 的结点个数C. T 中左孩子指针为空的结点个数D. T 中右孩子指针为空的结点个数解析根据转换规则森林中的叶结点没有孩子因此在二叉树中左孩子指针为空右孩子可能为兄弟不为空。二叉树中左孩子为空的结点对应原森林中无孩子的结点即叶结点。答案C【2016】森林的树的个数计算题目若森林 F 有 15 条边、25 个结点则 F 包含树的个数是______。A. 8 B. 9 C. 10 D. 11解析核心公式n 个结点的树有 n-1 条边因此森林中树的个数 总结点数 - 总边数树的个数 25 - 15 10答案C【2019】树转二叉树的遍历对应题目若将一棵树 T 转化为对应的二叉树 BT则下列对 BT 的遍历中其遍历序列与 T 的后根遍历序列相同的是______。A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 按层遍历解析直接对应核心遍历关系表树的后根遍历 对应二叉树的中序遍历。答案B【2021】由二叉树遍历还原森林的树数题目某森林 F 对应的二叉树为 T若 T 的先序遍历序列是 a,b,d,c,e,g,f中序遍历序列是 b,d,a,e,g,c,f则 F 中树的棵数是______。A. 1 B. 2 C. 3 D. 4解析步骤 1由二叉树的前序 中序遍历还原二叉树前序a(根) → b,d → c,e,g,f中序b,d → a → e,g,c,f→ 根 a 的左子树为b,d右子树为c,e,g,f右子树前序c(根) → e,g → f中序e,g → c → f→ 根 c 的左子树为e,g右子树为f左子树e,g前序e(根)→g中序e→g→ e 的右孩子为 g步骤 2将二叉树转换为森林二叉树的根a是第一棵树的根a的右孩子c是第二棵树的根c的右孩子f是第三棵树的根因此森林共 3 棵树。答案C2.2 正则 k 叉树专项2016 真题题目如果一棵非空 kk≥2叉树 T 中每个非叶结点都有 k 个孩子则称 T 为正则 k 叉树。请回答下列问题并给出推导过程。1若 T 有 m 个非叶结点则 T 中的叶结点有多少个2若 T 的高度为 h单结点的树 h1则 T 的结点数最多为多少个最少为多少个1叶结点数推导总边数 总结点数 - 1树的基本性质非叶结点数为m每个非叶结点有k个孩子因此总边数 k * m总结点数n 叶结点数n0 非叶结点数m代入边数公式k * m (n0 m) - 1解得n0 k*m - m 1 m*(k-1) 12结点数的最值推导最多结点数满 k 叉树每一层都填满结点第 1 层1 个第 2 层k 个第 3 层k² 个…第 h 层k^(h-1) 个总结点数 1 k k² ... k^(h-1) (k^h - 1) / (k - 1)最少结点数每一层仅一个非叶结点其余为叶结点第 1 层1 个第 2~h 层每层 k 个结点总结点数 1 k*(h-1) k*h - k 1三、核心算法实现层序遍历、树深度、带权路径长度 WPL3.1 二叉树层序遍历求深度完整可运行代码层序遍历广度优先遍历是求二叉树深度的经典方法核心思路是按层遍历每遍历完一层深度 1。#include stdio.h #include stdlib.h #define MAXSIZE 100 // 二叉树结点定义 typedef char TreeType; typedef struct TreeNode { TreeType data; struct TreeNode *lchild; struct TreeNode *rchild; }TreeNode; typedef TreeNode* BiTree; // 队列定义用于层序遍历 typedef TreeNode* ElemType; typedef struct { ElemType *data; int front; int rear; }Queue; // 全局变量先序遍历创建二叉树的字符串#表示空结点 char str[] ABDH#K###E##CFI###G#J##; int idx 0; // 1. 先序遍历创建二叉树 void createTree(BiTree *T) { TreeType ch str[idx]; if (ch #) // 空结点 { *T NULL; } else { // 分配结点空间 *T (BiTree)malloc(sizeof(TreeNode)); (*T)-data ch; // 递归创建左、右子树 createTree((*T)-lchild); createTree((*T)-rchild); } } // 2. 初始化队列 Queue* initQueue() { Queue *q (Queue*)malloc(sizeof(Queue)); q-data (ElemType*)malloc(sizeof(ElemType) * MAXSIZE); q-front 0; q-rear 0; return q; } // 3. 判断队列是否为空 int isEmpty(Queue *Q) { return Q-front Q-rear; } // 4. 入队 int equeue(Queue *Q, ElemType e) { // 队列满判断 if ((Q-rear 1) % MAXSIZE Q-front) { printf(队列已满入队失败\n); return 0; } Q-data[Q-rear] e; Q-rear (Q-rear 1) % MAXSIZE; return 1; } // 5. 出队 int dequeue(Queue *Q, ElemType *e) { if (isEmpty(Q)) { printf(队列为空出队失败\n); return 0; } *e Q-data[Q-front]; Q-front (Q-front 1) % MAXSIZE; return 1; } // 6. 获取队列当前元素个数 int queueSize(Queue *Q) { if (isEmpty(Q)) return 0; return (Q-rear - Q-front MAXSIZE) % MAXSIZE; } // 7. 层序遍历求二叉树深度 int maxDepth(TreeNode* root) { if (root NULL) return 0; // 空树深度为0 int depth 0; Queue *q initQueue(); equeue(q, root); // 根结点入队 while(!isEmpty(q)) { int count queueSize(q); // 当前层的结点数 while(count 0) { TreeNode* curr; dequeue(q, curr); // 出队当前结点 // 左孩子入队 if (curr-lchild ! NULL) equeue(q, curr-lchild); // 右孩子入队 if (curr-rchild ! NULL) equeue(q, curr-rchild); count--; } depth; // 一层遍历完成深度1 } return depth; } int main(int argc, char const *argv[]) { BiTree T; createTree(T); // 创建二叉树 printf(二叉树深度为%d\n, maxDepth(T)); // 输出深度 return 0; }代码说明采用先序遍历 # 占位的方式创建二叉树符合数据结构教材的标准实现。队列采用循环队列实现避免假溢出时间复杂度 O (n)空间复杂度 O (n)最坏情况为完全二叉树队列存储 n/2 个结点。运行结果示例二叉树深度为5。3.2 二叉树带权路径长度 WPL2014 真题代码实现带权路径长度WPL是哈夫曼树的核心概念定义为所有叶结点的权值 × 该结点到根的路径长度 之和。#include stdio.h #include stdlib.h #define MAXSIZE 100 typedef int ElemType; // 二叉树结点定义带权值 typedef struct TreeNode { ElemType weight; struct TreeNode *left; struct TreeNode *right; }TreeNode; typedef TreeNode* BiTree; // 全局变量先序遍历创建二叉树的权值数组-1表示空结点 int idx 0; int weight[] {100, 42, 15, -1, -1, 27, -1, -1, 58, 28, 13, 5, -1, -1, 8, -1, -1, 15, -1, -1, 30, -1, -1}; // 1. 先序遍历创建带权二叉树 void createTree(BiTree *T) { ElemType ch weight[idx]; if (ch -1) // 空结点 { *T NULL; } else { *T (BiTree)malloc(sizeof(TreeNode)); (*T)-weight ch; createTree((*T)-left); createTree((*T)-right); } } // 2. 层序遍历计算WPL int wpl(BiTree T) { if (T NULL) return 0; // 数组模拟队列简化实现 BiTree queue[MAXSIZE]; int front 0; int rear 0; int wpl 0; int depth 0; // 当前层的深度根结点深度为0 queue[rear] T; // 根结点入队 while(rear ! front) { int count rear - front; // 当前层结点数 while(count 0) { BiTree curr queue[front]; // 出队 // 叶结点累加权值×深度 if (curr-left NULL curr-right NULL) { wpl depth * curr-weight; } // 非叶结点孩子入队 if (curr-left ! NULL) queue[rear] curr-left; if (curr-right ! NULL) queue[rear] curr-right; count--; } depth 1; // 深度1 } return wpl; } int main(int argc, char const *argv[]) { BiTree T; createTree(T); int w wpl(T); printf(二叉树带权路径长度WPL为%d\n, w); return 0; }代码说明采用层序遍历实现时间复杂度 O (n)空间复杂度 O (n)符合考研算法题的评分标准。示例二叉树的 WPL 计算叶结点 D (15, 深度 3)、A (27, 深度 3)、F (5, 深度 5)、B (8, 深度 5)、C (15, 深度 4)、E (30, 深度 3)WPL 15×3 27×3 5×5 8×5 15×4 30×3 325代码运行结果325验证正确性。四、核心考点总结与避坑指南4.1 必背核心公式树的基本性质n 个结点的树有 n-1 条边森林的树数 总结点数 - 总边数。正则 k 叉树叶结点数n0 m*(k-1)1满 k 叉树结点数(k^h -1)/(k-1)。树转二叉树无右孩子结点数 总结点数 - 非叶结点数 1。遍历对应关系树先根 二叉树前序树后根 二叉树中序。4.2 常见易错点❌ 混淆树、森林、二叉树的遍历对应关系错误认为树的后根 二叉树的后序。❌ 正则 k 叉树的结点数计算错误忽略 “边数 总结点数 - 1” 的核心公式。❌ 层序遍历求深度时忘记按层计数直接累加结点数导致深度错误。❌ 森林转二叉树时错误认为二叉树的右孩子对应原树的孩子实际对应兄弟。