考研数据结构：树与二叉树核心考点解析

1. 考研数据结构中的树与二叉树核心要点解析作为计算机考研408的必考内容树与二叉树在历年真题中平均占比达到15%-20%。我当年备考时花了整整两周时间才理清各类树结构的区别与联系这里把最精华的复习笔记整理分享给大家。2. 树的基本概念与性质2.1 树的定义与术语树是n(n≥0)个结点的有限集合。当n0时称为空树非空树满足有且仅有一个根结点其余结点可分为m(m≥0)个互不相交的有限集合每个集合本身又是一棵树关键术语图解A / | \ B C D / \ \ E F G结点A、B、C等字母代表的元素边连接结点的线度结点拥有的子树数如A的度为3叶子度为0的结点E、F、G2.2 树的存储结构考研常考两种表示方法双亲表示法适合找父节点#define MAX_SIZE 100 typedef struct { int data; int parent; // 父节点下标 } PTNode; PTNode tree[MAX_SIZE];孩子兄弟表示法节省空间typedef struct CSNode { int data; struct CSNode *firstchild, *nextsibling; } CSNode, *CSTree;3. 二叉树专题突破3.1 二叉树的性质第i层最多有2^(i-1)个结点深度为k的二叉树最多有2^k-1个结点对于任何二叉树叶子结点数n0 度为2的结点数n2 1证明第三条性质设总结点数nn0n1n2边数en-1。又因为en12n2联立可得n0n213.2 特殊二叉树满二叉树深度为k且有2^k-1个结点完全二叉树编号与满二叉树对应判断技巧出现空结点后不能有非空结点存储优势适合用数组存储i的左孩子是2i3.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-1102310012^9-1511前9层结点数511第10层结点数1001-511490第9层非叶子结点ceil(490/2)245总叶子数490(256-245)5014.2 线索二叉树typedef struct ThreadNode { int data; struct ThreadNode *lchild, *rchild; int ltag, rtag; // 0表示孩子1表示线索 } ThreadNode;中序线索化过程设置pre指针初始为NULL中序遍历时若p-lchild为空则ltag1lchildpre若pre!NULL且pre-rchild为空则pre-rtag1pre-rchildp5. 树与二叉树的转换5.1 森林转二叉树实操步骤将每棵树转为二叉树左孩子右兄弟把第二棵二叉树作为第一棵的右子树递归处理剩余树5.2 二叉树还原为树逆向操作从根节点开始右链上的结点都是兄弟每个结点的左子树是其孩子6. 备考建议与常见误区必背公式完全二叉树高度⌈log2(n1)⌉结点数计算n0n21易错点混淆树的度和图的度忽略空树的情况遍历时忘记递归终止条件推荐练习题已知先序ABDECFG中序DBEACGF画二叉树证明n个结点的二叉树有n1个空指针最后分享我的复习时间分配基础概念2天遍历算法3天重点写代码应用题5天每天10道真题综合模拟2天记得准备白纸多画图树结构可视化理解比死记硬背效率高得多。我在考前画了近百棵树形结构考试时遇到相关题目就能快速反应。