ArrayList based binary tree implementation in Java

1) Maybe not what you're looking for, but I would get rid of Person.state. Having two separate fields that are both used for determining whether a person is a zombie or not is confusing and error prone. What does it mean when zombie is true and state is p?

2) Miorel's comment has some good insights. It's not really clear from what you've given us what the tree is supposed to represent, why it has to be a tree, or how it gets populated.

3) You need some sort of World object. Zombies might be a good choice. Somewhere, apparently, you need a tree of all people. At the very least, you need some sort of collection of people. That collection needs to be declared, instantiated and populated. You might want it as a member of the Zombies class. Definitely not as a member of the Person class of which you'll have many.

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.

Q1) Am i on the right track with my person class ?

From my point of view i must say no.

What is wrong with it ?

You have redundant logic. Fields zombie and state refer to the same status of human potential.

At this point we have to make a decision what is a zombie and what is a person. Do the act, behave in the same way ? From my observation they have some common features but also very distinct elements of they expression. To prove it let imagine we stand in front of human an ask him about the time. Most probably he will give us some logic answer. Zombie from other hand will for sure try to eat our brain before we finish the question.

That is why instead of introducing status (that btw should be a enum) i would use the inherit mechanism.

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

How to show that a friend is human or zombie ?

For this purpose you have used method isZombie. As we have now two classes having this method is irrational. As class Zombie stand for zombies and Human. So having in code something like if(human.isZombie()), looks oddly.

And here is where the power of OOP kick. We are not inserted, on detecting that an object is this type or another. What we want is to present on console (for this case), the valid character that inform user that this object is human or zombie.

To be able to do that we must add a method to class Human and [override] it in class Zombie. This method will be responsible for returning valid char.

public class Person {

  //...   

  public char howDoOtherSeeMe() {

    return 'P';

  } 
}

public class Zombie : Person {

   //...

   @override
   public char howDoOtherSeeMe() {

    return 'Z';

  } 
}

Q2)Is the tree structure mentioned in method descriptions a binary tree?

A2. No. Binary tree from definition can have only two nodes and cant have cycles. Also coupling the structure inside our Person class might provide class to grow rapidly and without control.

1. Yes, I think you are on the right track. But, just as some others have pointed out, having both a char state and boolean zombie is redundant. Personally, in this case, I think that inheritance is major overkill--understandable, perhaps, in the case where you may later want to have "person" who can be a "zombie" or a "vampire" or even a "werewolf," however, I think in this case being able to simply say if (p.isZombie()) { ... } would suffice, but I'll leave it at that since this is an age-old design argument--of which I belong in the "composition-over-inheritance" camp (http://en.wikipedia.org/wiki/Composition_over_inheritance)

2. This is indeed a Tree structure, however, I highly doubt it is a binary tree--based on the spec, however there is no reason it couldn't be. To me, this appears to be an N-Ary Tree. Which, in case you haven't touched on these trees before, they are simply a generic tree structure where each node can have any number of children nodes. This link gives a better explanation: http://www.brpreiss.com/books/opus5/html/page257.html (more on this in a moment)

3. You are not missing anything to implement those methods (that I can tell, it would depend on your professor--How are they going to mark this? Run their own test code? Just look at your code? Or are you providing client code (main method) that demonstrates how this works? If they are running test code, you will have to be sure that your Person API is compatible with their specs).

The important thing to understand here, is the data structure you have created and how it represents an N-Ary Tree. The Person class represents a single node in the Tree (any node, could be root, doesn't matter) and the ArrayList<Person> stores each child node (or friend) that belongs to the node. It's essentially a "linked-structure." Consider this:

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

This class has 0 or more children (stored in children), and each child is a Node (which, in turn has 0 or more children).

So, I could easily make some Node to be the root Node, and then build a tree that way:

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

In essence, this would create a tree that might be represented as such:

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

Now, perhaps you might notice why I said previously "there is no reason it couldn't be [a binary tree]" Technically speaking, an binary tree is an N-Ary tree where N=2.

Another thing which is important to realize (the previous link about N-Ary trees mentions it), is that each Node can be thought as its own N-Ary tree. So, for example, when you say draw(Person p) as far as the method is concerned, p will always be the root of some N-Ary tree--whether it is actually the root of an entire tree or just the root of some subtree of the tree.

Hope this helps! I know you posted this question a while ago, so I hope you managed to complete this successfully or I'm not too late. If not, maybe it will help someone else :/

Also, the important thing to remember when tackling these kinds of problems (Algorithms and Data Structures) is by trying not to be bogged down by extraneous details, for example (in this instance), it is not too important whether they are "People who might be Zombies with some Friends," etc. That's not the abstraction we are looking for! We simply want to represent this sort of relationship in a Tree! Of course, this will become harder for real world problems since we aren't always given the best data structure, and often we need to leverage different types of data structures in order to create some task.

Always try to isolate the root of the problem, and go from there. Often you'll find a lot of problems are simply another simple problem with added details/data; or even just a slight variation of another problem.

Best of luck in your studies.