java - Java 中的基本 Array[] 树数据结构

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，其子项存储在数组中。我需要编写可以打开数据文件的代码，然后遍历树数据结构以查看输入名称是否是根 (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>>();
    }
}

因为我必须使用数据文件，所以除了将子节点存储在 Dog[] 中之外，我无法将节点的结构更改为任何其他内容。我找不到使用基本数组存储子节点的节点类示例，而且我无法弄清楚执行此操作的语法。我认为在我尝试使用泛型学习之前先看看它是否有助于我的理解。

到目前为止，这是我的代码:

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;

    }