Базовый массив [] Структура данных дерева в Java

Question

Это вопрос домашней работы, поэтому я не ищу полный код ответа.

я был дан класс 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; 
    } 

} 

И файл данных, который содержит корень собака пятно, которая имеет своих детей, хранящихся в массиве. Мне нужно написать код, который может открыть файл данных, а затем перейти через структуру данных дерева, чтобы узнать, является ли входное имя потомком корня (Spot).

Я довольно уверен, что могу открыть файл данных. Я борюсь с синтаксисом создания узлов, у которых есть массив в качестве ссылки. Наш учебник охватывает только бинарные деревья, которые либо связаны с левым или правым, но не с переменным числом ссылок. Я нашел пример универсального метода, который использует подход List.

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>>(); 
    } 
} 

Поскольку я должен использовать файл данные я не могу изменить структуру узла на что-либо другое, чем хранение детей в собачке []. Я не могу найти пример класса node, используя базовый массив для хранения дочерних элементов, и я не могу понять синтаксис для этого. Я думаю, что это поможет моему пониманию увидеть это без дженериков, прежде чем я попытаюсь изучить его.

Вот мой код до сих пор:

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

вам нужно перебрать массив детей.

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; 

    } 

Answer 2

Основное различие между массивом и списком массива в этих алгоритмах является то, что у вас есть ограниченные возможности для массивов и вам необходимо обрабатывать распределение элементов (щенки);

Вы не должны фокусироваться на родовом, если задача состоит в том, чтобы изучить массив. Generic позволяет вам определить шаблон для общей функциональности объектов. Лучше изменить реализацию, когда это делается в родовом, чем начинать с них, чтобы решить конкретную проблему.

То, что вы сейчас класс как это:

class Dog { 

    private String name; 
    private Dog[] puppies 

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

} 

Что вы можете сделать, это добавить конкретный метод к нему, который будет выполнять какие-то действия.

class Dog { 

    private final String name; 
    private final Dog[] puppies = new Dog[20]; //We create 20 slots for puppies to fill 
    private int puppiesCount = 0; 

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

    public addPuppie(Dog puppie) { 
     this.puppies[puppiesCount] = puppie; //We assign the puppie to this Dog puppies. 
     this.puppiesCount = puppiesCount + 1; //We increment the count of puppies 
    } 

    public Dog[] getPuppies() { 
     return Arrays.copyOf(puppies, puppiesCount); 
    } 

    public boolean isMyPuppie(Dog puppie) { 

     for(int = 0; i < puppiesCount; i++) { 

      if(puppies[i] == puppie) { //We compare the object references to state that are equal 
      return true; 
      } 

     } 

     return false; 
    } 
} 

Как эта передача в дерево.

Поскольку каждый объект имеет массив из себя, его можно гнездить.

Dog max = new Dog("Max"); 

Dog tom = new Dog("Tom"); //childOfRoot; 

Dog barry = new Dog("Barry);"// child of Tom 

Чтобы создать дерево, вам нужно сделать что-то подобное.

tom.addPuppie(barry); // We assign barry to tom 
max.addPuppie(tom); // we assign tom to max. 

Эта концепция должна быть расширена с глубоким поиском, где вам нужно ввести поиск возвратность и отношение от ребенка к родителю может быть добавлен.