Solved

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

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

 

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

Free Tool: Path Explorer

An intuitive utility to help find the CSS path to UI elements on a webpage. These paths are used frequently in a variety of front-end development and QA automation tasks.

One of a set of tools we're offering as a way of saying 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

Suggested Solutions

Title # Comments Views Activity
how to add new optional parameter to JSP 1 49
servlet example 11 50
use lov values 2 64
Tagging and Merging on Branch 1 30
Introduction This article is the second of three articles that explain why and how the Experts Exchange QA Team does test automation for our web site. This article covers the basic installation and configuration of the test automation tools used by…
Introduction This article is the last of three articles that explain why and how the Experts Exchange QA Team does test automation for our web site. This article covers our test design approach and then goes through a simple test case example, how …
The viewer will learn how to implement Singleton Design Pattern in Java.
This video teaches viewers about errors in exception handling.

821 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