Learn how to a build a cloud-first strategyRegister Now

x
?
Solved

Binary Tree Preorder Traverse

Posted on 2006-04-02
26
Medium Priority
?
268 Views
Last Modified: 2008-02-01
Hi,

I have the function below:

public void showStructure(AccountNode current, int offset, int step) {
    if ((current == null))
        return;
    showStructure(current.right, offset, step);            
   System.out.println(Integer.toString(++i) + " " + Pad.leftJustify("", offset) + current.accountName);
   showStructure(current.left, offset + step, step);            
}

It is supposed to display items in a tree in preorder traverse. I also want to store the items in an arrayList according to the order displayed.

Can someone please provide some pointers or show me how it can be done?

Thank you.

Regards
0
Comment
Question by:yiyi83
  • 9
  • 8
  • 5
  • +2
25 Comments
 
LVL 86

Expert Comment

by:CEHJ
ID: 16353590
You should recurse left before right
0
 
LVL 86

Expert Comment

by:CEHJ
ID: 16353594
You can add the current node to a List that's an instance variable

if ((current == null))
        return;
nodesVisited.add(current);
0
 
LVL 14

Expert Comment

by:hoomanv
ID: 16353606
pre-order (prefix) traversal

visit(node)
    print node.value
    if node.left  != null then visit(node.left)
    if node.right != null then visit(node.right)
0
Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.

 
LVL 92

Expert Comment

by:objects
ID: 16353607
public void showStructure(AccountNode current, int offset, int step) {
    if ((current == null))
        return;
   System.out.println(Integer.toString(++i) + " " + Pad.leftJustify("", offset) + current.accountName);
    showStructure(current.right, offset, step);          
   showStructure(current.left, offset + step, step);          
}
0
 
LVL 14

Expert Comment

by:hoomanv
ID: 16353609
the one you wrote is in-order (infix) traversal

    if node.left  != null then visit(node.left)
    print node.value
    if node.right != null then visit(node.right)
0
 

Author Comment

by:yiyi83
ID: 16354011
Dear All,

Thanks for the comments. I realize that I been using the wrong tranverse (Thanks to hoomany for highlighting).

How about the below?

private void preorderStore(AccountNode root) {
   if ( root != null ) {  // (Otherwise, there's nothing to print.)
       System.out.println(root.accountName);
       if (root.left != null) {
           preorderStore( root.left );   // Print items in left subtree.
       }
       if (root.right != null) {
           preorderStore( root.right );  // Print items in right subtree.
       }
    }
}

When I tried to store the value, it is looping.

Example:
Account One
Account One
Account Two
Account One
Account Two
Account Two.One

How can I eliminate the looping?

Regards
0
 
LVL 86

Expert Comment

by:CEHJ
ID: 16354048
Please post code where you add nodes
0
 
LVL 92

Expert Comment

by:objects
ID: 16354210
you don't need to check if right/left are null, as you check wheteher root is null already when called
And add the node the same place you print it out
, you can pass the node list as a parameter


private void preorderStore(List nodeList, AccountNode root) {
   if ( root != null ) {  // (Otherwise, there's nothing to print.)
       System.out.println(root.accountName);
       nodeList.add(root.accountName);
       preorderStore( nodeList, root.left );   // Print items in left subtree.
       preorderStore( nodeList, root.right );  // Print items in right subtree.
    }
}
0
 

Author Comment

by:yiyi83
ID: 16354281
The code as below:

private void preorderStore(AccountNode root) {
   if ( root != null ) {  // (Otherwise, there's nothing to print.)
       parentArray.add(root.accountName);
       System.out.println(root.accountName);
       if (root.left != null) {
           preorderStore( root.left );   // Print items in left subtree.
       }
       if (root.right != null) {
           preorderStore( root.right );  // Print items in right subtree.
       }
    }
}

Regards
0
 
LVL 86

Expert Comment

by:CEHJ
ID: 16354312
>>you don't need to check if right/left are null, as you check wheteher root is null already when called

Just because root != null, it doesn't mean root.left and root.right are not null. In fact, not checking is merely wasteful of the stack
0
 
LVL 86

Expert Comment

by:CEHJ
ID: 16354319
>>The code as below:

No, sorry - i should have been more explicit - i meant the code where you add the nodes to the tree in the first place
0
 

Author Comment

by:yiyi83
ID: 16354452
Hi CEHJ,

As below:

