一文带你详解完全二叉树（超详细）

大家好，欢迎来到IT知识分享网。

完全二叉树

我们知道树是一种非线性数据结构。它对儿童数量没有限制。二叉树有一个限制，因为树的任何节点最多有两个子节点：左子节点和右子节点。

什么是完全二叉树？

完全二叉树是一种特殊类型的二叉树，其中树的所有级别都被完全填充，除了最低级别的节点从尽可能左侧填充之外。

完全二叉树的一些术语：

• 根： 没有边来自父节点的节点。示例-节点A
• 子节点： 具有某些传入边的节点称为子节点。示例 – 节点 B、F 分别是 A 和 C 的子节点。
• 兄弟节点：具有相同父节点的节点是兄弟节点。示例 – D、E 是兄弟姐妹，因为他们有相同的父母 B。
• 节点的度数： 特定父节点的子节点数量。示例 – A 的次数为 2，C 的次数为 1。D 的次数为 0。
• 内部/外部节点： 叶节点是外部节点，非叶节点是内部节点。
• 级别： 计算到达目标节点的路径中的节点数。示例 – 由于节点 A 和 E 形成路径，因此节点 D 的级别为 2。
• 高度： 到达目标节点的边数，根的高度为 0。示例 – 节点 E 的高度为 2，因为它有两条距根的边。

我们知道树是一种非线性数据结构。它对叶子节点数量没有限制。二叉树有一个限制，因为树的任何节点最多有两个子节点：左子节点和右子节点.

什么是完全二叉树？

完全二叉树是一种特殊类型的二叉树，其中树的所有级别都被完全填充，除了最低级别的节点尽可能左侧填充之外。

完全二叉树的一些术语：

• 根：没有边来自父节点的节点。示例-节点A
• 子节点： 具有某些传入边的节点称为子节点。示例 – 节点 B、F 分别是 A 和 C 的子节点。
• 兄弟节点：具有相同父节点的节点是兄弟节点。示例 – D、E 是兄弟姐妹，因为他们有相同的父母 B。
• 节点的度数： 特定父节点的子节点数量。示例 – A 的次数为 2，C 的次数为 1。D 的次数为 0。
• 内部/外部节点： 叶节点是外部节点，非叶节点是内部节点。
• 级别： 计算到达目标节点的路径中的节点数。示例 – 由于节点 A 和 E 形成路径，因此节点 D 的级别为 2。
• 高度：到达目标节点的边数，根的高度为 0。示例 – 节点 E 的高度为 2，因为它有两条距根的边。

完全二叉树的性质：

• 完全二叉树被称为真二叉树，其中所有叶子都具有相同的深度。
• 在完全二叉树中，深度d处的节点数为 2 d。
• 在具有n 个节点的完全二叉树中，树的高度为log(n+1) 。
• 除最后一个级别外所有级别均已满。

完美二叉树与完全二叉树：

具有最大节点数、高度为“h”的二叉树是完美二叉树。 对于给定高度h，节点的最大数量为 2h+1-1。

高度为 h 的完全二叉树是高度为h-1的完美二叉树，并且在最后一层中元素按从左到右的顺序存储。

示例1：

给定二叉树的高度为 2，该树中的最大节点数为 n = 2 h+1 -1 = 22+1 -1 = 23 -1 = 7。 因此我们可以断定它是一个完美的二叉树。 现在对于一个完整的二叉树，它的高度达到h-1，即；1、最后一层元素按照从左到右的顺序存储。因此它也是一棵完全二叉树。这是存储在数组中时元素的表示形式

元素逐级存储在数组中。在数组中，所有元素都是连续存储的。

示例2：

给定二叉树的高度为 2，节点的最大数量为 2h+1 – 1 = 22+1 – 1 = 2 3 – 1 = 7。 但树中的节点数是6。因此它不是完美的二叉树。 现在对于一个完整的二叉树，它的高度达到 h-1，即；1 和最后一级元素按从左到右的顺序存储。因此这是一个完全二叉树。将元素存储在数组中，它会像；

示例3：

二叉树的高度为2，最多可以有7个节点，但只有5个节点，因此它不是完美的二叉树。 在完全二叉树的情况下，我们看到在最后一层元素不是从左到右顺序填充的。所以它不是一个完全二叉树。

数组中的元素不连续。

完整二叉树与完全二叉树：

对于满二叉树，每个节点有 2 个子节点或 0 个子节点。

示例1：

在给定的二叉树中，没有度数为 1 的节点，每个节点有 2 个或 0 个子节点，因此它是一个满二叉树。

对于完全二叉树，元素是逐层存储的，而不是从最后一层的最左边开始。因此这不是一个完整的二叉树。数组表示形式为：

示例2：

在给定的二叉树中，没有度为 1 的节点。每个节点的度为 2 或 0。因此，它是满二叉树。

对于完全二叉树，元素是逐层存储的，并从最后一层的最左边开始填充。因此这是一个完全二叉树。下面是树的数组表示：

示例3：

在给定的二叉树中，节点 B 的度数为 1，这违反了满二叉树的属性，因此它不是满二叉树

对于完全二叉树，元素是逐层存储的，并从最后一层的最左边开始填充。因此这是一个完全二叉树。二叉树的数组表示为：

示例4：

在给定的二叉树中，节点 C 的度数为 1，这违反了满二叉树的属性，因此它不是满二叉树

对于完全二叉树，元素是逐层存储的，并从最后一层的最左边开始填充。这里节点 E 违反了条件。因此这不是一个完整的二叉树。

完全二叉树的创建：

