0

我有 3 种递归实现的方法。是的，这是给学校的，所以请不要简单明了的答案，我会很感激描述性的答案，这样我就可以学习了！我是树结构的新手。

3种方法如下...

public class Zombies{
   public static int countPeople(Person p){...}
   // counts all the people in the tree structure 
   // starting with Person p. 

   public static int countZombies(Person p){...}
   // counts all the people in the tree structure
   // starting with Person p that are zombies

   public static void draw(Person p){...}
   // draws a diagram of the people in tree structure
   // starting with Person p.
   // each person will be denoted by a P and 
   // person that is a zombie will be denoted by a Z
   //
   // The diagram should illustrate the family tree
   // structure.  Each person will be drawn with 3 minus  
   // signs '-' for each level below p.

我已经开始了我的 Person 课程，我有几个问题。

1）我的个人课程是否在正确的轨道上

2）方法描述中提到的树结构是二叉树吗？

3）能够实现这些方法我缺少什么（如果有的话，或者这个树结构是否需要构建块）

下面是我的 Person 类。

public class Person{

    public int     id;     // some identification number unique to the person
    public boolean zombie; // true if the person is a zombie
    public char    state;  // p means human, z means zombie

    public ArrayList<Person> friends;  // list of friends

    public Person(int id, char state, boolean zombie){
        this.id = id;
        this.state = state;
        this.zombie = zombie;
    }

    public boolean isZombie() {
        if (state == 'p'){
            return zombie=false;
        }
        else if (state == 'z'){
            return zombie=true;
        }
        return zombie;  
    }
}

树类型的示例输出如下..

P          (this is Person q)
---P       (this is a friend of q, say q1)
------P    (this is a friend of q1)
------Z    (this is another friend of q1, who is a zombie)
---Z       (this is a friend of q, say q2, who is a zombie)
------Z    (this is a friend of q1, who is also a zombie)
------P    (this is a friend of q1, who is not a zombie)

提前感谢您的耐心和帮助/输入！

4

4 回答 4

1

Hopefully this gives you some insight as to the implementation of an array based binary tree.

Taken from another post:

When you write binary trees as an Array you are building what's typically called a heap. Heaps are fairly well documented and this article will give you lots of detail about how they are implemented:

http://en.wikipedia.org/wiki/Binary_heap

Link to original:

ArrayList Based Binary Tree - Java

Edit:

What it looks like you are doing is creating a binary tree of people of class "Person". Each "parent" person has "friends" which would be children of that "Person". If the number of "friends" is limited to 2 then this is a binary tree format.

Trees are just organizational structures used to hold data... and in your case different people. The part of the binary heap that has no relevance to you is that heaps are organized based on node value. You don't need to worry about that.

So your class Zombie can take any person object and all of their associated "friends" and determine how many are people or zombies etc.

Each instance of a person will have a tree of friends, sort of, from which you can access from that person.

What makes the structure a tree is a link to the children from the parent. So person1 has 2 friends, friend1 and friend2. You then access friend1 and then check to see if he has any friends. If so, you check that friends friend and so on. This is a very generic explanation of the way trees can help you navigate information.

Basically, if any person in the tree has more than 2 friends, it is no longer a binary tree.

Check out this:

http://en.wikibooks.org/wiki/A-level_Computing/AQA/Problem_Solving,_Programming,_Operating_Systems,_Databases_and_Networking/Programming_Concepts/Tree_traversal_algorithms_for_a_binary_tree

This is an example of traversing trees. You can have values to increment as you traverse to give you the number of zombies or regular people in the tree.

I apologize if this is explanation seems scattered but I'm having a hard time understanding what you are trying to do and the organization.

Edit2:

Ok so you call the static function from the Zombie class. You need to recursively check the person and all his friends.

If you want this to be a binary tree implementation each person can have no more than 2 friends.

If it being a binary tree isn't required then there is no restriction on the size of the friends array in each person.

Essentially what you need to do is have the function in the Zombie class iterate through all the people (friends, friends of friends, etc) check to see if they are zombies. When you find out if they are, print to console the result. Then move on.

So look at the link I posted above about iterating through trees and apply that to the arraylist of friends for each person. There are different ways to recursively iterate through... so pick a style (which looks like you need in-order traversal) and implement the checking/printing function that way.

This is a lead, let me know if you get stuck again. The abstraction involved in understanding trees can be tricky.

于 2013-04-01T21:22:12.380 回答
1

1）也许不是你要找的，但我会摆脱Person.state. 有两个单独的字段都用于确定一个人是否是僵尸，这是令人困惑和容易出错的。when zombieistrue和stateis 是什么意思p？

2) Miorel 的评论有一些很好的见解。从你给我们的内容来看，这棵树应该代表什么，为什么它必须是一棵树，或者它是如何被填充的，这并不是很清楚。

3) 你需要某种 World 对象。Zombies可能是一个不错的选择。显然，在某个地方，您需要一棵所有人的树。至少，你需要一些人的集合。需要声明、实例化和填充该集合。您可能希望它成为Zombies该类的成员。Person绝对不是你会拥有很多的班级的一员。

