Tree data structure

[Nacao]

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!

[KevinWorkman]

JTree is not a data structure, it's a GUI component. You might want to look at TreeSet or TreeMap instead.

[Nacao]

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.

[KevinWorkman]

So what's your question then?

[Nacao]

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

[Nacao]

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?

[KevinWorkman]

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?

[Nacao]

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

[KevinWorkman]

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.

[Nacao]

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:

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?

[R-J]

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).

private class Node {
   String name;
   int match;
   Node left, right;
}

You can add a constructor or assign nodes the following way.

Node temp = new Node();
temp.name = null;
temp.match = 0;
temp.right = null;
temp.left = null;

[KevinWorkman]

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.

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:

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.

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?

[KevinWorkman]

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).

private class Node {
   String name;
   int match;
   Node left, right;
}

You can add a constructor or assign nodes the following way.

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.

[DarrylBurke]

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

[Nacao]

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.

[Nacao]

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:

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:

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!

[JosAH]

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

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

[DarrylBurke]

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

[Nacao]

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):

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.