我们知道，完全二叉树是一棵树，其中除了最后一层（例如l）之外，所有其他层都有（2l）个节点，并且节点从左到右排列。 可以使用数组来表示。如果父级是索引i则左子级位于2i+1，右子级位于2i+2。

算法：

为了创建完全二叉树，我们需要一个队列数据结构来跟踪插入的节点。

步骤1： 当树为空时，用新节点初始化根。

步骤2： 如果树不为空，则获取前面的元素

• 如果前面的元素没有左子节点，则将左子节点设置为新节点
• 如果右子节点不存在，则将右子节点设置为新节点

步骤 3： 如果该节点有两个子节点，则将其从队列中弹出

步骤4： 将新数据入队。

考虑下面的数组：

0. 第一个元素将是根（索引处的值 = 0）

A 被视为根

2. 下一个元素（索引 = 1处）将是左元素，第三个元素（索引 = 2）将是根的右子元素

B 作为A左孩子，D 作为A右孩子

3. 第四个（索引 = 3）和第五个元素（索引 = 4）将是 B 节点的左右子节点

E和F是B的左孩子和右孩子

4. 下一个元素（索引= 5）将是节点D的左子节点

G 成为 D 节点的左子节点

这就是完整二叉树的创建方式。

完全二叉树的应用：

• 堆排序
• 基于堆排序的数据结构

顺序方式从给定数组构造完整二叉树

给定一个元素数组，我们的任务是以顺序方式从该数组构造一个完整的二叉树。也就是说，数组左侧的元素将从第 0 层开始逐层填充到树中。

示例：

输入：arr[] = {1, 2, 3, 4, 5, 6} 输出：以下树的根 1 / \ 2 3 / \ / 4 5 6 ​ ​ 输入：arr[] = {1, 2, 3, 4, 5, 6, 6, 6, 6, 6} 输出：以下树的根 1 / \ 2 3 / \ / \ 4 5 6 6 / / 6 66 

我们仔细观察，我们可以看到，如果父节点位于数组中的索引 i 处，则该节点的左子节点位于索引 (2_i + 1) 处，右子节点位于索引处 (2_i + 2)在数组中。 利用这个概念，我们可以通过选择父节点来轻松插入左节点和右节点。我们将插入数组中存在的第一个元素作为树中第 0 层的根节点，并开始遍历数组，对于每个节点，我们将在树的左侧和右侧插入子节点。

下面是执行此操作的递归程序：

JavaScript 代码

​ let root ​ class Node { constructor(data) { this.left = null this.right = null this.data = data } } ​ // 将 arr 数组中的元素构造为二叉树 function insertLevelOrder(arr, i) { let root = null if (i < arr.length) { root = new Node(arr[i]); // 设置节点的左节点 root.left = insertLevelOrder(arr, 2 * i + 1); // 设置节点的右节点 root.right = insertLevelOrder(arr, 2 * i + 2); } return root } ​ // 按树结构打印元素 function inOrder(root) { if (root != null) { console.log("元素的值:" + root.data); inOrder(root.left) inOrder(root.right) } } ​ let arr = [1, 2, 3, 4, 5, 6, 6, 6, 6]; // 将数组转换为树结构 root = insertLevelOrder(arr, 0); // 打印树结构的元素 inOrder(root); 

输出结果：[1 2 4 6 6 5 3 6 6]

Golang 代码

package main ​ import ( "fmt" "testing" ) ​ type Node struct { Left *Node Right *Node Data int } ​ // 给定数据构建二叉树 func insertLevelOrder(arr []int, index int) *Node { var node *Node if index < len(arr) { node = &Node{ Left: insertLevelOrder(arr, 2*index+1), Right: insertLevelOrder(arr, 2*index+2), Data: arr[index], } } return node } ​ func inOrder(node *Node) []int { var rest []int if node != nil { rest = append(rest, node.Data) rest = append(rest, inOrder(node.Left)...) rest = append(rest, inOrder(node.Right)...) } return rest } ​ func Test_main(t *testing.T) { var arr = []int{1, 2, 3, 4, 5, 6, 6, 6, 6} node := insertLevelOrder(arr, 0) result := inOrder(node) fmt.Println(result) } 

输出结果： [1 2 4 6 6 5 3 6 6]

题外话

感兴趣的小伙伴，赠送全套Python学习资料，包含面试题、简历资料等具体看下方。

👉CSDN大礼包🎁：全网最全《Python学习资料》免费赠送🆓！（安全链接，放心点击）

一、Python所有方向的学习路线

Python所有方向的技术点做的整理，形成各个领域的知识点汇总，它的用处就在于，你可以按照下面的知识点去找对应的学习资源，保证自己学得较为全面。

二、Python必备开发工具

工具都帮大家整理好了，安装就可直接上手！

三、最新Python学习笔记

当我学到一定基础，有自己的理解能力的时候，会去阅读一些前辈整理的书籍或者手写的笔记资料，这些笔记详细记载了他们对一些技术点的理解，这些理解是比较独到，可以学到不一样的思路。

四、Python视频合集

观看全面零基础学习视频，看视频学习是最快捷也是最有效果的方式，跟着视频中老师的思路，从基础到深入，还是很容易入门的。

五、实战案例

纸上得来终觉浅，要学会跟着视频一起敲，要动手实操，才能将自己的所学运用到实际当中去，这时候可以搞点实战案例来学习。

六、面试宝典

👉CSDN大礼包🎁：全网最全《Python学习资料》免费赠送🆓！（安全链接，放心点击）

若有侵权，请联系删除