Basic Array[] Tree Data-Structure in Java

Question

This is a homework question, so I'm not looking for a complete code answer.

I have been given a class Dog

package lab12;

import java.io.Serializable;

public class Dog implements Serializable{

    public Dog[] children;
    public String name;

    public Dog(String name)
    {
        this.name = name;
    }

    @Override
    public String toString()
    {
        return name;
    }

}

And a datafile that contains a root dog Spot that has its children stored in an array. I need to write code that can open the datafile, and then step through the tree data structure to see if an input name is a descendant of the root (Spot).

I am pretty confident I can open the datafile. I am struggling with the syntax of creating nodes that have an array as the link. Our textbook covers only binary trees, which either link to left or right, but not to a variable number of links. I found an example of a generic one that uses a List approach.

public class Tree<T> 
{
    private Node<T> root;

    public static class Node<T> 
    {
        private T data;
        private Node<T> parent;
        private List<Node<T>> children;
    }

    public Tree(T rootData) 
    {
        root = new Node<T>();
        root.data = rootData;
        root.children = new ArrayList<Node<T>>();
    }
}

Since I have to use the datafile I can't change the structure of the Node to anything other than storing the children in a Dog[]. I can't find an example of a node class using a basic array to store the children and I can't figure out the syntax for doing this. I think it would help my understanding to see it without generics before I try to learn it with.

Here's my code so far:

package lab12;

public class DogTree 
{
    //Start Inner Class
    private static class Node
    {
        private String name;
        private Node parent;
        private Node Dog[] children; //This is where I'm confused
    }
    //End Inner Class

    private Node root;

    public DogTree()
    {
        root = null;
    }

    public boolean isDescendant(String name)
    {
        return isInSubtree(name, root);
    }

    private static boolean isInSubtree(String name, Node subTreeRoot)
    {
        if(subTreeRoot == null)
        {
            return false;
        }
        else if(subTreeRoot.name.equals(name))
        {
            return true;
        }
        else
        {
            //This is where my confusion on the 
            //node design causes implementation problems
            return isInSubtree(name, subTreeRoot.children); 
        }
    }
}

Answer 1

you need to iterate over the array of children.

private static boolean isInSubtree(String name, Node subTreeRoot)
    {
        if(subTreeRoot == null)
        {
            return false;
        }
        else if(subTreeRoot.name.equals(name))
        {
            return true;
        }
        else
        {
           for( int i = 0; i< subTreeRoot.children.length();i++)
             if(isInSubtree(name, subTreeRoot.children[i]))
            return true;
        }
        return false;

    }