• Post Reply Bookmark Topic Watch Topic
  • New Topic

Help me out to devise an algorithm for this  RSS feed

 
shesh anand
Greenhorn
Posts: 29
  • Mark post as helpful
  • send pies
  • 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 !!!
 
Ulf Dittmer
Rancher
Posts: 42972
73
  • Mark post as helpful
  • send pies
  • 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
  • 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 ]
 
Henry Wong
author
Sheriff
Posts: 23295
125
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • 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
 
Bob Good
Ranch Hand
Posts: 86
  • Mark post as helpful
  • send pies
  • 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
  • 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: 42972
73
  • Mark post as helpful
  • send pies
  • 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
  • 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
  • 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
  • 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 !!!
 
It is sorta covered in the JavaRanch Style Guide.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!