两天来我一直在尝试解决这个问题,但我不知道如何将数组表示为堆(从左到右)。我尝试在其他网站上寻找答案,但找不到。
问题是有一个给定的数组。例如……
{26,5,3,2,1,1...}
我需要像这样将其转换为无序堆。
26
/ \
5 3
/ \
2 1
到目前为止我所做的就是这个,但我无法弄清楚如何在转到正确的节点之前检查最左边的子节点是否已被填充。
package myTest;
public class UnsortedBT {
static int[] unsortedArr = new int[]{26,5,3,2,1,1,10,2,4};
public static void main(String[] args) {
// TODO Auto-generated method stub
UnsortedBT c = new UnsortedBT();
BinaryTree tree = c.new BinaryTree(unsortedArr[0]);
for(int i=1 ;i<unsortedArr.length;i++)
{
BinaryTree newTree = c.new BinaryTree(unsortedArr[i]);
tree.insert(newTree);
}
System.out.println(tree.left.left.right.data);
}
public class BinaryTree{
private BinaryTree right;
private BinaryTree left;
private int data;
public BinaryTree(int s){
data = s;
right = null;
left = null;
}
public int checkTree(){
if(left == null && right == null){
return 1;
}else if(left == null){
return 1 + right.checkTree();
}else if(right == null){
return 1 + left.checkTree();
}else{
return 1 + left.checkTree() + right.checkTree();
}
}
public void insert(BinaryTree bt){
if(left == null){
setLeft(bt);
}else if(right == null){
setRight(bt);
}else{
int leftCheck = left.checkTree();
int rightCheck = right.checkTree();
// The problem is lies here
if(leftCheck==rightCheck||left!=null&&left==null){
left.insert(bt);
}else{
right.insert(bt);
}
}
}
public void setLeft (BinaryTree l){ left = l; }
public void setRight(BinaryTree r){ right = r; }
}
}
最佳答案
嗯,我认为你正在做 DFS,这会引起困惑 你可以用 BFS 方式做同样的问题
queue.add(new Node(a[0])// Initilize queue with first element
intilize array index counter variable i=0
while(queue.isnotempty)
{
node currentnode=queue.deque();
int left=2*i+1
int right=2*i+2
currentnode.left=new Node(left>array.lenght-1?null:array[left]); //put left variable
currentnode.right=new Node(right>array.lenght-1?null:array[left]); //put right node
if(currennode.left!=null)
queue.enquer(currennode.left);
if(currennode.right!=null)
queue.enquer(currennode.right);
i++;
}
Algorithm works on bfs 我们做的是BFS遍历 逐个递增索引并将子节点添加到子节点队列中,然后将其出队
找到更新后的工作代码
package com;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
class Node {
int node;
Node left = null;
Node right = null;
public Node(int value) {
// TODO Auto-generated constructor stub
this.node = node;
}
}
public class ArrayToHeap {
public static void main(String... args)
{
int [] array = new int[]{1,2,3,4,5,6};
Node head=new Node(1);
Queue<Node> queue = new LinkedList();
queue.add(head);
int i=0;
while (!queue.isEmpty())
{
Node currentnode=queue.remove();
int left=2*i+1;
int right=2*i+2;
currentnode.left=left>array.length-1?null:new Node(array[left]);
currentnode.right=right>array.length-1?null:new Node(array[right]);
if(currentnode.left!=null)
queue.add(currentnode.left);
if(currentnode.right!=null)
queue.add(currentnode.right);
i++;
}
}
}
关于arrays - 使用给定的数组创建一个未排序的堆(从左到右),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/38355502/