GeeCON Prague 2014*
The moose likes Beginning Java 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 » Beginning Java
Bookmark "Binary Search Tree" Watch "Binary Search Tree" New topic
Author

Binary Search Tree

Joe Long
Greenhorn

Joined: Mar 07, 2004
Posts: 4
Hi Everyone, i'm still real new at configuring methods. which way would be the best to implement given this code. At the insert method, I need to check to see if the key is already in the binary tree, if it is...then just exit the method.I am wondering wouldnt I just call the query method before entering the "insert" method? any help on modifying this method to check for key would be great!
/******************************************************************************
File: IntTree.java
Date: 3/5/2004
Name: Joe Long
Description:
This class demonstrates several concepts related to creating and maintaining
a binary search tree. The data items are ints, but could be any Comparable
data type.
Notes & Caveats:
-The Node class has been made into a private inner class so that this class
is entirely self-contained.
******************************************************************************/
public class IntTree
{
private Node root;
//-----------------------------------------------------------------------------
// constructor creates a Node to serve as the list head.

public IntTree()
{
root = new Node();
}
//-----------------------------------------------------------------------------
// Method: void maximum()
public int maximum()
{
Node node;

for (node = root; node.right != null; node = node.right);

return node.item;
}
//-----------------------------------------------------------------------------
// Method: void minimum()
public int minimum()
{
Node node;

for (node = root.right; node.left != null; node = node.left);

return node.item;
}
//-----------------------------------------------------------------------------
// Method: void insert(int key)
// Insert a new key at its proper place in the BST. If the key is found to be
// already in the tree the insert request is simply ignored.
public void insert(int key)
{
insertHelper(root, key);
}

private void insertHelper(Node node, int key)
{
if (node.item > key)
{
if (node.left != null) insertHelper(node.left, key);
else node.left = new Node(key);
}
else
{
if (node.right != null) insertHelper(node.right, key);
else node.right = new Node(key);
}
}


// An iterative implementation of the insert method

public void insertInterative(int key)
{
Node node = root;

do
{
if (node.item > key)
{
if (node.left == null)
{
node.left = new Node(key);
break;
}
else node = node.left;
}
else
{
if (node.right == null)
{
node.right = new Node(key);
break;
}
else node = node.right;
}
}
while (node != null);
}

//-----------------------------------------------------------------------------
// Method: boolean query(int key)
// Returns true if the specified key is in the list, otherwise false.
public boolean query(int key)
{
return queryHelper(root, key);
}

private boolean queryHelper(Node node, int key)
{
boolean result = false;

if (node.item > key)
{
if (node.left != null)
result = queryHelper(node.left, key);
}
else if (node.item < key)
{
if (node.right != null)
result = queryHelper(node.right, key);
}
else result = true;

return result;
}


// An iterative implementation of the query method
public boolean queryIterative(int key)
{
boolean result = false;

return result;
}

thanks
Joe Long
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Binary Search Tree