Building an ArrayList tree - Java

Question

How can I build a basic tree of Objects from an ArrayList (in this case Person objects from my Person class below)? Conceptually I understand how the tree works, how to add Objects to my arraylist but I am having a lot of trouble with the building aspect of the tree and linking nodes together I seem to find overwhelming. Also, from the research i have done, it seems that a recursvie algorithm is the best way to tackle this. Is it true? I am a beginner in Java so please a detailed answer and not just code would be appreciated.

Here is the the Person class i have and which the objects in the tree i want to base it from.

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){
        this.id = id;
        this.state = state;
        //this.zombie = zombie;
    }

Thanks in advance for any input and explanations. It is greatly appreciated!

below is sample output and demonstrates the desired hierarchy of the tree

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)

id like to create the tree structure so that there are no cross-links. Each Person in the tree structure can exist in only one friend's list and there will be one Person that is in no ones friend's list (the root of the tree). and each friend can only have two friends. (i assume this is a binary tree)

Edit: Could I use the treemap that is provided by java?

@supersam654 well im trying to make a tree from objects in my arraylist — choloboy7, Apr 03 '13 at 14:03
What kind of relationship/hierarchy should your tree represent? Is it friends, friends of friends, etc? — PM 77-1, Apr 03 '13 at 14:03
Is there any reason for doing this task or is it a pure learning exercise? — PM 77-1, Apr 03 '13 at 14:06
@PM77-1 it is a self created expansion of a assignment in school. Which is why im asking for detailed answers and not just code. I am learning Java and hope to someday become a guru ;) gotta challenge myself to get there! — choloboy7, Apr 03 '13 at 14:10
OK. How is this friendship currently reflected in your `ArrayList`? Where is this info in your `Person` class? — PM 77-1, Apr 03 '13 at 14:11
@PM77-1 lets assume Person root is the root. root can have two friends, either a person or a zombie, we will call friend 1 person1 and friend 2 zombie1, person1 can have two friends person2 and zombie2, and so on. Did i answer your question? If not please ask in a different way as i may not understand what you mean :S thanks! — choloboy7, Apr 03 '13 at 14:17
the purpose of this program, is to create the tree of two types of person object, and to practice creating methods that will count each of the types within the tree. — choloboy7, Apr 03 '13 at 14:20
"lets assume Person root is the root" - the trouble here is that they are ALL instances of Person, not just the root. Also, what happens when A is a friend of B and B is a friend of A? You get a circular reference. Building a tree like the one you required is a tricky task even for an experienced developer. — NickJ, Apr 03 '13 at 14:32
@NickJ I am no experienced developer :P is there a simpler way to create a tree of type person? — choloboy7, Apr 03 '13 at 14:48
How is a List a Tree? A List is a list of objects, in your case, Person. See this Stack Overflow answer for a basic Tree structure. http://stackoverflow.com/a/3522481/300257 — Gilbert Le Blanc, Apr 03 '13 at 15:47
@choloboy7 - You explicitly state that you want to "build a basic tree of Objects **from an ArrayList**". If you wanted just to build a tree from scratch that will be a different question with different responses. If, however, you really want to build the tree from the information already in your ArrayList, then you need to explain how you plan to do so. `ArrayList` is an essence just a convenient repository for objects that can be accessed by their indexes. Each object is completely oblivious of all others. You simply do not have enough info there to build a tree. — PM 77-1, Apr 03 '13 at 16:36

score 0 · Accepted Answer · answered Apr 03 '13 at 16:04

Maybe I am missing something but what does ArrayList (or lists in general) have to do with the task? If any person can have links to a number of people then it is a graph. E.g. it may have cycles like A->B->C->A that you can't represent using a tree.

The fact a person has a list of friends means that a node in the graph can be linked to arbitrary number of other nodes.

So I think you should build a graph.

If you want to get rid of duplicate links (e.g. A->B, B->A) then do it as a post-processing step.

score 0 · Answer 2 · answered Apr 03 '13 at 16:18

If I have understood the problem properly and correctly, you can use TreeMap with a Comparator to build such a tree structure. Iterate over the ArrayList adding each element to the treemap. The Comparator.compare(k1, k2) should implement the relationship that you are trying to put here. One example can be found here example1 and here example2

Building an ArrayList tree - Java

2 Answers2