- hello，大家好，我是 Lorin ，首先祝大家双节快乐，这篇文章也是放假前的最后一篇文章，祝大家食用愉快，有所收获。
引言
- 在计算机科学和数据结构领域，二叉树是一种基本的数据结构，常用于实现各种算法和数据处理。在二叉树的概念中，有两个重要的子类：完全二叉树和满二叉树。本文将详细介绍这两种类型的二叉树，探讨它们的特点、区别以及应用场景。
完全二叉树
- 完全二叉树是一种特殊的二叉树，具有以下特点：
定义
代码语言：txt复制1、除了最后一层外，每一层的节点都被填满。
2、如果最后一层存在节点，那么这些节点从左到右依次填充，不留空缺。
3、完全二叉树的高度通常较小，具有良好的平衡性。数组和完全二叉树转换
- 由于完全二叉树的特殊性，我们可以用数组存储完全二叉树，下面我们看看它们之间如何转换：
- 示例：
数组：[1, 2, 3, 4, 5, 6, 7]
对应完全二叉树：
1
/
2 3
/ /
4 5 6 7数组转完全二叉树
- 给定一个数组 1, 2, 3, 4, 5, 6, 7，要将它转换为完全二叉树，可以按照以下步骤进行：
数组中的第一个元素是树的根节点，即 1。
对于数组中的第 i 个元素，它的左子节点位于数组的第 2*i 个位置，右子节点位于数组的第 2*i 1 个位置。根据这个规则，构建树的其他节点。
左子节点：2*1 = 2，所以根节点 1 的左子节点是 2。
右子节点：2*1 1 = 3，所以根节点 1 的右子节点是 3。
根节点 2 的左子节点是 4，右子节点是 5。
根节点 3 的左子节点是 6，右子节点是 7。
重复上述步骤，直到数组中的所有元素都构建成二叉树。完全二叉树转数组
- 给定一个完全二叉树，要将它转换为数组，可以按照以下步骤进行：
遍历二叉树，按照层次顺序从上到下、从左到右依次访问节点。
将每个访问的节点的值按照顺序存储到数组中。Java 版实现
代码语言：java复制class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
}
}
public class Convertor {
// 将数组转换为完全二叉树
public static TreeNode arrayToCompleteBinaryTree(int[] arr) {
return arrayToCompleteBinaryTree(arr, 0);
}
private static TreeNode arrayToCompleteBinaryTree(int[] arr, int index) {
if (index >= arr.length) {
return null;
}
TreeNode root = new TreeNode(arr[index]);
root.left = arrayToCompleteBinaryTree(arr, 2 * index 1);
root.right = arrayToCompleteBinaryTree(arr, 2 * index 2);
return root;
}
// 将完全二叉树转换为数组
public static int[] completeBinaryTreeToArray(TreeNode root) {
int height = getHeight(root);
// 完全二叉树的节点数最大为满二叉树节点数 数组值为默认值0表示无该节点
int[] arr = new int[(int) Math.pow(2, height) - 1];
completeBinaryTreeToArray(root, arr, 0);
return arr;
}
private static void completeBinaryTreeToArray(TreeNode root, int[] arr, int index) {
if (root == null) {
return;
}
arr[index] = root.val;
completeBinaryTreeToArray(root.left, arr, 2 * index 1);
completeBinaryTreeToArray(root.right, arr, 2 * index 2);
}
private static int getHeight(TreeNode root) {
if (root == null) {
return 0;
}
return 1 Math.max(getHeight(root.left), getHeight(root.right));
}
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5, 6};
TreeNode root = arrayToCompleteBinaryTree(arr);
int[] result = completeBinaryTreeToArray(root);
for (int num : result) {
System.out.print(num " ");
}
}
}满二叉树
定义
- 满二叉树是一种更加特殊的完全二叉树，具有以下特点：
1、所有层的节点都被填满。
2、满二叉树的高度是固定的，由节点数量决定。
高度为 H 满二叉树节点个数 N：
N = 2^0 2^1 2^2 ... 2^H = 2^H - 1 数组和满二叉树转换
- 满二叉树是一棵特殊的完全二叉树，因此实现方式和完全二叉树相同。
总结
树高度
- 完全二叉树的高度通常较小，但不确定，取决于节点数量。
- 满二叉树的高度由节点数量决定，是确定的。
应用场景
- 完全二叉树在堆数据结构中广泛应用，如二叉最小堆和二叉最大堆。
- 满二叉树在一些特定的数据存储和检索算法中有用，但相对较少见。
个人简介
