什么是网站静态页面,360优化大师最新版下载,软文营销方法有哪些,互联网网站开发用哪个语言开发树是 “非线性结构” 的代表#xff08;区别于线性表的 “一对一”#xff0c;树是 “一对多”#xff09;#xff0c;而二叉树是树结构中最常用、考试最核心的类型#xff08;90% 的树相关题目围绕二叉树展开#xff09;。比如电脑中的文件系统#xff08;C 盘→文件夹…树是 “非线性结构” 的代表区别于线性表的 “一对一”树是 “一对多”而二叉树是树结构中最常用、考试最核心的类型90% 的树相关题目围绕二叉树展开。比如电脑中的文件系统C 盘→文件夹→文件、数据库中的 B 树索引都基于树结构设计。下文从 “树的基本概念” 入手重点拆解二叉树的性质、遍历和特殊类型确保每个考点都有 “例子 计算”。一、先搞懂树的基本概念基础铺垫树的结构像 “自然界的树”有根、枝、叶先记清核心术语考试常考术语辨析术语通俗解释例子以文件系统树为例根节点树的最顶层节点没有父节点C 盘整个文件系统的根父节点 / 子节点直接上层节点为父直接下层节点为子“文档” 文件夹是 “C 盘” 的子节点“C 盘” 是父节点叶子节点没有子节点的节点树的最底层“简历.docx” 文件没有下层内容节点的度该节点拥有的子节点数量“文档” 文件夹有 3 个文件→度为 3树的深度从根节点到最底层叶子节点的层数根为 1 层C 盘→文档→简历.docx→深度为 3关键提醒树的 “深度” 计算有两种说法根为 0 层或 1 层考试中若未说明默认 “根为 1 层”按官方教程标准。二、核心考点 1二叉树的定义与重要性质二叉树是 “每个节点最多有两个子节点” 的树左子节点和右子节点顺序不能乱比如 “左子树存小于父节点的值右子树存大于父节点的值”后续二叉搜索树会讲。考试重点考二叉树的 5 个重要性质常考计算需熟记并会应用。1. 二叉树的 5 个重要性质必背 计算性质 1第 i 层最多有 2^(i-1) 个节点i≥1解释第 1 层根最多 1 个2^01第 2 层最多 2 个2^12第 3 层最多 4 个2^24以此类推计算示例求第 5 层最多有多少个节点→ 2^(5-1)16 个。性质 2深度为 k 的二叉树最多有 2^k -1 个节点k≥1解释所有层的最大节点数相加124...2^(k-1) 2^k -1计算示例深度为 3 的二叉树最多有多少节点→ 2^3 -17 个124。性质 3任意二叉树叶子节点数 度为 2 的节点数 1记为 n0 n2 1解释度为 0 的是叶子节点n0度为 1 的是有 1 个孩子的节点n1度为 2 的是有 2 个孩子的节点n2总节点数 n n0 n1 n2同时通过 “边” 的数量推导可得 n0 n2 1计算示例某二叉树有 5 个度为 2 的节点3 个度为 1 的节点求叶子节点数→ n0516 个总节点数 63514 个。性质 4完全二叉树的叶子节点数重点完全二叉树是 “除最后一层外每一层节点数都满最后一层节点从左到右排满不能空左缺右”后续会细讲其叶子节点数满足若总节点数 n 为奇数n0 (n1)/2若总节点数 n 为偶数n0 n/2计算示例完全二叉树有 15 个节点奇数→ n0(151)/28 个有 14 个节点偶数→ n014/27 个。性质 5完全二叉树中节点 i从根开始按层编号左到右的左孩子是 2i右孩子是 2i1父节点是 i//2解释根节点编号 1第 2 层左 2 右 3第 3 层左 4 右 5、左 6 右 7以此类推计算示例编号为 5 的节点左孩子 2×510右孩子 2×5111父节点 5//22整除。2. 特殊二叉树考试高频类型定义关键特征便于判断满二叉树深度为 k且节点数 2^k -1每一层都满叶子节点全在最后一层没有度为 1 的节点完全二叉树除最后一层外全满最后一层从左到右排满度为 1 的节点最多 1 个要么 0 个要么 1 个二叉搜索树BST左子树所有节点值父节点值右子树所有节点值父节点值中序遍历结果是 “从小到大的有序序列”判断示例深度为 3节点数 7→满二叉树也是完全二叉树深度为 3节点数 6→完全二叉树最后一层左 4、5缺 6、7深度为 3节点数 5→不是完全二叉树最后一层左 4缺 5右 6 存在→空左缺右不符合。三、核心考点 2二叉树的遍历必考遍历是 “按一定顺序访问二叉树的所有节点”考试重点考 3 种遍历方式前序根→左→右、中序左→根→右、后序左→右→根核心是 “递归思想”也可用栈 / 队列实现非递归但考试重点考递归逻辑。1. 三种遍历的定义记顺序以如下二叉树为例根 A左子树 B右子树 CB 的左 D右 EC 的左 FA/ \B C/ \ /D E F1前序遍历根→左→右步骤先访问根节点再递归遍历左子树最后递归遍历右子树遍历结果A → B → D → E → C → F。2中序遍历左→根→右步骤先递归遍历左子树再访问根节点最后递归遍历右子树遍历结果D → B → E → A → F → C。3后序遍历左→右→根步骤先递归遍历左子树再递归遍历右子树最后访问根节点遍历结果D → E → B → F → C → A。2. 遍历结果推导真题高频考试常考 “已知两种遍历结果求第三种”核心是 “中序遍历 前序 / 后序可唯一确定二叉树”前序 后序不能唯一确定因无法判断左 / 右子树范围。推导示例已知前序 A→B→D→E→C→F中序 D→B→E→A→F→C求后序。Step1前序的第一个节点是根AStep2在中序中找 A 的位置左边是左子树D→B→E右边是右子树F→CStep3前序中 A 之后的节点是左子树的前序B→D→E再之后是右子树的前序C→FStep4对左子树根 B重复 Step1-Step3中序左 D右 E→前序 B→D→E中序 D→B→EStep5对右子树根 C重复 Step1-Step3中序左 F右空→前序 C→F中序 F→CStep6按后序规则遍历结果 D→E→B→F→C→A和之前一致。3. 遍历的应用场景遍历方式应用场景例子前序遍历复制二叉树、获取树的前缀表达式按前序顺序复制节点保持树结构中序遍历二叉搜索树排序从小到大中序遍历 BST得到有序序列后序遍历计算二叉树的节点数、高度先算子树后序遍历每个节点时累加子树节点数四、核心考点 3二叉树的高度计算常考树的高度深度是 “从根到最远叶子节点的层数”考试常考 “根据遍历结果或节点数计算高度”核心是 “递归计算左、右子树高度取最大值 1根节点”。1. 已知二叉树结构计算高度以上面的二叉树为例根 A 的左子树B高度B 的左 D高度 1、右 E高度 1→ 左子树高度 112根 A 的右子树C高度C 的左 F高度 1、右空→ 右子树高度 112根 A 的高度 max (2,2)13。2. 已知完全二叉树的节点数计算高度完全二叉树的高度 k 满足2^(k-1) ≤ n 2^kn 是总节点数高度 k⌈log₂(n1)⌉向上取整或 k⌊log₂n⌋1向下取整。计算示例n15满二叉树2^(3-1)4 ≤15 82^3不对2^(4-1)8 ≤15 162^4→k4n102^(3-1)4 ≤10 8不对2^38 ≤10 162^4→k4公式验证⌊log₂10⌋1314正确。五、备考小贴士3 步搞定记性质与公式重点背二叉树的 5 个性质尤其是 n0n21、完全二叉树的叶子节点数和高度计算每天花 5 分钟默写练遍历推导找 10 道 “已知前序 中序求后序” 的题目按 “找根→分左右子树→递归” 的步骤练习确保能快速推导辨特殊二叉树记住满二叉树、完全二叉树、BST 的关键特征如完全二叉树度为 1 的节点最多 1 个做题时先判断类型再用对应性质计算。下一篇【基础知识】专栏将讲解 “图结构基础”图的定义、存储、遍历图是更复杂的非线性结构“多对多”考试中常结合 “最短路径”“拓扑排序” 出题建议提前回顾树的遍历逻辑图的遍历是树遍历的延伸。
