Full Binary Tree

定义 Definition

full binary tree（满二叉树）：一种二叉树结构，其中每个节点要么没有子节点（叶子节点），要么恰好有两个子节点；不存在“只有一个子节点”的节点。
（注意：它不同于 complete binary tree「完全二叉树」和 perfect binary tree「完美二叉树」。）

发音 Pronunciation

/fʊl ˈbaɪnəri triː/

例句 Examples

A full binary tree has no nodes with only one child.
满二叉树中不存在只有一个子节点的节点。

In a full binary tree, the number of leaves is one more than the number of internal nodes.
在满二叉树中，叶子节点的数量比内部节点的数量多 1。

词源 Etymology

full 在这里表示“结构上完整、没有缺一边的情况”；binary 源自拉丁语 bini（“两个一组”），表示“二”；tree 在数学与计算机科学中借用“树”的形象来表示层级分支结构。合起来强调：每次分叉都“成对出现”。

相关词 Related Words

• Binary Tree
• Complete Binary Tree
• Perfect Binary Tree
• Leaf
• Internal Node
• Subtree
• Traversal

文学与著作中的用例 Literary Works

• Donald E. Knuth, The Art of Computer Programming（在树形结构与递归讨论中涉及二叉树及其变体术语）
• Thomas H. Cormen et al., Introduction to Algorithms（算法与数据结构章节中讨论二叉树性质，相关术语常出现）
• Robert Sedgewick & Kevin Wayne, Algorithms（讲解树结构与实现时常对二叉树类型作区分，包括“full”这一类约束）