2

Today i was told to create tree data structure with the below class,

public class Node(){
private string lable;
private List<Node> children;
}

After started to create the tree, i struck at very first.

It contains Node inside a node. I am totally confused. Well, tree maybe very familiar to you. You may think Whats this! Its clear. How you getting confused something like that.

For me, this the first time i am trying to create a tree in java. To be honest, i only used setters and getters inside a class in java. With these methods, I cannot think of inserting new nodes after the first level.

I have seen some examples in google and many in stackoverflow. But for a beginner(in tree) like me they looks incomplete. May be they may thought, the OP can continue with that.

If anyone explain me its concept and how to add more children, with any generic example i would be appreciative.

Update:

It may look weired to you, but this is how i started at the beginning.

Node node = new Node();
String label = "Bikes";
ArrayList<Node> children = new ArrayList<Node>();

    Node childNode = new Node();
    childNode.setLabel("Yamaha");
    children.add(childNode);

    childNode = new Node();
    childNode.setLabel("Suzuki");
    children.add(childNode);

    childNode = new Node();
    childNode.setLabel("Honda");
    children.add(childNode);

    node.setLabel(label);
    node.setChildren(children);

After that, like i told i cannot think for next level. After doing some searches i have found that they are having a method addChild()

Then i created mine, 

    public void addChildren(Node node){
    children.add(node);
}

I continued like this,

        ArrayList<Node> children = new ArrayList<Node>();

    node.setLabel(label);
    node.addChildren(node);

Now again i strucked here. Again i cannot think of adding more branches to the root node. i hope this makes some what clear.

Improve this question
10
  • 1
    Have you bothered to Google for some examples? Commented Feb 18, 2011 at 18:18
  • 1
    Sounds like a homework question... Commented Feb 18, 2011 at 18:20
  • Are familiar with the List interface? Commented Feb 18, 2011 at 18:21
  • 2
    @DVK I have seen some examples in google and many in stackoverflow. But for a beginner(in tree) like me they looks incomplete... Commented Feb 18, 2011 at 18:22
  • 2
    @Jhurtado - then he should have posted specific example that he doesn't get and asked what was unclear about it. Commented Feb 18, 2011 at 18:22

6 Answers 6

Reset to default
3

First drop the () in the class name:

Should be: 

public class Node { 
....

edit

I press sumbit before time. Here's the complete answer ( hint: you can undo the downvote now :P )

They are called trees , because one branch may either have leafs or other branches.

That's why a node may have other nodes inside.

When a node doesn't have children, then in a leaf. When it does is a branch.

So, it would be something like this:

import java.util.*;
// This is your existing code:
class Node { 
    private String label;
    private List<Node> children = new ArrayList<Node>();

    // Here's how you would build one with that strucure
    public static void main( String ... args ) { 

        Node one = new Node();
        one.label = "1";

        Node two = new Node();
        two.label = "2";

        Node root = new Node();
        root.label = "plus";
        root.children.add( one );
        root.children.add( two );

        print( root );
    }

    // Here's how you'll print the values
    static void print( Node node ) { 

         System.out.println( node.label );

         for( Node child : node.children ) { 
            // if child is a branch 
            if( child.children.size() > 0 ) { 
                // print the branch ( recursively ) 
                print( child );
             } else { 
                // is a leaf, just print the label.
                System.out.println( "-- ["+child.label+"]" );
             }
          }
     }
}

That is a root node ( "plus" ) has two childs ( "1" and "2" ) those nodes in turn may have other nodes ( that's not the case here ) like a tree does.

I hope this help you.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Let me know if this is clear enough as for ( levels ) goes. You can also try to model an organization chart ( as deep as: ) General -> Colonel -> Captain -> Sargeant -> Private
2

Its all about composite pattern : wikipedia definition.
Try to understand it first.I think the Java syntax is not a problem.
I hope this help you.

Improve this answer

Comments

1

Your original question is fairly vague but to answer your ? of node inside on node. If you visualize it, A tree consists of branches(nodes), and each branch can have child branches, and so on.

Good explanation here.

Improve this answer

Comments

1

The tree starts with a parent node. Each node has a label and can have 0 to many children. The reason you have a list of nodes is because those are the child nodes of that given node.

Improve this answer

Comments

1

I think the bigger issue here is the way you are thinking about how to write a function to solve a task on a tree. For lists, it is straight forward. You loop over the items of the list and perform some action using the current item of the list.

However, since trees are a different data structure, you need a different method to perform similar steps. The easiest way to work with a tree is to write a recursive method. This is a method that at some point calls itself in order to do more work.

recursiveFunction(Node n) {
  do work for current node

  for(Node child : children) {
    recursiveFunction(child);
  }
}

It may take a little thinking to see what work needs to be done on the current node and if there are some special cases based on it's values, but the structure will look similar.

Improve this answer

Comments

0

In OscarRYZ's answer In the recursive method print(Node), the print(Node) method is called in itself:

if( child.children.size() > 0 ) {
// print the branch ( recursively )
print( child );
}else {
// is a leaf, just print the label.
System.out.println( "-- ["+child.label+"]" );
}

this print(Node) method will be called recursively as long as the node is a branch, and when it gets to a leaf, it will just print the leaf's label with

System.out.println( "-- ["+child.label+"]" );
and go back to its branch.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.