• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Liutauras Vilda
  • Campbell Ritchie
  • Tim Cooke
  • Bear Bibeault
  • Devaka Cooray
Sheriffs:
  • Jeanne Boyarsky
  • Knute Snortum
  • Junilu Lacar
Saloon Keepers:
  • Tim Moores
  • Ganesh Patekar
  • Stephan van Hulst
  • Pete Letkeman
  • Carey Brown
Bartenders:
  • Tim Holloway
  • Ron McLeod
  • Vijitha Kumara

Binary Search Tree  RSS feed

 
Greenhorn
Posts: 4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
It is sorta covered in the JavaRanch Style Guide.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!