[mel_ga]

Hi, I have the following Binary Search tree but when i'm populating it from the main class it is only displaying me the first object. I think the fault is in the insert method but I don't know. If someone can found for me the fault I will be very grateful. Here's the code:

   BNode Insert(BNode rt, BNode newNode) {
        if (rt == null) {
            rt = newNode;
        } else if (newNode.getObj().getSeqNo() <= rt.getObj().getSeqNo()) {
            Insert(rt.getLeft(), newNode);
        } else {
            Insert(rt.getRight(), newNode);
        }
        return rt;
    }
   
  public void insertBST(AnyClass newObj) {
        BNode bn = new BNode(newObj);
        root = Insert(root, bn);
    }

[macosxnerd101]

Moved to Java. Please do not post programming help questions in the Site Questions forum. That is for DIC related questions.

Your Insert method looks fine to me. Post sufficient code so we can run a sample, and include the input you are providing, the output you are getting, and the output you are expecting.

[mel_ga]

When I run my Main program the BST is only inserting the right node and its leaving the root and the left.

[mel_ga]

public class BNode {

    public BNode left, right;
    private AnyClass obj;

    public BNode getLeft() {
        return left;
    }

    public void setLeft(BNode left) {
        this.left = left;
    }

    public AnyClass getObj() {
        return obj;
    }

    public void setObj(AnyClass obj) {
        this.obj = obj;
    }

    public BNode getRight() {
        return right;
    }

    public void setRight(BNode right) {
        this.right = right;
    }

    public BNode(AnyClass newObj) {
        left = null;
        right = null;
        obj = newObj;
    }
}
public class AnyClass {

    private int seqNo;
    private String key;

    public AnyClass() {
    }

    public AnyClass(int seqno,String Key) {
        this.seqNo = seqno;
        this.key=Key;
    }
    
    public void setKey(String key) {
        this.key=key;
    }

    public String getKey() {
        return key;
    }

    public int getSeqNo() {
        return seqNo;
    }

    public void setSeqNo(int seqNo) {
        this.seqNo = seqNo;
    }
    
    

    public String getData() {
        return ("number is :" + seqNo+"key is :" + key);
        
    }

[mel_ga]

public class BNode {

    public BNode left, right;
    private AnyClass obj;

    public BNode getLeft() {
        return left;
    }

    public void setLeft(BNode left) {
        this.left = left;
    }

    public AnyClass getObj() {
        return obj;
    }

    public void setObj(AnyClass obj) {
        this.obj = obj;
    }

    public BNode getRight() {
        return right;
    }

    public void setRight(BNode right) {
        this.right = right;
    }

    public BNode(AnyClass newObj) {
        left = null;
        right = null;
        obj = newObj;
    }
}
public class AnyClass {

    private int seqNo;
    private String key;

    public AnyClass() {
    }

    public AnyClass(int seqno,String Key) {
        this.seqNo = seqno;
        this.key=Key;
    }
    
    public void setKey(String key) {
        this.key=key;
    }

    public String getKey() {
        return key;
    }

    public int getSeqNo() {
        return seqNo;
    }

    public void setSeqNo(int seqNo) {
        this.seqNo = seqNo;
    }
    
    

    public String getData() {
        return ("number is :" + seqNo+"key is :" + key);
        
    }

[mel_ga]

Could you pls help me in finding the error?

This post has been edited by mel_ga: 17 May 2012 - 08:01 AM

[macosxnerd101]

Quote

Post sufficient code so we can run a sample, and include the input you are providing, the output you are getting, and the output you are expecting.

Post what you are running- all of it. Please include what I asked for in my last post so I can better help you.

[mel_ga]

import Dataobjects.AnyClass;
import NonLinearStructures.BinSearchTree;

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
/**
 *
 * */
public class Test {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
    
       System.out.println ("tree");       
        BinSearchTree bins = new BinSearchTree(null);
        AnyClass obje1 = new AnyClass(5, "borg");
        bins.insertBST(obje1);

