使用给定的数组创建一个未排序的堆（从左到右）

Question

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

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

{26,5,3,2,1,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; }        
}
}

Answer 1

如果您的节点是 i 那么您可以将子节点指定为 2i + 1 和 2i + 2。

loop(i to n/2){
   iParent(i)     = i;
   iLeftChild(i)  = 2*i + 1;
   iRightChild(i) = 2*i + 2;
}

尝试这样的事情。

Answer 2

好吧，我认为你正在做 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++;
    }



}
}

Answer 3

所以你想从数组构建一个二叉树。您给出的示例表明树在数组中以 breadth-first 顺序表示。也就是说，数组中索引为 0 的项目是根。接下来的两项是根的children。接下来的四个是那些children的children，等等

正如 Aman Sachan 在他的回答中指出的那样，您可以通过以下方式确定节点的 children：

left child index = (node index)*2 + 1
right child index = (node index)*2 + 2

使用该信息，您可以递归地构建树，depth-first，就像您对二叉树进行中序遍历一样。像这样的伪代码。

tree_node build_tree(array, index)
{
    // if the index is beyond the end of the array, then there's
    // no node here.
    if (index >= array.length)
        return null;

    // create the new node with the proper value.
    new_node = new tree_node(array[index]);

    // build the left node
    new_node.left = build_tree(array, (2*index) + 1);

    // and the right node
    new_node.right = build_tree(array, (2*index) + 2);

    // and then return the newly-built node
    return new_node;
}

您通过传递数组和第一个索引来调用它：

tree_node root_node = build_tree(array, 0);

还有另一个解决方案反映了二叉树的 breadth-first 遍历。如果懂breadth-first遍历，应该可以自己推导出解

使用给定的数组创建一个未排序的堆（从左到右）

Create an unsorted heap (left to right) using given array

arrays

algorithm

heap

binary-tree