企业官网建设流程全解析

1. 考研数据结构中的树与二叉树核心要点解析

作为计算机考研408的必考内容，树与二叉树在历年真题中平均占比达到15%-20%。我当年备考时花了整整两周时间才理清各类树结构的区别与联系，这里把最精华的复习笔记整理分享给大家。

2. 树的基本概念与性质

2.1 树的定义与术语

树是n(n≥0)个结点的有限集合。当n=0时称为空树，非空树满足：

• 有且仅有一个根结点
• 其余结点可分为m(m≥0)个互不相交的有限集合，每个集合本身又是一棵树

关键术语图解：

A / | \ B C D / \ \ E F G

• 结点：A、B、C等字母代表的元素
• 边：连接结点的线
• 度：结点拥有的子树数（如A的度为3）
• 叶子：度为0的结点（E、F、G）

2.2 树的存储结构

考研常考两种表示方法：

1. 双亲表示法（适合找父节点）

#define MAX_SIZE 100 typedef struct { int data; int parent; // 父节点下标 } PTNode; PTNode tree[MAX_SIZE];

2. 孩子兄弟表示法（节省空间）

typedef struct CSNode { int data; struct CSNode *firstchild, *nextsibling; } CSNode, *CSTree;

3. 二叉树专题突破

3.1 二叉树的性质

1. 第i层最多有2^(i-1)个结点
2. 深度为k的二叉树最多有2^k-1个结点
3. 对于任何二叉树，叶子结点数n0 = 度为2的结点数n2 + 1

证明第三条性质：设总结点数n=n0+n1+n2，边数e=n-1。又因为e=n1+2n2，联立可得n0=n2+1

3.2 特殊二叉树

1. 满二叉树：深度为k且有2^k-1个结点
2. 完全二叉树：编号与满二叉树对应
   • 判断技巧：出现空结点后不能有非空结点
   • 存储优势：适合用数组存储（i的左孩子是2i）

3.3 二叉树遍历

真题常考遍历序列还原问题：

graph TD A((A)) --> B((B)) A --> C((C)) B --> D((D)) B --> E((E))

• 先序：A B D E C
• 中序：D B E A C
• 后序：D E B C A

已知中序+其他任一种遍历可唯一确定二叉树

4. 高频考点题型解析

4.1 完全二叉树相关计算

例题：一棵完全二叉树有1001个结点，求叶子结点数。

解：

• 设高度为h，则2^10-1=1023>1001>2^9-1=511
• 前9层结点数=511
• 第10层结点数=1001-511=490
• 第9层非叶子结点=ceil(490/2)=245
• 总叶子数=490+(256-245)=501

4.2 线索二叉树

typedef struct ThreadNode { int data; struct ThreadNode *lchild, *rchild; int ltag, rtag; // 0表示孩子，1表示线索 } ThreadNode;

中序线索化过程：

1. 设置pre指针初始为NULL
2. 中序遍历时：
   • 若p->lchild为空，则ltag=1，lchild=pre
   • 若pre!=NULL且pre->rchild为空，则pre->rtag=1，pre->rchild=p

5. 树与二叉树的转换

5.1 森林转二叉树

实操步骤：

1. 将每棵树转为二叉树（左孩子右兄弟）
2. 把第二棵二叉树作为第一棵的右子树
3. 递归处理剩余树

5.2 二叉树还原为树

逆向操作：

1. 从根节点开始，右链上的结点都是兄弟
2. 每个结点的左子树是其孩子

6. 备考建议与常见误区

1. 必背公式：

   • 完全二叉树高度：⌈log2(n+1)⌉
   • 结点数计算：n0=n2+1

2. 易错点：

   • 混淆树的度和图的度
   • 忽略空树的情况
   • 遍历时忘记递归终止条件

3. 推荐练习题：

   • 已知先序ABDECFG，中序DBEACGF，画二叉树
   • 证明n个结点的二叉树有n+1个空指针

最后分享我的复习时间分配：

• 基础概念：2天
• 遍历算法：3天（重点写代码）
• 应用题：5天（每天10道真题）
• 综合模拟：2天

记得准备白纸多画图，树结构可视化理解比死记硬背效率高得多。我在考前画了近百棵树形结构，考试时遇到相关题目就能快速反应。