1、除了最后一层外,每一层的节点都被填满。
2、如果最后一层存在节点,那么这些节点从左到右依次填充,不留空缺。
3、完全二叉树的高度通常较小,具有良好的平衡性。
数组:[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。
重复上述步骤,直到数组中的所有元素都构建成二叉树。
遍历二叉树,按照层次顺序从上到下、从左到右依次访问节点。
将每个访问的节点的值按照顺序存储到数组中。
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
👋 你好,我是 Lorin 洛林,一位 Java 后端技术开发者!座右铭:Technology has the power to make the world a better place.
🚀 我对技术的热情是我不断学习和分享的动力。我的博客是一个关于Java生态系统、后端开发和最新技术趋势的地方。
🧠 作为一个 Java 后端技术爱好者,我不仅热衷于探索语言的新特性和技术的深度,还热衷于分享我的见解和最佳实践。我相信知识的分享和社区合作可以帮助我们共同成长。
💡 在我的博客上,你将找到关于Java核心概念、JVM 底层技术、常用框架如Spring和Mybatis 、MySQL等数据库管理、RabbitMQ、Rocketmq等消息中间件、性能优化等内容的深入文章。我也将分享一些编程技巧和解决问题的方法,以帮助你更好地掌握Java编程。
🌐 我鼓励互动和建立社区,因此请留下你的问题、建议或主题请求,让我知道你感兴趣的内容。此外,我将分享最新的互联网和技术资讯,以确保你与技术世界的最新发展保持联系。我期待与你一起在技术之路上前进,一起探讨技术世界的无限可能性。
📖 保持关注我的博客,让我们共同追求技术卓越。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。