Meaningless Drivel is fun!
The moose likes Java in General and the fly likes Binary search tree Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Java in General
Bookmark "Binary search tree" Watch "Binary search tree" New topic

Binary search tree

Keshan Pillay

Joined: May 21, 2008
Posts: 29
Hello everyone! Thanks for checking out my topic.
What I need to do for this assignment, is I need to pass a string as an argument to my program. Then I need to put the letters into a binary search tree. I successfully managed to pass the string, say..."MGABDF" and then I used a for loop, and string.chatAt() to put each letter of the String into an array for easier access later. What i'm having trouble with, is my use of the binary search tree. I'm quite stuck actually.

This is what i've got so far and i can't seem to set the root. Let me know if you need to see the code for the BinarySearchTree and TreeNode.

Many Thanks.
Campbell Ritchie

Joined: Oct 13, 2005
Posts: 46367
Binary trees are quite straightforward to write once you have got your head round the structure. They don't need sorting, if you have some sort of sorting on insertion, and they don't maintain insertion order, unless they have a List associated which records insertion order. They don't usually support duplicates, which means they represent Sets.

You appear to be putting code which "does things" into your constructor. Don't. Not even if you see a book by Judy Bishop with that sort of thing in. The constructor is for setting up the initial state of the object, and by the end of the constructor every instance field ought to be assigned a non-null value, then you put code to "do things" in methods. So you want a method which calls the tree and fills it up, a method which calls the tree and queries it as to whether it contains a particular value, and a method which calls the tree to get it printed out.

The filling up, the searching and the printing should be done inside the tree.

You want a method which reads something like thisThat could be the main method, but I prefer a method called go(), which you call from the main method.

Let's have that lot in the main method for the time being, even though a 1-line main method would be better, because you don't want too many changes all at once.Now design a TreeNode class which the following methods
  • public void add(char c)
  • public boolean contains(char c)
  • public void print()
  • Beware of null values; every binary tree is guaranteed to contain null values, so you must check for them when you are traversing the tree.

    It might be helpful for you to show your code, yes.

    Good luck with it.
    Piet Verdriet
    Ranch Hand

    Joined: Feb 25, 2006
    Posts: 266
    Create a Tree-class that encapsulates your root (and it's children). Here's a start:

    [ October 16, 2008: Message edited by: Piet Verdriet ]
    I agree. Here's the link:
    subject: Binary search tree
    It's not a secret anymore!