Complete Binary Tree

定义 Definition

（数据结构）完全二叉树：除最后一层外，每一层的结点都被填满；最后一层的结点按从左到右尽可能靠左排列。常用于实现二叉堆（heap），便于用数组顺序存储。

发音 Pronunciation (IPA)

/kəmˈpliːt ˈbaɪnəri triː/

词源 Etymology

complete 意为“完整的、齐全的”，来自拉丁语 completus（填满、完成）；binary 意为“二进制的/由二组成的”，来自拉丁语 bini（两个一组）；tree 在计算机科学中借用“树”的形象来表示分层分支结构。合起来指“一种结构上尽可能被填满的二叉树”。

例句 Examples

A heap is usually stored as a complete binary tree.
堆通常以完全二叉树的形式存储。

Because the complete binary tree keeps nodes packed to the left, we can map parent and child positions efficiently in an array.
由于完全二叉树把结点尽量向左紧凑排列，我们可以在数组中高效地映射父子结点的位置。

相关词 Related Words

• Binary Tree
• Full Binary Tree
• Perfect Binary Tree
• Heap
• Node
• Traversal
• Level-Order Traversal
• Balanced Tree

文献与作品 Literary / Notable Works

• Introduction to Algorithms（Cormen, Leiserson, Rivest, Stein）：在堆与堆排序部分讲解以完全二叉树表示的二叉堆。
• The Art of Computer Programming, Vol. 1: Fundamental Algorithms（Donald E. Knuth）：在树与数据结构相关章节讨论二叉树及其结构性质。
• Algorithms（Robert Sedgewick & Kevin Wayne）：在优先队列/堆实现中使用完全二叉树的数组表示法。