I have a setup like this

The first part of the question is to implement a function that generates a complete binary tree (i.e. two arrays) with a given size as input where the node and edge weights are set randomly between 1 and 20 inclusive.

I wrote the code below for the first part and I need to develop a greedy algorithm and a recursive algorithm for finding the shortest path for all nodes in the tree.

How can I develop greedy and recursive algorithms guys?

public static void main(String[] args) {

    System.out.println(Arrays.toString(randWN(9)));
    int[][] qq=randWE(9);

    for (int[] row : qq)
        System.out.println(Arrays.toString(row));
}

public static int[] randWN(int size)
{
    int[] WN=new int[size];
    for (int i = 0; i < WN.length; i  ) {
        WN[i]=getRandomNumber(1,20);
    }
    return WN;
}
public static int[][] randWE(int size)
{
    int counter=0;
    int iterator=0;
    int[][] WE=new int[size][size];
    for (int i = 0; i < WE.length; i  ) {
        for (int j = 0; j < WE[size-1].length; j  ) {
            if(j>iterator && counter<2)
            {
                WE[i][j]=getRandomNumber(1,20);
                counter  ;
                iterator  ;
            }
        }
        counter=0;
    }
    return WE;

}
public static int getRandomNumber(int min, int max) {
    return (int) ((Math.random() * (max - min))   min);
}

output of the first part is here

CodePudding user response：

Correct me if am mistaken, but your code does not produce a binary tree, but rather a square matrix. How does this represent a complete binary tree?

I think an implementation using a class node with parent and child attributes which in turn are nodes as well, makes more sense?

And then you just follow a greed algorithm to find the shortest path. E.g. recursively traverse the tree, always choosing to cheapest path to the next node, and backtrack once you are at a leaf. Maybe looking up binary trees on wikipedia might help.

Or I missinterpreted something and am completely wrong.

CodePudding user response：

i attached screenshots in the question but it didn't attached sorry for that this is the question

and i finished the first part it has 2 array