• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Help me out to devise an algorithm for this

 
Greenhorn
Posts: 29
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
In the following string:

f b, b c, a c, e b, d a, g a

two letters are tuples with each tuple separated by commas. The first letter in each tuple is a node and the second letter is the parent of the node. Please write a function that takes the string as input, and outputs a representation of the tree that the nodes form

that too graphically but leave that graphical part for now !!!
 
Rancher
Posts: 43081
77
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I would approach it in two steps. First, create an in-memory tree data structures that is filled with the data from that string. Then, consider how to print (or display) that tree structure.

In this case, it looks as if each parent has no more than two children. If that is a valid assumption, you could start with a class like this:

You'd need setter and getter methods for the parent, children and the letter as well.
[ March 18, 2008: Message edited by: Ulf Dittmer ]
 
shesh anand
Greenhorn
Posts: 29
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
if you could give ...some more elaborated code snippet that would be of great help...it's an urgent issue ....
[ March 18, 2008: Message edited by: shesh anand ]
 
author
Posts: 23951
142
jQuery Eclipse IDE Firefox Browser VI Editor C++ Chrome Java Linux Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Originally posted by shesh anand:
if you could give ...some more elaborated code snippet that would be of great help...it's an urgent issue ....



Well, what have you done so far?

Henry
 
Ranch Hand
Posts: 86
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Here is something to start you thinking...you are looking for an algorithm, not java code.

Some Questions first:
1) Can a node can have more than one parent? (or why not)
2) Can a node can have more than one child? (yes from your sample)
3) Can the input list of tuples create more than one tree? (or why not)

I think you want something of this fashion, however this is a very simplified algorithm to get you started:

for each tuple in string (child, parent)
search for child in tree(s)
if child found in tree, add parent as parent of tree-child

search for parentin tree
if parent found in tree, add child as child of tree-parent

if neither child or parent found...start new tree

try to join sub trees together (optional...depends on requirements)

I hope this gives you some ideas.
 
shesh anand
Greenhorn
Posts: 29
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
O !! Friend send in some java code that suits to requirement ...if you could do that ... i mean i'll be grrrrrrrrrrrraaaaaaateful to you no i really mean it...leave that jargon alone !!!
 
Ulf Dittmer
Rancher
Posts: 43081
77
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
If you don't want to spend time thinking about the problem and trying understand it, you will be hard pressed to arrive at a solution. Again, we'll be happy to help you, but not if you don't ShowSomeEffort. Plus, this is NotACodeMill.
 
Bob Good
Ranch Hand
Posts: 86
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I agree....you did not even answer my questions, sheesh!
 
shesh anand
Greenhorn
Posts: 29
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator


I know this is not a <b>CODEMILL</b>...i have tried this but this only gives me right successor to the depth if i feed this a String.. "fb bc ac"...the complete sequence is..."fb bc ac eb da ga"...currently i am getting result for the "fb bc ac"...sequence of string and that too not very correctly...only getting right hand side of the last child !!!

[ UD: added CODE tags ]
[ March 19, 2008: Message edited by: Ulf Dittmer ]
 
shesh anand
Greenhorn
Posts: 29
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
import java.awt.*;
import javax.swing.*;
import javax.swing.event.*;
import javax.swing.tree.*;
import java.util.*;
/*
<applet code = "JTreeDemo2" width=4
00 height=200>
</applet>
*/
public class JTreeDemo2 extends JApplet
{
JTree tree;
JLabel jlabel;


public void init()
{
try
{
SwingUtilities.invokeAndWait(new Runnable()
{
public void run()
{
makeGUI();
}
}
);
}
catch (Exception e)
{
System.out.println("can't create coz of" + e);
}
}
private void makeGUI()

{

DefaultMutableTreeNode grandparent =null;
Scanner sc=new Scanner(System.in);
System.out.println ("Enter a string ");
String s=sc.nextLine();
int l;
int i;
DefaultMutableTreeNode parent1 = null;
char a[]=new char[s.length()/2];
for (i=1,l=0;i<s.length();i+=2,l++)
{
a[l]=s.charAt(i);
System.out.println ("In if "+a[l]);

}
char p=a[0];
char p1=p;

for(i=0;i<a.length;i++)
{
if(p==a[i])
{
p=a[i];


}
if(p!=a[i])
{
p1=a[i];


}


grandparent = new DefaultMutableTreeNode(p1);
parent1 = new DefaultMutableTreeNode(p);
grandparent.add(parent1);


System.out.println ("***p-->"+p) ;
System.out.println ("***p1--->"+p1) ;
}

char b[]=new char[s.length()/2];
char child ;
char ch,ch1;
for(i=0,l=0;i<b.length;i+=2,l++)
{
b[l]=s.charAt(i);
System.out.println ("b[l] "+b[l]);
for(int j=0;j<=i;j++)
{
if(a[i]==b[j])
{
ch1=b[j];
System.out.println("ch1"+ch1);
}
else
{
ch=b[j];
System.out.println("ch"+ch);
}
}



if(p==b[l])
continue;
else
{
child = b[l];
System.out.println (child);
}




//create subtree of a

DefaultMutableTreeNode child11 = new DefaultMutableTreeNode(child);
parent1.add(child11);
}





tree = new JTree(grandparent);

//addtree to a scrollpane
JScrollPane jsp = new JScrollPane(tree);
add(jsp);//add scrollpane to the contentpane
jlabel = new JLabel();
add(jlabel,BorderLayout.SOUTH);

tree.addTreeSelectionListener(new TreeSelectionListener() {
public void valueChanged(TreeSelectionEvent tse){
jlabel.setText("Selection is " + tse.getPath());
}

});
}
}




I know this is not a <b>CODEMILL</b>...i have tried this but this only gives me right successor to the depth if i feed this a String.. "fb bc ac"...the complete sequence is..."fb bc ac eb da ga"...currently i am getting result for the "fb bc ac"...sequence of string and that too not very correctly...only getting right hand side of the last child !!!
 
Consider Paul's rocket mass heater.
reply
    Bookmark Topic Watch Topic
  • New Topic