Binary Tree
I am trying to rebuild a tree from its preorder traversal
(A (B (C) ()) (E )) where each (X) is a node
I have this (A (B (C) ()) (E )) as a string.
I was thinking of implementing this with a Stack but It looks like it is hard process.
the other approach is to access each character with the charat() and build from their the node in this scenario I don't know if I have to use recursive methods or have to go back and forth from child to parent nodes.
Any suggestions
Thanks
# 1
Since literally 2 days ago i became interested in binary trees, im gonna help you. I like the idea of having the data stored as a parenthetical string -similar to LISP. So heres my suggestion...
Have a parser function keep track of open/close parens. When the first parens is open it makes the node 'A'. Then when the next set of parens are found it generate the subnodes 'B' 'C', or whatever based on format.
Ok, that didnt really help... So heres my formatting concept which is just about the ame as yours...
A(B(D) C(E F))
this should create:
...........A............
........./.....\..........
......B.......C.......
.......|....../....\......
......D...E.....F....
So an easy implementation would be based on some sort of Recursive parens checking function. 'A' is seen first, then in 'A's parens are B and C. B is detected first with its subset (and call to the recursive function). Sequence A->B->D will be generated first. The C is found as a subnode of 'A', then calls the recursive function again and finds E and F. forming: A->C->E then A->C->F.
Ok thats alot of talk, but give that a shot. Note: convert the string to a chararray first so it you can find the parens easily.
note incase your wondering: parens = parenthesis.
# 2
THanks
OK, here is what I did .
Build generic BinTree with Data as charcter and left and right tree
and each tree is built recursively .It seem to me logically done
public BinTree(char inData,BinTree A,BinTree B)
{ root = new BTNode(inData,A.root,B.root); }
}
int i=0;
int j=i+2;
public BinTree buildTree(String in){
if ((in.charAt(i)=='(')&& (in.charAt(j)==')'))
{
BinTree A = new BinTree(in.charAt(i+1),buildTree(in.substring(j)),buildTree(in.substring(j+3)));
return A;
else
buildTree(in.substring(i+2));
}
}
But I dont think this is going to work for the else part
?
# 3
> ...> But I dont think this is going to work for the else> part > ?If you're not sure whether something works or not, you should try it.
# 4
Thanks for the reply
I have tried it.
And it error that i have to initialize the left and right nodes.
It give exception error at the line at BinTree.<init>
{ root = new BTNode(inData,A.root,B.root); }
But how I am going to intialize the nodes if I am building the tree?
# 5
> Thanks for the reply
>
> I have tried it.
> And it error that i have to initialize the left and
> right nodes.
> It give exception error at the line at
> BinTree.<init>
> { root = new BTNode(inData,A.root,B.root); }
That doesn't tell me much. I don't know what methods/constructors this BTNode class has.
> But how I am going to intialize the nodes if I am
> building the tree?
Can you explain your algorithm in words to me? Because it's not clear to me what your algorithm is supposed to do.
# 6
Here is my code
public class BinTree {
// binary tree single node class
// holding a char type
private class BTNode {
private char data;// data
private BTNode left; // left child
private BTNode right; // right child
// precondition: none
// postcondition: a single node is created with
// inData content and links to L and R
public BTNode(char inData,BTNode L,BTNode R)
{ data = inData;
left = L;
right = R;
}
}
public BTNode root; // root of the tree
// postcondition: empty BinTree is created.
public BinTree() {root = null;}
// postcondition: a single node tree is created.
public BinTree(char inData)
{ root = new BTNode(inData,null,null);}
// postcondition: a new binary tree is created
// with the specified root content and with the
// links to the given left and right subtrees
public BinTree(char inData,BinTree A,BinTree B)
{ root = new BTNode(inData,A.root,B.root); }
int i=0;
int j=i+2;
public BinTree buildTree(String in){
if ((in.charAt(i)=='(')&& (in.charAt(j)==')'))
{
BinTree A = new BinTree(in.charAt(i+1),buildTree(in.substring(j)),buildTree(in.substring(j+3)));
return A;
}
return null;
}
}
What I am trying to do is I read each character from the String like (A(B(C)(D))(E(F)())) that is a preorder traversaland build that tree .
In my algorithm I am looking for '( ' and ' )' which mean a new node is found and the same process for the left and right for that node is done by recursive call.
I hope I made it clearer
Thanks for your help
# 7
> ...
> What I am trying to do is I read each character from
> the String like (A(B(C)(D))(E(F)())) that is a
> preorder traversaland build that tree .
> In my algorithm I am looking for '( ' and ' )' which
> mean a new node is found and the same process for
> the left and right for that node is done by recursive
> call.
> I hope I made it clearer
I don't see how your algorithm is ever going to work. Have you tried doing it on a piece of paper with your example tree? Try stepping through your algorithm on a piece of paper and write down what gets executed.
But what is the problem at the moment? If you get compiler errors, then copy and paste those here as well.
PS next time when posting code, please use code tags:
http://forum.java.sun.com/help.jspa?sec=formatting
# 8
Here's some pseudo code of an algorithm that should work:
public class BinTree {
public BTNode root;
public BinTree(String tree) {
root = null;
tree = tree.replaceAll("\\s+", ""); // remove all white spaces
parseTree(tree, root); // build the tree
}
parseTree(String 'tree', BTNode 'parent') {
BTNode 'node' <- the first node in this 'tree'
IF 'root' is null
'root' <- 'node'
END IF
String 'lTree' <- the left subtree of 'parent'
String 'rTree' <- the right subtree of 'parent'
IF the length of 'lTree' is more than 3
parseTree('lTree', 'node.left')
END IF
IF the length of 'rTree' is more than 3
parseTree('rTree', 'node.right')
END IF
}
// ... your methods ...
public static void main(String[] args) {
new BinTree("(A (B (C) ()) (E ))");
}
}
Note that the proposed algorithm only works for valid tree-Strings!
# 9
thanksyou are saying if the left or the right is more than tree characters than we have to make a subtree for it?Can you clear this for me please.
# 10
> thanks
> you are saying if the left or the right is more than
> tree characters than we have to make a subtree for
> it?
>
> Can you clear this for me please.
Sorry, I forgot to assign the left and right nodes in my pseudo code. And there is also no need for the BTNode parameter in the parseTree(...) method: only the String is sufficient.
Here is an update including your example tree: (A (B (C) ()) (E ))
// Call 1 | Call 2 |
// -++
parseTree('tree') {// 'tree' = "(A(B(C)())(E))"| 'tree' = "(B(C)())" |
//| |
BTNode 'node' <- the first node in this 'tree'// 'node' = A| 'node' = B |
//| |
IF 'root' is null // true| false|
'root' <- 'node'// 'root' = 'node' | -|
END IF //| |
//| |
String 'lTree' <- the left subtree of 'node'// 'lTree' = "(B(C)())"| 'lTree' = "(C)"|
String 'rTree' <- the right subtree of 'node'// 'rTree' = "(E)" | 'rTree' = "()"|
//| |
'node.left' = the first node in this 'llTree'// A.left = B| B.left = C |
'node.right' = the first node in this 'rTree'// A.right = E| B.right = null|
//| |
IF the length of 'lTree' is more than 3// this is true for "(B(C)())" | false|
parseTree('lTree')// call parseTree("(B(C)())") | -|
END IF //| |
//| |
IF the length of 'rTree' is more than 3// this is false for "(E)"| false|
parseTree('rTree')// -| -|
END IF //| |
}//| |
# 11
Here is my code which will assign any size tree. (not only branches of two)
The formatting is annoying, but computers are only as smart as you make them, and I made it pretty dumb (oops).
//class starter.java
public class starter
{
static java.util.List nodes = new java.util.ArrayList();
public static void main ( String args[] )
{
String data = "Ariel(Bob(Morgan(Jeremy()Alexis())Susan(Ruth()))Thomas(Jill()Cara()))";
findNode( data, null );
//
drawTree( (Node)nodes.get(0),0 );
}
public static void drawTree( Node son, int indent )
{
for ( int i = 0; i<indent; i++ )
System.out.print(" ");
System.out.println( "- " + son.getName() );
if ( son.Sons()==0 )
return;
for ( Object n : son.getSons() )
{
Node nd = (Node)n;
drawTree(nd,indent+1);
}
}
public static void findNode( String d, Node parent )
{
char array[] = d.toCharArray();
int parens = 0;
int start_idx = 0;
int end_idx = 0;
int last_idx = 0;
boolean no_parens = true;
//
for ( int i = 0; i><array.length; i++ )
{
if ( array[i]=='(' )
{
no_parens=false;
if (parens==0)
start_idx=i+1;
parens++;
}
else if ( array[i]==')' )
{
parens--;
if (parens==0)
{
end_idx=i;
//
String name = d.substring(last_idx,start_idx-1);
Node n = new Node(name,parent);
if ( parent!=null )
parent.addSon(n);
nodes.add(n);
last_idx = end_idx+1;
//
findNode( d.substring(start_idx,end_idx), n );
}
}
}
if ( no_parens && d.length()!=0 )
{
String parts[] = d.split(" ");
for ( int i=0; i><parts.length; i++ )
{
Node n = new Node(parts[i],parent);
if ( parent!=null )
parent.addSon(n);
nodes.add(n);
}
}
}
}
// class Node.java
public class Node
{
public Node( String n, Node f )
{
name = n;
Father = f;
Sons = new java.util.ArrayList();
}
public String getName()
{
return name;
}
public Node getFather()
{
return Father;
}
public void addSon( Node a )
{
Sons.add( a );
}
public java.util.List getSons()
{
return Sons;
}
public Node getSons( int i )
{
return (Node)Sons.get(i);
}
public int Sons()
{
return Sons.size();
}
String name;
Node Father;
java.util.List Sons;
}
I know its not a binary tree, but this may be useful.>
