?
Solved

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

Posted on 2016-10-24
6
Medium Priority
?
204 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 9

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 9

Accepted Solution

by:
James Bilous earned 2000 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
Free Tool: Subnet Calculator

The subnet calculator helps you design networks by taking an IP address and network mask and returning information such as network, broadcast address, and host range.

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

 

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 9

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

The 14th Annual Expert Award Winners

The results are in! Meet the top members of our 2017 Expert Awards. Congratulations to all who qualified!

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

Join & Write a Comment

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…
When there is a disconnect between the intentions of their creator and the recipient, when algorithms go awry, they can have disastrous consequences.
This video teaches viewers about errors in exception handling.
This tutorial explains how to use the VisualVM tool for the Java platform application. This video goes into detail on the Threads, Sampler, and Profiler tabs.

589 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