Solved

Java. Convert method from recursion based to iteration based ( loop based )

Posted on 2016-10-24
6
77 Views
Last Modified: 2016-10-31
 public void toString(NodeImpl<E> node) {
        if (node == root) {
            treeToString.append(root.key + "(");
        }
        if (node.left == nil && node.right == nil) {
            if (node == node.parent.right) {
            }
        }
        if (node.left != nil) {
            if (node.left.left != nil || node.left.right != nil) {
                treeToString.append(node.left.key + "(");
                toString(node.left);
            } else {
                if (node.right != nil) {
                    treeToString.append(node.left.key);
                } else {
                    treeToString.append(node.left.key + ")");
                }
                toString(node.left);
            }
        }
        if (node.right != nil) {
            if (node.right.left != nil || node.right.right != nil) {
                if (node.left != nil) {
                    treeToString.append("," + node.right.key + "(");
                } else {
                    treeToString.append(node.right.key + "(");
                }
                toString(node.right);
            } else {
                if (node.left != nil) {
                    treeToString.append("," + node.right.key);
                } else {
                    treeToString.append(node.right.key);
                }
                toString(node.right);
            }
            treeToString.append(")");
        }
    }

Open in new window


I need to implement toString  to represent a tree like (also each level can be a separate line):
    (n1(n11(n111, n112), n12(n121, n122)))
that corresponds to tree hierarchy:
                    n1
      n11                 n12
n111 n112      n121   n122

In addition, the method should be based on the loop. I made the method which is work correctly based on recurion. Could help me to convert this method to loop based.
Thx in advanced dear experts !
0
Comment
Question by:SunnyX
  • 3
  • 3
6 Comments
 
LVL 8

Expert Comment

by:James Bilous
ID: 41857208
This is essentially a depth first search that prints as it traverses the graph. Heres some pseudo code for an iterative approach: http://www.cs.toronto.edu/~heap/270F02/node36.html

It'd be easier to start from there than to try and chop up and repurpose your recursive code IMO.
0
 

Author Comment

by:SunnyX
ID: 41858666
Yes, indeed there is conceptual simularity with deep-first search. However, does I handle the bracket in my case ?
0
 
LVL 8

Accepted Solution

by:
James Bilous earned 500 total points
ID: 41858722
If we think about the bracket placement, it becomes apparent that they occur whenever a child node is entered or left.

This would correspond to the following points in the pseudo-code:

 DFS(G,v)   ( v is the vertex where the search starts )
         Stack S := {};   ( start with an empty stack )
         for each vertex u, set visited[u] := false;
         push S, v;
         while (S is not empty) do
            u := pop S;
            if (not visited[u]) then
               // Print '('
               // Print node name
               visited[u] := true;
               for each unvisited neighbour w of u
                  push S, w;
               // Print ')'
            end if
         end while
      END DFS()

Open in new window

0
Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

 

Author Comment

by:SunnyX
ID: 41858751
Okey, this is implementation of the deep-first search in Java which is work fine for sure.
private List<Node<E>> breadthFirst(Node<E> n) {
        Queue<Node<E>> queue = new LinkedList();
        LinkedList<Node<E>> output = new LinkedList();
        if (n == null) {
            return output;
        }
        queue.add(n);
        while (!queue.isEmpty()) {
            Node<E> node = queue.remove();
            output.add(node);
            if (left(node) != null) queue.add(left(node));
            if (right(node) != null) queue.add(right(node));
        }
        return output;
    }

Open in new window


Could you please tell me how can change the code to handle brackets ?
0
 
LVL 8

Expert Comment

by:James Bilous
ID: 41858763
What you posted is breadth first search not depth first since it uses a queue. You need to use a stack instead for DFS.
0
 

Author Closing Comment

by:SunnyX
ID: 41867012
thx
0

Featured Post

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

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

Suggested Solutions

Title # Comments Views Activity
Unable to start eclipse ? 17 133
advertisement module in core php 4 147
Where to store the queries for modification of table 4 55
eclipse apache tomcat admin console 52 73
Iteration: Iteration is repetition of a process. A student who goes to school repeats the process of going to school everyday until graduation. We go to grocery store at least once or twice a month to buy products. We repeat this process every mont…
Basic understanding on "OO- Object Orientation" is needed for designing a logical solution to solve a problem. Basic OOAD is a prerequisite for a coder to ensure that they follow the basic design of OO. This would help developers to understand the b…
Video by: Michael
Viewers learn about how to reduce the potential repetitiveness of coding in main by developing methods to perform specific tasks for their program. Additionally, objects are introduced for the purpose of learning how to call methods in Java. Define …
Viewers will learn about if statements in Java and their use The if statement: The condition required to create an if statement: Variations of if statements: An example using if statements:

867 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

Need Help in Real-Time?

Connect with top rated Experts

22 Experts available now in Live!

Get 1:1 Help Now