于 2013-04-01T21:26:30.473 回答
0

  1. 是的，我认为你在正确的轨道上。但是，正如其他一些人指出的那样，同时拥有 achar state和boolean zombie是多余的。就个人而言，在这种情况下，我认为继承是主要的过度杀伤力——也许可以理解，如果你以后想要拥有可以是“僵尸”或“吸血鬼”甚至“狼人”的“人”， ” 然而，我认为在这种情况下，能够简单地说if (p.isZombie()) { ... }就足够了，但我将把它留在那里，因为这是一个古老的设计论点——我属于“组合优于继承”阵营（http://en.wikipedia.org/wiki/Composition_over_inheritance）

  2. 这确实是一个树结构，但是，我非常怀疑它是基于规范的二叉树，但是没有理由不能。对我来说，这似乎是一棵 N-Ary 树。如果您以前没有接触过这些树，它们只是一个通用的树结构，其中每个节点可以有任意数量的子节点。此链接给出了更好的解释：http ://www.brpreiss.com/books/opus5/html/page257.html （稍后会详细介绍）

  3. 你不会错过任何东西来实现这些方法（我可以说，这取决于你的教授——他们将如何标记这个？运行他们自己的测试代码？看看你的代码？或者你提供客户端代码（ main 方法）来演示它是如何工作的？如果他们正在运行测试代码，你必须确保你的 Person API 与他们的规范兼容）。

这里要理解的重要一点是您创建的数据结构以及它如何表示 N-Ary 树。该类Person表示树中的单个节点（任何节点，可以是根，没关系），并ArrayList<Person>存储属于该节点的每个子节点（或朋友）。它本质上是一个“链接结构”。考虑一下：

class Node {
    public ArrayList<Node> children = new ArrayList<Node>();
}

这个类有 0 个或多个孩子（存储在 中children），每个孩子都是一个Node（反过来有 0 个或多个孩子）。

因此，我可以轻松地将一些Node作为 root Node，然后以这种方式构建一棵树：

Node root = new Node();
root.children.add(new Node());
root.children.add(new Node());
root.children.get(0).children.add(new Node());
root.children.get(0).children.add(new Node());

从本质上讲，这将创建一棵树，可以这样表示：

    root
     /\
    /  \
   0    1
  / \
 /   \
0     1

现在，也许您可​​能会注意到为什么我之前说“没有理由不能成为 [二叉树]” 从技术上讲，二叉树是 N=2 的 N-Ary 树。

另一件重要的事情（关于 N-Ary 树的先前链接提到了它）是每个 Node 都可以被认为是它自己的 N-Ary 树。因此，例如，当您说draw(Person p)就方法而言，p将始终是某个 N-Ary 树的根——无论它实际上是整棵树的根还是只是树的某个子树的根。

希望这可以帮助！我知道你不久前发布了这个问题，所以我希望你成功地完成了这个问题，否则我还不算太晚。如果没有，也许它会帮助别人：/

此外，在处理这类问题（算法和数据结构）时要记住的重要一点是尽量不要被无关的细节所困扰，例如（在这种情况下），他们是否是“那些可能是僵尸和一些朋友，”等等。这不是我们正在寻找的抽象！我们只是想在树中表示这种关系！当然，这对于现实世界的问题会变得更加困难，因为我们并不总是得到最好的数据结构，而且我们经常需要利用不同类型的数据结构来创建一些任务。

始终尝试找出问题的根源，然后从那里着手。通常，您会发现很多问题只是添加了详细信息/数据的另一个简单问题；甚至只是另一个问题的轻微变化。

祝你学习顺利。

于 2013-04-30T01:28:02.020 回答
0

Q1）我的个人课程是否在正确的轨道上？

从我的角度来看，我必须说不。

它有什么问题？

你有多余的逻辑。领域zombie和state指人的潜力相同的地位。

在这一点上，我们必须做出决定，什么是僵尸，什么是人。做事，以同样的方式行事？根据我的观察，它们有一些共同的特征，但它们表达的元素也非常不同。为了证明这一点，让我们想象我们站在人类面前问他时间。很可能他会给我们一些合乎逻辑的答案。在我们完成问题之前，来自另一只手的僵尸肯定会尝试吃掉我们的大脑。

这就是为什么我不会使用继承机制而不是引入状态（顺便说一句应该是枚举）。

public class Person {

  private final int id;

  public Person(int id) {
   this.id = id;

  }

  public int hashCode() {
     return id;
  }

  public boolean equals(Object object) {

    if(object instance of Person) {
       return this.id == ((Person) object).id;
    }

    return false;
  }
}

public class Zombie : Person {

   public Zombie(int id) {
      super(id);
   }
)

如何表明朋友是人类还是僵尸？

为此，您使用了 method isZombie。因为我们现在有两个类有这个方法是不合理的。类Zombie代表僵尸和Human. 所以在代码中有类似if(human.isZombie()), 看起来很奇怪。

这就是 OOP 的强大之处。在检测到对象是这种类型或另一种类型时，我们不会插入。我们想要的是在控制台上显示（对于这种情况），通知用户该对象是人类或僵尸的有效字符。

为了能够做到这一点，我们必须向 Human 类添加一个方法，并在 Zombie 类中[覆盖]它。此方法将负责返回有效字符。

public class Person {

  //...   

  public char howDoOtherSeeMe() {

    return 'P';

  } 
}

public class Zombie : Person {

   //...

   @override
   public char howDoOtherSeeMe() {

    return 'Z';

  } 
}

Q2）方法描述中提到的树结构是二叉树吗？

A2。不，定义中的二叉树只能有两个节点并且不能有循环。此外，在我们的 Person 类中耦合结构可能会提供类快速增长且不受控制。

于 2013-04-02T13:17:55.490 回答