        AnyClass obje2 = new AnyClass(6, "camilleri");
        bins.insertBST(obje2);

        AnyClass obje3 = new AnyClass(7, "gatt");
        bins.insertBST(obje3);

        bins.ListInOrder();
        

    }
}
package NonLinearStructures;

import Dataobjects.AnyClass;
import LinearNodes.Node;
import LinearStructures.List;
import binaryNodes.BNode;

/**
 *
 * @author Melvic
 */
public class BinSearchTree {

    private BNode root;

    public BNode getRoot() {
        return root;
    }

    public void setRoot(BNode root) {
        this.root = root;
    }

    public BinSearchTree(BNode rt) {
        root = null;
    }

    BNode Insert(BNode rt, BNode newNode) {
        if (rt == null) {
            rt = newNode;
        
            if (newNode.getObj().getSeqNo() <= rt.getObj().getSeqNo()) {
           rt.left= Insert(rt.getLeft(), newNode);           

            } else {
                Insert(rt.getRight(), newNode);
            }

        }
        return rt;
    }
    

        
  public void insertBST(AnyClass newObj) {
        BNode bn = new BNode(newObj);
        root = Insert(root, bn);
    }
    
        
        
    
    private BNode search(BNode rt, String key) {
        if (rt == null) {
            return null;
        } else if (key.equals(rt.getObj().getKey())) {
            return rt;

        } else if (key.compareToIgnoreCase(rt.getObj().getKey()) < 0) {
            return search(rt.getLeft(), key);
        } else {
            return search(rt.getRight(), key);
        }
    }

    public AnyClass searchBST(String keyname) {
        BNode temp = search(root, keyname);
        if (temp == null) {
            return null;
        } else {
            return temp.getObj();
        }
    }

    public void InorderBst(BNode root) {      
        if (root != null) {
            InorderBst(root.getLeft());
        System.out.println(root.getObj().getData());
            InorderBst(root.getRight());
        }
    }

    public void ListInOrder() {
        InorderBst(root);

    }

This post has been edited by macosxnerd101: 17 May 2012 - 02:01 PM
Reason for edit:: Fixed code tags

[macosxnerd101]

Here's the first logic error I see. You test if rt is null, then assign rt = newNode. Remember that rt is a local variable. You really want to check if root is null, then assign root = newNode. Assigning rt = newNode will only affect rt within the method call. It will not affect root.

The second logic error I see is that you are making an assignment to rt.left. You don't want to do this. Make the assignment in the base case(s) of the method. Don't worry about returning Nodes.

[jjl]

Quote

Here's the first logic error I see. You test if rt is null, then assign rt = newNode. Remember that rt is a local variable. You really want to check if root is null, then assign root = newNode. Assigning rt = newNode will only affect rt within the method call. It will not affect root.

The root is assigned to the return value of Insert, if rt is null than rt is set to the new node and then returned (therefore assigning the root - or subroot).

Quote

The second logic error I see is that you are making an assignment to rt.left. You don't want to do this. Make the assignment in the base case(s) of the method. Don't worry about returning Nodes.

You need to return the nodes to restructure the BST, otherwise the root and sub-roots will never change.

see comments

    BNode Insert(BNode rt, BNode newNode) {
        if (rt == null) {
            rt = newNode;
        
            if (newNode.getObj().getSeqNo() <= rt.getObj().getSeqNo()) {
           rt.left= Insert(rt..left, newNode);           

            } else {
                Insert(rt.right, newNode); // you need to assign rt.right to the returned node
            }

        }
        return rt;
    }

An easier way to compare BNodes is to implement the Comparable interface, then you could simple use compareTo(T)

This post has been edited by jjl: 17 May 2012 - 03:27 PM

[mel_ga]

Yes I was doing this but since left and right are private I cannot access them. When I do rt.getleft() it is giving me an error. What can I do?

[mel_ga]

In my code above they left and right are public but I must make them private