complete m-ary tree术语定义差异及对应树结构标准称谓咨询

这类「除最后一层外所有层级完全填充、最后一层未填满时节点全部靠左排列、空间效率最高的m叉树」，目前不存在全球完全统一的标准术语，不同领域、不同教材的术语定义存在明确分歧，是数据结构入门阶段非常容易混淆的概念。

两类主流定义体系的冲突 #

目前主流的术语定义分为两套，核心差异就是对complete m-ary tree的所指完全不同：

• 以维基百科、国内绝大多数通用数据结构教材（如严蔚敏版《数据结构》）为代表的工程实践向资料体系：
  把你描述的这种靠左填充、适合用数组顺序存储的m叉树称为完全m叉树（complete m-ary tree）；把「所有叶子节点深度相同、所有内部节点都恰好有m个子节点」的全满结构称为完美m叉树（perfect m-ary tree），我们平时实现二叉堆、优先级队列时用到的完全二叉树，就属于这套定义下的概念。
• 你提到的两本经典教材采用的是数学/理论计算机方向的传统定义：
  两本书中定义的complete m-ary tree，恰好对应上一套体系里的完美m叉树，原文定义如下：

  《算法导论（第四版）》：完全k叉树是所有叶子深度相同、所有内部节点度数均为k的k叉树。
  《离散数学及其应用（第8版）》：完全m叉树是所有叶子都在同一层级的满m叉树。
  在这套定义体系下，你说的那种最后一层靠左填充的m叉树，通常被称为近似完全m叉树（almost complete m-ary tree）或者左完全m叉树（left-complete m-ary tree）。

入门学习避坑提示 #

• 不要脱离上下文死记术语的对应含义，碰到相关概念先确认当前资料采用的定义体系，尤其是参加考试、对照不同教材学习、阅读开源代码实现时，先对齐定义再做后续推导，避免因为术语歧义出错。
• 国内本科数据结构课程、计算机专业考研的考察范围内，几乎全部采用第一套工程向定义：即完全m叉树就是你描述的这种空间效率最高、最后一层节点靠左排列的结构，所有层全满、叶子同深度的结构被称为满m叉树。
• 如果阅读的是离散数学、算法导论类的理论资料，碰到complete m-ary tree表述时，要优先对应到「所有叶子同深度的全满m叉树」的定义，不要和堆结构用到的左填充完全树混淆。

内容的提问来源于stack exchange，提问作者Xiaobang Shi