尧图网站建设 
考点频率★★★★★数据结构必考选择题常考树的基本术语与二叉树性质难度⭐⭐建议重点掌握树的基本术语根/叶子/度/深度理解二叉树的递归定义区分满二叉树与完全二叉树1️⃣ 什么是树树Tree是一种非线性数据结构它由nnnn≥0n \ge 0n≥0个节点组成节点之间有层次关系。递归定义树是nnn个节点的有限集合。当n0n0n0时称为空树当n0n0n0时有且仅有一个根节点Root其余节点可分为mmmm≥0m \ge 0m≥0个互不相交的有限集合每个集合本身又是一棵树称为子树。打个比方树就像公司的组织架构图。总经理根节点下面有多个部门经理子树每个部门经理下面又有多个员工子树的子树。总经理是所有人的“祖先”最底层的员工是“叶子”。树的特点每个节点有零个或多个子节点除根节点外每个节点有且仅有一个父节点节点之间没有环路不是图2️⃣ 树的基本术语软考必考术语含义示例说明根节点Root树中唯一没有父节点的节点总经理父节点Parent某节点的直接上层节点部门经理是员工的父节点子节点Child某节点的直接下层节点员工是部门经理的子节点兄弟节点Sibling具有相同父节点的节点同一部门下的员工叶子节点Leaf没有子节点的节点度为0最底层的员工度Degree节点拥有的子节点个数一个经理管3个人 → 度为3树的度树中所有节点的度的最大值全公司最多管5个人 → 树的度为5深度Depth从根节点到某节点的唯一路径长度根节点深度为0根节点高度为0第3层员工的深度为3从0开始或深度为2从0开始不同教材定义可能不同考试时以题目定义为准高度Height从某节点到其最远叶子节点的路径长度同上层次Level根节点为第1层往下递增根节点在第1层森林Forestmmmm≥0m \ge 0m≥0棵互不相交的树的集合多个组织架构图放一起3️⃣ 二叉树Binary Tree3.1 什么是二叉树二叉树是一种特殊的树结构其特点是每个节点最多只有两个子节点分别称为左子节点和右子节点。正式定义二叉树是nnnn≥0n \ge 0n≥0个节点的有限集合。当n0n0n0时为空二叉树当n0n0n0时由一个根节点和两棵互不相交的子树组成这两棵子树分别称为左子树和右子树且左子树和右子树本身也是二叉树。3.2 二叉树与树的区别对比项树一般二叉树子节点个数任意0≤degree≤m0 \le degree \le m0≤degree≤m最多2个左、右子节点顺序无序有序区分左右度数限制无每个节点度≤2\le 2≤2空树允许允许是否为有序树一般树无序二叉树有序关键点二叉树是有序树——左子树和右子树不能互换。即使只有一个子节点也必须明确它是左子节点还是右子节点。3.3 二叉树的五种基本形态形态描述图示空二叉树没有节点无只有根节点根节点没有子节点(A)只有左子树根节点只有左子节点(A( B ))只有右子树根节点只有右子节点(A( C ))左右子树均有根节点同时有左右子节点(A( B )( C ))4️⃣ 满二叉树与完全二叉树重点4.1 满二叉树Full Binary Tree定义一棵高度为hhh的二叉树如果所有叶子节点都在第hhh层且每个非叶子节点都有两个子节点则称为满二叉树。特点每一层的节点数都达到最大值第iii层有2i−12^{i-1}2i−1个节点根节点为第1层总节点数 2h−12^h - 12h−14.2 完全二叉树Complete Binary Tree定义一棵高度为hhh的二叉树如果第111层到第h−1h-1h−1层都是满的且第hhh层的节点从左到右连续排列中间没有空缺则称为完全二叉树。特点满二叉树一定是完全二叉树完全二叉树不一定是满二叉树叶子节点只能出现在最后两层可以通过数组顺序存储无需指针4.3 满二叉树 vs 完全二叉树易混淆对比项满二叉树完全二叉树所有叶子节点都在最底层只能在最后两层非叶子节点都有两个子节点每个节点度≤2\le 2≤2节点数2h−12^h - 12h−1不一定顺序存储可以可以经典考点5️⃣ 经典例题例题1一棵高度为hhh的满二叉树其节点总数为 。A.2h2^h2hB.2h−12^h - 12h−1C.2h12^h 12h1D.2h1−12^{h1} - 12h1−1解析高度为hhh的满二叉树共有2h−12^h - 12h−1个节点。选B。例题2下列关于完全二叉树的叙述中正确的是 。A. 完全二叉树中所有叶子节点都在同一层B. 完全二叉树可以用数组顺序存储C. 完全二叉树就是满二叉树D. 完全二叉树中每个节点的度都为2解析A错误——完全二叉树的叶子节点可以在最后两层B正确——完全二叉树是顺序存储的经典应用C错误——完全二叉树不一定是满二叉树D错误——叶子节点度为0。选B。6️⃣ 记忆口诀树是非线性结构根节点唯一无父。叶子度为0树的度看最大。二叉树最多两个子左右有序不混淆。满二叉树全满完全二叉树连续填。7️⃣ 小测验评论区对答案一棵高度为hhh的完全二叉树其节点数最多为 。A.2h2^h2hB.2h−12^h - 12h−1C.2h1−12^{h1} - 12h1−1D.2h12^{h} 12h1本专栏日更点击头像 → 专栏《软考中级高频考点》订阅第一时间接收新内容#软考中级 #软件设计师 #树 #二叉树 #满二叉树 #完全二叉树 #数据结构 #软考备考 【数据结构】树的基本概念与二叉树定义
考点频率★★★★★数据结构必考选择题常考树的基本术语与二叉树性质难度⭐⭐建议重点掌握树的基本术语根/叶子/度/深度理解二叉树的递归定义区分满二叉树与完全二叉树1️⃣ 什么是树树Tree是一种非线性数据结构它由nnnn≥0n \ge 0n≥0个节点组成节点之间有层次关系。递归定义树是nnn个节点的有限集合。当n0n0n0时称为空树当n0n0n0时有且仅有一个根节点Root其余节点可分为mmmm≥0m \ge 0m≥0个互不相交的有限集合每个集合本身又是一棵树称为子树。打个比方树就像公司的组织架构图。总经理根节点下面有多个部门经理子树每个部门经理下面又有多个员工子树的子树。总经理是所有人的“祖先”最底层的员工是“叶子”。树的特点每个节点有零个或多个子节点除根节点外每个节点有且仅有一个父节点节点之间没有环路不是图2️⃣ 树的基本术语软考必考术语含义示例说明根节点Root树中唯一没有父节点的节点总经理父节点Parent某节点的直接上层节点部门经理是员工的父节点子节点Child某节点的直接下层节点员工是部门经理的子节点兄弟节点Sibling具有相同父节点的节点同一部门下的员工叶子节点Leaf没有子节点的节点度为0最底层的员工度Degree节点拥有的子节点个数一个经理管3个人 → 度为3树的度树中所有节点的度的最大值全公司最多管5个人 → 树的度为5深度Depth从根节点到某节点的唯一路径长度根节点深度为0根节点高度为0第3层员工的深度为3从0开始或深度为2从0开始不同教材定义可能不同考试时以题目定义为准高度Height从某节点到其最远叶子节点的路径长度同上层次Level根节点为第1层往下递增根节点在第1层森林Forestmmmm≥0m \ge 0m≥0棵互不相交的树的集合多个组织架构图放一起3️⃣ 二叉树Binary Tree3.1 什么是二叉树二叉树是一种特殊的树结构其特点是每个节点最多只有两个子节点分别称为左子节点和右子节点。正式定义二叉树是nnnn≥0n \ge 0n≥0个节点的有限集合。当n0n0n0时为空二叉树当n0n0n0时由一个根节点和两棵互不相交的子树组成这两棵子树分别称为左子树和右子树且左子树和右子树本身也是二叉树。3.2 二叉树与树的区别对比项树一般二叉树子节点个数任意0≤degree≤m0 \le degree \le m0≤degree≤m最多2个左、右子节点顺序无序有序区分左右度数限制无每个节点度≤2\le 2≤2空树允许允许是否为有序树一般树无序二叉树有序关键点二叉树是有序树——左子树和右子树不能互换。即使只有一个子节点也必须明确它是左子节点还是右子节点。3.3 二叉树的五种基本形态形态描述图示空二叉树没有节点无只有根节点根节点没有子节点(A)只有左子树根节点只有左子节点(A( B ))只有右子树根节点只有右子节点(A( C ))左右子树均有根节点同时有左右子节点(A( B )( C ))4️⃣ 满二叉树与完全二叉树重点4.1 满二叉树Full Binary Tree定义一棵高度为hhh的二叉树如果所有叶子节点都在第hhh层且每个非叶子节点都有两个子节点则称为满二叉树。特点每一层的节点数都达到最大值第iii层有2i−12^{i-1}2i−1个节点根节点为第1层总节点数 2h−12^h - 12h−14.2 完全二叉树Complete Binary Tree定义一棵高度为hhh的二叉树如果第111层到第h−1h-1h−1层都是满的且第hhh层的节点从左到右连续排列中间没有空缺则称为完全二叉树。特点满二叉树一定是完全二叉树完全二叉树不一定是满二叉树叶子节点只能出现在最后两层可以通过数组顺序存储无需指针4.3 满二叉树 vs 完全二叉树易混淆对比项满二叉树完全二叉树所有叶子节点都在最底层只能在最后两层非叶子节点都有两个子节点每个节点度≤2\le 2≤2节点数2h−12^h - 12h−1不一定顺序存储可以可以经典考点5️⃣ 经典例题例题1一棵高度为hhh的满二叉树其节点总数为 。A.2h2^h2hB.2h−12^h - 12h−1C.2h12^h 12h1D.2h1−12^{h1} - 12h1−1解析高度为hhh的满二叉树共有2h−12^h - 12h−1个节点。选B。例题2下列关于完全二叉树的叙述中正确的是 。A. 完全二叉树中所有叶子节点都在同一层B. 完全二叉树可以用数组顺序存储C. 完全二叉树就是满二叉树D. 完全二叉树中每个节点的度都为2解析A错误——完全二叉树的叶子节点可以在最后两层B正确——完全二叉树是顺序存储的经典应用C错误——完全二叉树不一定是满二叉树D错误——叶子节点度为0。选B。6️⃣ 记忆口诀树是非线性结构根节点唯一无父。叶子度为0树的度看最大。二叉树最多两个子左右有序不混淆。满二叉树全满完全二叉树连续填。7️⃣ 小测验评论区对答案一棵高度为hhh的完全二叉树其节点数最多为 。A.2h2^h2hB.2h−12^h - 12h−1C.2h1−12^{h1} - 12h1−1D.2h12^{h} 12h1本专栏日更点击头像 → 专栏《软考中级高频考点》订阅第一时间接收新内容#软考中级 #软件设计师 #树 #二叉树 #满二叉树 #完全二叉树 #数据结构 #软考备考