Win a copy of Mesos in Action this week in the Cloud/Virtualizaton forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

how do i solve this recorsive function question??

 
johny doe
Ranch Hand
Posts: 78
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
there is abinary tree for which in every vertex there are no more objects
than son of a son.
the given classes are class of the tree and class of a vertex

wright the only the code which is needed for making searches on the tree

this is the question
whithout any given code
i dont know how to start doing this???
how do i solve this question??
 
Bert Bates
author
Sheriff
Posts: 8898
5
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
This looks like a homework question, we're happy to help, but you need to show some effort on your side...so what have you got so far? what's confusing so far?
[ December 18, 2007: Message edited by: Bert Bates ]
 
johny doe
Ranch Hand
Posts: 78
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
i am confused about
how do i make a serched in a binary tree

how do i build a recursive code about a tree
i cant imagine this.
 
fred rosenberger
lowercase baba
Bartender
Posts: 12126
30
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
first, do you know what a binary tree is? Do you know what is meant by 'search a binary tree'?

if the answer to both of these is yes, pretend you have a picture of this binary tree in front of you.

Tell me in plain old english how would you, personally, search this tree? No computers, no Java, no programming language. tell me what steps you would take to examine this tree.
 
johny doe
Ranch Hand
Posts: 78
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
i whould check the top one,
if its not there
i whould pick one of the main branches which come out of him

and check if his sons got the value

then i whould pick one of the sons as the top
and search its sons
if i got to the bottom of the tree and i didnt find my value
i whould pick another son as the top and search each of his sons.

even when i go to the sons of sons i need to check every possibility.

i think i need to set a proccess which sets one of the sons
to be the top and search it own sons
and if i didnt get any result the it will switch to other sons

this procces must aply also to the sons of the sons etc..

lots of thoughts dont have any clue how to build it
 
Stan James
(instanceof Sidekick)
Ranch Hand
Posts: 8791
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Quick binary tree description: each node has two children, the left one is smaller, the right one is larger. But the right one or both may be empty, meaning no more children.

To walk a tree in order

1 start at the root
2 go left as far as you can
3 back up to the last place you could have gone right
4 go right
5 repeat from 2

Draw some on paper and try it:

See if you can write a Node class with a value and two references to child nodes, load up some values and walk them in order. Show us your work! That's how we know where you're stuck.
 
fred rosenberger
lowercase baba
Bartender
Posts: 12126
30
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by johny doe:
i whould check the top one,
if its not there
i whould pick one of the main branches which come out of him


Ok. but how do you decide which of the main branches to follow? do you ALWAYS choose the left? (then when do you get to the right branch?) do you do it randomly? (then how can you be sure you've covered all possibilities?)

think about how you'd chose, and how you'd keep track of where you went for a given node (assume the whole tree is a node with two children, and that's it).
 
johny doe
Ranch Hand
Posts: 78
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
i tried to firure out this subject fron the start

i got some articles aabout binary trees
i started to analize them i got stuck in a certain part of the explanatopn
when we build a binary tree
i marked // where my problem is
the problem is with the line
root.insert(toAdd);

dose it calls its self or the function below
they both got the same signatures.
i cant figure out which way it goes from there???
==================================
public class BTree
{
private BNode root;
public BTree()
{
root = null;
}
}

Public class BNode
{
private Object data;
private BNode left;
private BNode right;
public BNode(Object data)
{
this.data = data;
this.left = null;
this.right = null;
}
public void insert(Object toAdd)
{
if (isEmpty())
{
root = new BNode(toAdd);
}
else
{
root.insert(toAdd); //my problem is hereeee
}
}

public void insert(Object toAdd)
{
double select;
select = Math.random();
if (select > 0.5)
{
if (left == null)
{
left = new BNode(toAdd);
}
else
{
left.insert(toAdd);
}
}
else
{
if (right == null)
{
right = new BNode(toAdd);
}
else
{
right.insert(toAdd);
}
}
}
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic