Solved

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

Posted on 2016-10-24
6
45 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 7

Expert Comment

by:James Bilous
Comment Utility
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
Comment Utility
Yes, indeed there is conceptual simularity with deep-first search. However, does I handle the bracket in my case ?
0
 
LVL 7

Accepted Solution

by:
James Bilous earned 500 total points
Comment Utility
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
Why You Should Analyze Threat Actor TTPs

After years of analyzing threat actor behavior, it’s become clear that at any given time there are specific tactics, techniques, and procedures (TTPs) that are particularly prevalent. By analyzing and understanding these TTPs, you can dramatically enhance your security program.

 

Author Comment

by:SunnyX
Comment Utility
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 7

Expert Comment

by:James Bilous
Comment Utility
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
Comment Utility
thx
0

Featured Post

Better Security Awareness With Threat Intelligence

See how one of the leading financial services organizations uses Recorded Future as part of a holistic threat intelligence program to promote security awareness and proactively and efficiently identify threats.

Join & Write a Comment

Suggested Solutions

By the end of 1980s, object oriented programming using languages like C++, Simula69 and ObjectPascal gained momentum. It looked like programmers finally found the perfect language. C++ successfully combined the object oriented principles of Simula w…
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…
Viewers will learn about the different types of variables in Java and how to declare them. Decide the type of variable desired: Put the keyword corresponding to the type of variable in front of the variable name: Use the equal sign to assign a v…
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:

763 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

6 Experts available now in Live!

Get 1:1 Help Now