Question:

Write a program to transform a free tree to a rooted tree. The free tree and the root are input by the user, and for the rooted tree, you output it level by level. (Hint: Use Adjacency Matrix or Adjacency Lists to store the tree, and use queue to implement the transformation.)

I am having trouble adding each node to its respective parent using the adjacency list. Also, I need to be able to print out each node level by level.

Here is my attempt:

import java.util.ArrayList;

import java.util.Arrays;

import java.util.List;

import java.util.Scanner;

public class ExtraCredit {

private static Scanner scanner;

public static void main(String[] args) {

scanner = new Scanner(System.in);

int size;

int value;

int value2;

int[] arr;

int count = 0;

int edges;

int root;

int temp = 0;

int end = 0;

int position;

System.out.println("Enter the number of vertices in a free tree: ");

size = scanner.nextInt();

arr = new int[size];

System.out.print(" ");

System.out.println("Enter a list to represent vertice values (ex: 1 2 3 4 5): ");

for (int i = 0; i < arr.length; i++) {

arr[i] = scanner.nextInt();

}

System.out.print(" ");

System.out.println("Array generated: " + Arrays.toString(arr));

Graph graph = new Graph(size);

System.out.print(" ");

System.out.println("How many edges are there in your free tree?");

edges = scanner.nextInt();

while (count != edges && edges != 0) {

System.out.print(" ");

System.out.println("Enter an edge (ex: 1 2; creates an edge between index value 1 and 2): ");

value = scanner.nextInt();

value2 = scanner.nextInt();

if (value >= 0 && value < size && value2 >= 0 && value2 < size) {

graph.addEdge(value, value2);

}

count++;

}

System.out.print(" ");

System.out.println("Adjacency Matrix:");

for (int i = 0; i < arr.length; i++) {

for (int j = 0; j < arr.length; j++) {

if (graph.adjacencyMatrix[j][i] == true) {

System.out.print(1 + " ");

} else {

System.out.print(0 + " ");

}

}

System.out.print(" ");

}

System.out.print(" ");

System.out.println("Adjacency List:");

Integer[][] adjacencyList = new Integer[size][size];

for (int i = 0; i < arr.length; i++) {

for (int j = 0; j < arr.length; j++) {

if (graph.adjacencyMatrix[j][i] == true) {

adjacencyList[j][i] = arr[j];

}

}

}

for (int i = 0; i < arr.length; i++) {

System.out.print(arr[i] + ": ");

for (int j = 0; j < arr.length; j++) {

System.out.print(adjacencyList[j][i] + " ");

}

System.out.print(" ");

}

System.out.print(" ");

System.out.println("Choose a root to to transform the free tree by entering the index of the array: ");

root = scanner.nextInt();

Node tree = new Node(root);

Node tempTree = null;

int[] previous = new int[2];

// The end == 1000 was for testing purposes.

while(end == 1000) {

int j = root;

for (int i = 0; i < adjacencyList.length; i++) {

if (adjacencyList[j][i] != null) {

tempTree = new Node(adjacencyList[root][i]);

tree.addChild(tempTree);

previous[0] = j;

previous[1] = i;

}

}

end = 1000;

}

List listTree = tree.getChildren();

System.out.println(tree.getData());

for (int i = 0; i < listTree.size(); i++) {

System.out.println("YES: " + listTree.get(i).getData());

}

System.out.println("Size: " + listTree.size());

}

public static class Node {

private final Integer data;

private List children = new ArrayList<>();

public Node(Integer data) {

this.data = data;

}

public void addChild(Node node) {

children.add(node);

}

public List getChildren() {

return children;

}

public Integer getData() {

return data;

}

}

public static class Graph {

public static boolean adjacencyMatrix[][];

public int vertexCount;

public Graph(int vertexCount) {

this.vertexCount = vertexCount;

adjacencyMatrix = new boolean[vertexCount][vertexCount];

}

public void addEdge(int i, int j) {

if (i >= 0 && i < vertexCount && j > 0 && j < vertexCount) {

adjacencyMatrix[i][j] = true;

adjacencyMatrix[j][i] = true;

}

}

public void removeEdge(int i, int j) {

if (i >= 0 && i < vertexCount && j > 0 && j < vertexCount) {

adjacencyMatrix[i][j] = false;

adjacencyMatrix[j][i] = false;

}

}

public boolean isEdge(int i, int j) {

if (i >= 0 && i < vertexCount && j > 0 && j < vertexCount)

return adjacencyMatrix[i][j];

else

return false;

}

}

}