Results 1 to 9 of 9
 01022013, 07:35 PM #1Member
 Join Date
 Jan 2013
 Posts
 5
 Rep Power
 0
Generic Binary Search Tree HELP!!
Hi all!! Happy New Year to everyone!
Hi all !! Happy New Year!!
I am currently working on a Generic Binary Search Tree. The insertion is done according to a variable  int seqNo and the get and set methods for seqNo are in a class called AnyClass (which is in a package named dataobjects).
Now, when I am calling the getseqNo() method in the BST class, it seems that it cannot be found.
I also have a class named Node that creates the nodes for the BST.
These are my classes ;
This is the AnyClass Class:
Java Code:package dataobjects; import java.util.Scanner; public abstract class AnyClass { Scanner sc = new Scanner(System.in); public int seqNo; public String name; public AnyClass() { } public String getData() { return "Number " + seqNo; } public void edit() { System.out.println("Enter new number for the "); seqNo = sc.nextInt(); } public String getKey() { return " "+seqNo; } public void setseqNo(int SeqNo) { seqNo = SeqNo; } public int getseqNo() { return seqNo; } public static int randInt (int min, int max) { int n = min + (int) (Math.random() * (double) (maxmin+1)); System.out.println(n); return n; } }
Java Code:package LinearNode; import dataobjects.*; public class Node<E> { public E obj; public Node <E> next; public Node <E> left; public Node <E> right; public Node(E newObj) { obj = newObj; next = null; } public void show() { System.out.println(obj); } }
And finally the BST Class:
Java Code:import LinearNode.*; import dataobjects.*; public class BST<E> { Node <E> root; protected Node <E> insert (Node root,Node newNode) { if (root == null) root = newNode; else { if((newNode.obj.getSeqNo())<(root.obj.getSeqNo())) // if first is less than second root.left = insert(root.left,newNode); else root.right = insert(root.right, newNode); } return root; } public void insertBST (E newObj) { Node temp = new Node (newObj); root = insert (root,temp); } protected Node <E> search (Node root, int key) { if(root == null) return null; else { if(key == root.obj.getseqNo()) return root; else if (key<root.obj.getseqNo()) return search(root.left , key); else return search(root.right, key); } } public AnyClass SearchBST(int key) { Node <E> temp = search(root,key); if(temp== null) return null; else return temp.obj; } protected void inorder(Node root) { if(root !=null) //if not empty { inorder(root.left); root.show(); inorder(root.right); } } public void inorderBST() { inorder(root); } }
 01022013, 08:17 PM #2Member
 Join Date
 Dec 2011
 Posts
 25
 Rep Power
 0
Re: Generic Binary Search Tree HELP!!
What is the point of the 'next' Node. And in this method:
Java Code:protected Node <E> insert (Node root,Node newNode) { if (root == null) root = newNode; else { if((newNode.obj.getSeqNo())<(root.obj.getSeqNo())) // if first is less than second root.left = insert(root.left,newNode); else root.right = insert(root.right, newNode); } return root; }
Java Code:root.left = root.left; // or root.right = root.right;
Last edited by Potato; 01022013 at 08:24 PM.
 01022013, 08:24 PM #3Member
 Join Date
 Jan 2013
 Posts
 5
 Rep Power
 0
Re: Generic Binary Search Tree HELP!!
oh no.. nothing.. i declared that because I was using the Node class for another project... that has nothing to do with this. Thanks!
 01022013, 08:34 PM #4Member
 Join Date
 Dec 2011
 Posts
 25
 Rep Power
 0
Re: Generic Binary Search Tree HELP!!
If I understand you correctly, you want the insert method to insert the nodes based on the value of getSeqNo() right?
So it looks like this (Node 1 is the root because it has the smallest seqNo):
Node 1, seqNo=0
Node 2, seqNo=5
Node 3, seqNo=6
Node 4, seqNo=8
etc, they are in order of least to greatest
And for Node 1:
left = null
right = Node 2
And for Node 2:
left = Node 1
right = Node 3
etc.
Is that what you're trying to accomplish?
 01022013, 09:02 PM #5Member
 Join Date
 Jan 2013
 Posts
 5
 Rep Power
 0
Re: Generic Binary Search Tree HELP!!
Yes exactly! thanks !
 01022013, 09:28 PM #6
Re: Generic Binary Search Tree HELP!!
Cross posted
Generic Binary Search Tree (Java in General forum at JavaRanch)
dbIf you're forever cleaning cobwebs, it's time to get rid of the spiders.
 01022013, 09:50 PM #7Member
 Join Date
 Jan 2013
 Posts
 5
 Rep Power
 0
Re: Generic Binary Search Tree HELP!!
ok ok...fine... now I know that I cross Posted!!!!
 01022013, 09:58 PM #8Member
 Join Date
 Dec 2011
 Posts
 25
 Rep Power
 0
Re: Generic Binary Search Tree HELP!!
I mean, this would work if seqNo is unique (no 2 nodes have the same value for seqNo)
Java Code:protected Node <E> insert (Node root,Node newNode) { if (root == null) root = newNode; else { boolean dir = newNode.obj.getSeqNo() < root.obj.getSeqNo(); // direction: if true move left, if false move right Node<E> prev = root; do { root = dir ? root.left : root.right; if (root == null) { // moved all the way left or right if (dir) { // we moved all the way left this.root = newNode; // newNode is the head of your list of Nodes newNode.right = prev; // to the right of newNode is the previous head prev.left = newNode; // to the left of the previous head is newNode. a bit redundant. } else { // we moved all the way right prev.right = newNode; // to the right of your previous tail is newNode newNode.left = prev; // newNode is the new tail, to its left is the previous tail } } prev = root; // keep a reference to the previous root } while (newNode.obj.getSeqNo() < root.obj.getSeqNo() == dir); // If we got to this point, we haven't reached the head or tail end of the Node list // 'root' will be on one side of 'newNode' and 'prev' will be on the other side of 'newNode' // if we were moving left, i.e. dir == true, then root should be on the left said and prev on the right side. if dir == false, vice versa. if (dir) { root.right = newNode; prev.left = newNode; newNode.left = root; newNode.right = prev; } else { root.left = newNode; prev.right = newNode; newNode.right = root; newNode.left = prev; } } return root; }
 01022013, 10:06 PM #9Member
 Join Date
 Jan 2013
 Posts
 5
 Rep Power
 0
Similar Threads

Binary search tree ?
By santa in forum New To JavaReplies: 5Last Post: 06072011, 04:22 PM 
Generic Binary Search Tree, Allowing Only Comparable Elements
By XMalleus in forum Advanced JavaReplies: 6Last Post: 04282010, 01:49 AM 
Data Structures(Binary Search Tree to AVL Tree)ASAP pls
By jfAdik in forum Forum LobbyReplies: 0Last Post: 04042010, 08:40 AM 
Binary search tree search method
By chopo1980 in forum New To JavaReplies: 2Last Post: 12102009, 02:42 AM 
Binary Search Tree
By michael_mke in forum New To JavaReplies: 3Last Post: 12042008, 03:03 AM
Bookmarks