JAVA - Finding depth of a tree (almost done)?

Question

We are given a file with 99999 lines. Each line of the file represents a single node and it contains four integer: key, value, left child key, right child key (in the order specified). Key is a unique identifier assigned to each node. This identifier is just the line number. Value is the integer value stored in the node of the tree. Left and Right children are keys of the two appropriate children of the node. If a left or right child key is equal to zero, the appropriate child does not exist. The root node of the tree has key one.


Here are the first 10 lines, for example:
1 75 2 4
2 68 6 7
3 58 9 10
4 88 12 15
5 28 18 19
6 27 21 22
7 24 24 25
8 5 28 29
9 69 31 34
10 61 37 38

For example, the first line of the file is 1 75 2 4. It means that value of the node with key 1 is 75, key (line of file) of the left child of this node is 2, and key of right child is 4. Note: not all nodes in the file are part of the tree. Some lines in the file are there just to confuse you. What is the depth of this tree? (Depth is defined as the total number of nodes along the longest path.)

So... this is what I have so far:

import java.util.*;
import java.io.*;

class HW4
{
public static void main(String[]args) throws Exception
{
Scanner sc = new Scanner(new File("assignment_4.input"));
while(sc.hasNextLine())
{
int key = sc.nextInt();
int v = sc.nextInt();
int l = sc.nextInt(); //left child
int r = sc.nextInt(); // right child
TreeNode n = new TreeNode((TreeNode) key, (TreeNode) v, (TreeNode) l, (TreeNode) r); }
// System.out.println("The depth of the tree is " + depth + ".");
}
}

class TreeNode
{
int value;
TreeNode leftChild, rightChild;
TreeNode(TreeNode l, int v, TreeNode r)
{
value = v;
leftChild = l;
rightChild = r;
}
public int depth()
{
int ld = 0, rd = 0;
if (leftChild != null) ld = leftChild.depth();
if (rightChild != null) rd = rightChild.depth();
return Math.max(ld, rd) + 1;
}
}

What is wrong with my program? Obviously it doesn't work, but what do I do to fix it? If you want, you can do the whole problem and post it here. I have to find the depth of this tree with Java. Thank you! :)

Answer 1

Your problem is here:



int v = sc.nextInt();

int l = sc.nextInt(); //left child

int r = sc.nextInt(); // right child

TreeNode n = new TreeNode((TreeNode) key, (TreeNode) v, (TreeNode) l, (TreeNode) r);



You can not cast an int into a TreeNode. In fact, I'm guessing that you are getting a ClassCastException (that is, if it even compiles).



The issue comes in that you are referring to nodes before they are created. This means that as you are building your tree, you are going to need to refer to some nodes by reference (their node numbers).



There's a number of ways of building this tree. Here's a few:

1) Refer to nodes by their number, then look up nodes via another mechanism, such as a map or an index in an array.

2) Make two passes through the list. The first pass will build the nodes and put them in an array or in a map. The second pass will build the tree.

3) Build a list of prototype objects that represents the contents of the file, then build the tree using that.

Answer 2

To find the maximum depth of the tree you don't even need to build it, just fill in an array of nodes as you read them from the file, the array is indexed by the node number:



Define a class to represent a node. It will have four integer fields, one for each of the four numbers on the line for the node. The first number is really not needed as you will see below.



Declare and allocate an array of 100,000 nodes. Open the input file and read each line, getting the four numbers on the line (this seems like the part you are having trouble with). Once you have the four numbers, use the first number as an index into the node array. Construct a new node using the other three numbers and assign that new node into the array at the position indicated by the first number.



Once you have this data structure built, it's just a matter of recursively traversing it to find the maximum depth from the root; something like this:



int maxDepth ( int nodeId )

{

if (nodeId == 0) return 0;

int leftDepth = maxDepth(nodes[nodeId].left);

int rightDepth = maxDepth(nodes[nodeId].right);

return 1 + (leftDepth > rightDepth ? leftDepth : rightDepth);

}



where you call this function with the node id of the root node (1).

Answer 3

Step a million: Create an array of the a hundred thousand Node factors needed to keep all the entries. you may desire to have the fields 'fee', 'leftIndex', and 'rightIndex'. you do no longer might desire to keep the considerable for each ingredient, using fact the considerable often is the index of that ingredient in this array. Step 2: Write a recursive approach. This set of rules will verify the intensity of any given subtree; you grant it with the index of its "root" node, and it determines the intensity at that node. hint - the intensity at a given node is the utmost of the depths of its 2 infants, plus one. If the two newborn-indexes are 0, then the intensity of that subtree is a million.