6

这是一个家庭作业问题，所以我不是在寻找完整的代码答案。

我已经上了一个班狗

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

2 回答 2

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;

    }
于 2013-12-23T14:54:21.920 回答
0

这些算法中数组和数组列表之间的主要区别在于您的数组容量有限，并且您需要处理项目（小狗）的分配；

如果任务是学习数组，则不应专注于泛型。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;
    }
}

这是如何转移到树上的。

由于每个对象都有一个 is self 数组，因此可以嵌套它们。

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.

这个概念应该通过深度搜索来扩展，您需要引入递归搜索并且可以添加从子到父的关系。

于 2013-12-23T15:46:04.830 回答