Results 1 to 19 of 19
  1. #1
    Nacao is offline Member
    Join Date
    Aug 2011
    Posts
    9
    Rep Power
    0

    Question Tree data structure

    Hi there!

    Well, this is my problem. I want to create a tree data structure in Java but, honestly, I can't find any useful example. I took a look to JTree class but I am not really interested in drawing my tree on a window. Do I have to create a whole tree class with its methods?

    I need this structure so my algorithm can examine it as a tree and apply a prune criteria.
    Example: Imageshack - matchtree.png

    I gave a try to other data structures but I didn't find anything interesting.

    Thanks in advance!

  2. #2
    KevinWorkman's Avatar
    KevinWorkman is online now Crazy Cat Lady
    Join Date
    Oct 2010
    Location
    Washington, DC
    Posts
    3,690
    Rep Power
    8

    Default

    JTree is not a data structure, it's a GUI component. You might want to look at TreeSet or TreeMap instead.
    How to Ask Questions the Smart Way
    Static Void Games - Play indie games, learn from game tutorials and source code, upload your own games!

  3. #3
    Nacao is offline Member
    Join Date
    Aug 2011
    Posts
    9
    Rep Power
    0

    Default

    TreeSet is not really useful to me because I want to store duplicated elements and TreeMap works with keys, which is not what I am looking for.

    First, I want to create a customized tree (choosing the number of nodes for each level, add/delete nodes...) applying a prune criteria to delete branches so my algorithm can work faster with the content of the nodes.

  4. #4
    KevinWorkman's Avatar
    KevinWorkman is online now Crazy Cat Lady
    Join Date
    Oct 2010
    Location
    Washington, DC
    Posts
    3,690
    Rep Power
    8

    Default

    So what's your question then?
    How to Ask Questions the Smart Way
    Static Void Games - Play indie games, learn from game tutorials and source code, upload your own games!

  5. #5
    Nacao is offline Member
    Join Date
    Aug 2011
    Posts
    9
    Rep Power
    0

    Default

    Sorry. Is there any already implemented Java class that allows me to do what I want?

  6. #6
    Nacao is offline Member
    Join Date
    Aug 2011
    Posts
    9
    Rep Power
    0

    Default

    Mmmm...

    I've been thinking that maybe it would be better to create a Node class containing the name of the node, the data to be manipulated and an ArrayList with the list of the child nodes.

    Although I guess that the operations will be a bit complicated (ex. delete node). Almost all of them will be recursive to navigate through the linked ArrayList, right?

    Would it be better a LinkedList instead of an ArrayList?

  7. #7
    KevinWorkman's Avatar
    KevinWorkman is online now Crazy Cat Lady
    Join Date
    Oct 2010
    Location
    Washington, DC
    Posts
    3,690
    Rep Power
    8

    Default

    Why do you need an ArrayList or a LinkedList? If you have a node that points to another node that points to another node, in a tree structure, why do you need another data structure to hold them? Wouldn't that defeat the purpose of making them a tree?

    Is this for a homework assignment?
    How to Ask Questions the Smart Way
    Static Void Games - Play indie games, learn from game tutorials and source code, upload your own games!

  8. #8
    Nacao is offline Member
    Join Date
    Aug 2011
    Posts
    9
    Rep Power
    0

    Default

    How could I point to other node if Java doesn't use pointers? The only way I can do that is to store the children nodes in the father node itself, right?
    I am a bit new to Java so maybe I am talking nonsense.

    No, it's not homework. It's something bigger but I got stuck in this part. It's a modification/optimization of an algorithm. What I want to do is to prune the branches that are not necessary to analyze. I mean, if a node doesn't fullfil the algorithm requirements once it has been analyzed, all their children could be erased so the algorithm doesn't waste time analyzing them because they are neither going to fullfil the requirements. Sorry about the word tongue twister

    That's why I thought about a tree structure. Maybe ArrayList of ArrayList could be a solution. I'm a bit lost right now

  9. #9
    KevinWorkman's Avatar
    KevinWorkman is online now Crazy Cat Lady
    Join Date
    Oct 2010
    Location
    Washington, DC
    Posts
    3,690
    Rep Power
    8

    Default

    I'm not sure why Java's lack of pointers seems like a deal breaker to you. What can references (or to be pedantic, the values of references) not do that pointers can in this case? How would you do this with pointers? Do it with references instead.
    How to Ask Questions the Smart Way
    Static Void Games - Play indie games, learn from game tutorials and source code, upload your own games!

  10. #10
    Nacao is offline Member
    Join Date
    Aug 2011
    Posts
    9
    Rep Power
    0

    Default

    The thing is that I don't know how to save the children nodes of a node using references.
    How could I represent that? Would I be able to access the rest of the children nodes via the father node?

    On each node I need a name for it, a boolean to explain if the node passed the algorithm check (the data to be manipulated by the algorithm will be the name of the node) and a structure to store the children node. (That's why I used an ArrayList).
    That's what I have done to represent that:

    Java Code:
    public class Node {
        
        String name;
        //Name of the node.
        int match;
        //Attribute match: 1:CONSISTENT MATCH, -1:NOT CONSISTENT MATCH, 0:UNKNOWN.
        ArrayList <Node> children;
        //List of children nodes.
        }
    Any idea of a more efficient way to store the children nodes?

  11. #11
    R-J
    R-J is offline Member
    Join Date
    Aug 2011
    Posts
    11
    Rep Power
    0

    Default

    You don't need an ArrayList to store the child nodes. Just create Node references. You'll also want to make the Node class an inner class (private).

    Java Code:
    private class Node {
       String name;
       int match;
       Node left, right;
    }
    You can add a constructor or assign nodes the following way.

    Java Code:
    Node temp = new Node();
    temp.name = null;
    temp.match = 0;
    temp.right = null;
    temp.left = null;
    Last edited by R-J; 08-17-2011 at 02:51 PM.

  12. #12
    KevinWorkman's Avatar
    KevinWorkman is online now Crazy Cat Lady
    Join Date
    Oct 2010
    Location
    Washington, DC
    Posts
    3,690
    Rep Power
    8

    Default

    Quote Originally Posted by Nacao View Post
    The thing is that I don't know how to save the children nodes of a node using references.
    How could I represent that? Would I be able to access the rest of the children nodes via the father node?
    Yes you do. Anytime you store an Object "in" a variable, you're using a reference. Anytime you store something in an ArraList, you're using a reference. Array, reference. Passing into a method? You got it, reference. To access the children nodes, just use a getter function.

    Quote Originally Posted by Nacao View Post
    On each node I need a name for it, a boolean to explain if the node passed the algorithm check (the data to be manipulated by the algorithm will be the name of the node) and a structure to store the children node. (That's why I used an ArrayList).
    That's what I have done to represent that:

    Java Code:
    public class Node {
        
        String name;
        //Name of the node.
        int match;
        //Attribute match: 1:CONSISTENT MATCH, -1:NOT CONSISTENT MATCH, 0:UNKNOWN.
        ArrayList <Node> children;
        //List of children nodes.
        }
    That seems completely reasonable. I thought you were talking about storing every node in a single ArrayList, which doesn't make a ton of sense. Storing each node's children in its own ArrayList seems fine.

    Quote Originally Posted by Nacao View Post
    Any idea of a more efficient way to store the children nodes?
    What do you mean "more efficient"? What is inefficient about doing it that way? You seem to keep imagining problems that haven't actually happened yet. What happened when you just tried it?
    How to Ask Questions the Smart Way
    Static Void Games - Play indie games, learn from game tutorials and source code, upload your own games!

  13. #13
    KevinWorkman's Avatar
    KevinWorkman is online now Crazy Cat Lady
    Join Date
    Oct 2010
    Location
    Washington, DC
    Posts
    3,690
    Rep Power
    8

    Default

    Quote Originally Posted by R-J View Post
    You don't need an ArrayList to store the child nodes. Just create Node references. You'll also want to make the Node class an inner class (private).

    Java Code:
    private class Node {
       String name;
       int match;
       Node left, right;
    }
    You can add a constructor or assign nodes the following way.

    Java Code:
    Node temp = new Node();
    temp.name = null;
    temp.match = 0;
    temp.right = null;
    temp.left = null;
    You're assuming he wants a binary tree. He doesn't. Read the post again.
    How to Ask Questions the Smart Way
    Static Void Games - Play indie games, learn from game tutorials and source code, upload your own games!

  14. #14
    DarrylBurke's Avatar
    DarrylBurke is offline Member
    Join Date
    Sep 2008
    Location
    Madgaon, Goa, India
    Posts
    11,189
    Rep Power
    19

    Default

    Looks to me like someone's trying to reinvent DefaultTreeModel.

    Just because it's usually associated with a visual representation doesn't mean it has to.

    db

  15. #15
    Nacao is offline Member
    Join Date
    Aug 2011
    Posts
    9
    Rep Power
    0

    Default

    Kevin is right, right now I am not interested in binary trees.

    Well, I didn't know about class DefaultTreeModel. I will take a look at it and TreeNode class.
    I guess I will be able to make operations and take advantage of the tree structure without having to represent it graphically, right?

    At first glance I discarded JTree because I thought it was only used to graphically represent already structured data.

  16. #16
    Nacao is offline Member
    Join Date
    Aug 2011
    Posts
    9
    Rep Power
    0

    Default

    These days I've been playing with DefaultTreeModel and DefaultMutableTreeNode classes.
    What I really want to do is to combine 2 arrays to make a tree that looks like this:
    Array1: [O1, O2, O3, O4, O5]; Array2: [O1', O2', O3', O4', O5'];

    Picture of the final tree:
    ImageShack® - Online Photo and Video Hosting

    The problem I have is that once I define the tree nodes:
    Java Code:
    DefaultMutableTreeNode O1_O2' = new DefaultMutableTreeNode("O1_O2'");
    DefaultMutableTreeNode O2_O3' = new DefaultMutableTreeNode("O2_O3'");
     //I changed the names in this code so that they match with the picture. I know the  " ' " can carry problems when used with names.
    And I arrange them:
    Java Code:
    treeModel.insertNodeInto(O2_O3', O1_O2', 0);
    It only allows me to place the nodes in 1 position of the tree. But in my tree I need several nodes with the same name.

    Any idea?

    Thanks for your help!

  17. #17
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    12,999
    Blog Entries
    7
    Rep Power
    19

    Default

    If you want/have to implement the Node structure yourself, maybe the following definition can help you:

    Java Code:
    public class Node<T> {
       private T data;
       Node<T> leftChild;
       Node<T> sibling;
       Node<T> parent;
       ...
    }
    Each node has a parent node (no further explanation here) and a pointer/reference to its leftmost child node. There also is a reference/pointer to its sibling on the right. A bit of fiddling in the insertion and delete methods will do the rest.

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  18. #18
    DarrylBurke's Avatar
    DarrylBurke is offline Member
    Join Date
    Sep 2008
    Location
    Madgaon, Goa, India
    Posts
    11,189
    Rep Power
    19

    Default

    It only allows me to place the nodes in 1 position of the tree. But in my tree I need several nodes with the same name.
    You've been talking about a tree. In a tree, each node has only one parent.

    Now you seem to be talking about some other data structure in which a node can have more than one parent. That's something else entirely. A Graph comes to mind (but I've never used the structure, so I may be totally wrong).

    db

  19. #19
    Nacao is offline Member
    Join Date
    Aug 2011
    Posts
    9
    Rep Power
    0

    Default

    Ok, so. What I have finally done is to evaluate a node before representing it in my tree.
    If the evaluation is "true" I will represent it in the tree and if it doesn't, I will not represent it. This also accomplishes the prune criteria because if a node doesn't meet the requirements, its children will neither.

    My goal is to obtain the depth of the longest way from the root to a leaf.

    The "problem" now is that I will have to use a recursive method to do this. This is an approach of what I have got so far (it's some kind of a backtracking with a prune criteria):

    Java Code:
    public class Tree {
    
    
        int BuildTree(String[][] matrix, DefaultTreeModel previous_tree){
        
        int max_found_depth = 0;
    
        //matrix is just a string matrix that indicates what the names of the nodes should be.
        /**previous_tree is a tree which only indicates the path from the root to the current node
     (I need it for the algorithm). The names of the nodes are enough for the algorithm to work.**/
        
        if (node passed the criteria) then
           insert_node_in(previous_tree);
    
           if (new_depth>max_found_depth) max_found_depth = new_depth;
           BuildTree(String[][] matrix, DefaultTreeModel previous_tree(first_children));
    
        else 
    
           BuildTree(String[][] matrix, DefaultTreeModel previous_tree(sibling_node));
    
        return max_found_depth;
    
        }
            
        
    }

    Do you see any immediate error?

    I wanted to know if there is anything with this recursive method structure that is wrong before starting to code it. I would be very thankful if you could help me.

Similar Threads

  1. Tree Structure
    By chiku in forum New To Java
    Replies: 2
    Last Post: 01-27-2011, 08:31 PM
  2. Tree structure using JAVA
    By trill in forum Advanced Java
    Replies: 2
    Last Post: 05-27-2010, 11:02 AM
  3. standart tree structure?
    By willemien in forum New To Java
    Replies: 3
    Last Post: 05-06-2010, 07:56 PM
  4. how can i do crossover in this tree structure?
    By player123 in forum Advanced Java
    Replies: 2
    Last Post: 02-11-2009, 06:49 PM
  5. Printing Tree Structure using Swings
    By pradeep1_mca@yahoo.com in forum AWT / Swing
    Replies: 5
    Last Post: 08-30-2008, 01:54 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •