arrays - 使用给定的数组创建一个未排序的堆(从左到右)

标签 arrays algorithm heap binary-tree

两天来我一直在尝试解决这个问题,但我不知道如何将数组表示为堆(从左到右)。我尝试在其他网站上寻找答案,但找不到。

问题是有一个给定的数组。例如……

{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/

相关文章:

c++ - 创建有点太大的数组时出现段错误

php - 如何从数组中过滤特定值?

algorithm - 使用多个 CPU 查找最大数量的最短时间

Python合并算法

python - 最大小费计算器 - 天真的解决方案

java - hive 中带有条件参数的数组的大小

arrays - iOS12 中的 NSKeyedUnarchiver 更改 - 如何取消存档字符串数组

heap - Java PriorityQueue 实现 : Why Object[] queue instead of E[] queue? siftUp/siftDownComparable 中 "key"的用途是什么?

heap - 没有数组的 MinMax Heap 实现

arrays - 有效合并多集的 n 个元素的数据结构