private void addAccount(AccountNode current, T accountName, T parentAccount) {
    if (parentAccount == null)
    {
        current = new AccountNode(accountName, null, null);
        current.right = root;
        root = current;
    } else {
         AccountNode parentNode;
         AccountNode temp;
         parentNode = find(parentAccount);
         if (parentNode == null)
          {
      System.out.println("Parent Node does not exist.");
      System.out.println(parentAccount);
          }
         if (parentNode.left == null)
         {
      temp = new AccountNode(accountName, null, null);
      parentNode.left = temp;
         } else {
      temp = new AccountNode(accountName, null, null);
      temp.right = parentNode.left;
      parentNode.left = temp;
         }
      }
}

Does this help?

Regards
0
 
LVL 14

Expert Comment

by:hoomanv
ID: 16354499
what does it mean. what it is supposed to do
current.right = root;
root = current;
where the variable "root" is defined and of what type
0
 
LVL 14

Expert Comment

by:hoomanv
ID: 16354516
i think you are creating a cycle
0
 
LVL 86

Expert Comment

by:CEHJ
ID: 16354571
It may help for debugging if you actually name the root 'Root' for now
0
 

Author Comment

by:yiyi83
ID: 16354582
Hi,

Basically, I am trying to create a tree structure such as below:

Account One
     Account One.One
          Account.One.One
          Account One.Two
     Account One.Two
     Account One.Three
Account Two
    Account Two.One
    Account Two.Two
         Account Two.Two.One
Account Three

When I add account two, it should be the right child of account one and so fro.
When I add account two.one, it should be the left child of account two and so fro.
When I add account two.two, it should be the left child of account two and two.one will be its right child.

Does my code achieve that? From my testing, it seem to do so. I will be glad to send my code out for more comments.

Please let me know. Thank you.

Regards
0
 
LVL 86

Expert Comment

by:CEHJ
ID: 16354622
>>new AccountNode(accountName, null, null);

What are the two last parameters to that ctor btw?
0
 

Author Comment

by:yiyi83
ID: 16354662
Hi CEHJ,

It is the left and right node.

As below:

public AccountNode(T newAccountName, AccountNode left, AccountNode right) {
    accountName = newAccountName;
    this.left = left;
    this.right = right;
}

Regards
0
 
LVL 86

Expert Comment

by:CEHJ
ID: 16354676
Another question: what kind of ordering is being used and how does it work?
0
 

Author Comment

by:yiyi83
ID: 16354690
Hi,

I am not sure of what u mean. If you are refering to how a new node is added, it is as below:

the user will indicate the parent account and input the new account name.
I will find the parent node and insert the new account node as the first child.

Regards
0
 
LVL 14

Expert Comment

by:hoomanv
ID: 16354693
another pitfall (seperate from your program logic) that can cause a NullPointerException

         if (parentNode == null)
          {
 ////////////////
          }
         if (parentNode.left == null) // this should be "else if" other wise after getting out of first if an EXC will be thrown
         {
//////////////////
         }
         else {
///////////////
         }
0
 
LVL 86

Expert Comment

by:CEHJ
ID: 16354738
>>I am not sure of what u mean.

Some binary trees are ordered, some are not. Is one node 'greater' than another in your case?
0
 

Author Comment

by:yiyi83
ID: 16354760
Hi CEHJ,

My binary tree is based on user indication.

For example:

I have 3 top nodes, N1, N2, N3. Right child of N1 is N2. Right child of N2 is N3.

if user indicate, parent = N1
new node name = N1.1

The node, N1.1 will be the left child of N1.

Is that clearer?
0
 

Author Comment

by:yiyi83
ID: 16393778
Hi All,

I resolved my problem by initiatising the array at the start of the call.

Thank you all for helping.

Regards
0
 

Accepted Solution

by:
GranMod earned 0 total points
ID: 16429285
Closed, 100 points refunded.
GranMod
The Experts Exchange
Community Support Moderator of all Ages
0

Featured Post

Free Tool: ZipGrep

ZipGrep is a utility that can list and search zip (.war, .ear, .jar, etc) archives for text patterns, without the need to extract the archive's contents.

One of a set of tools we're offering as a way to say thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

INTRODUCTION Working with files is a moderately common task in Java.  For most projects hard coding the file names, using parameters in configuration files, or using command-line arguments is sufficient.   However, when your application has vi…
Java Flight Recorder and Java Mission Control together create a complete tool chain to continuously collect low level and detailed runtime information enabling after-the-fact incident analysis. Java Flight Recorder is a profiling and event collectio…
This theoretical tutorial explains exceptions, reasons for exceptions, different categories of exception and exception hierarchy.
Viewers will learn how to properly install Eclipse with the necessary JDK, and will take a look at an introductory Java program. Download Eclipse installation zip file: Extract files from zip file: Download and install JDK 8: Open Eclipse and …
Suggested Courses
Course of the Month21 days, 5 hours left to enroll

810 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question