Cristian Cristian - 1 month ago 6
Java Question

BinaryTree implementation

I want to implement a Binary Tree in java and i have a problem with the nodes.The problem is that i can't save the newN in the root node. Everytime i try to insert a new node, the root is null and the pointer doesn't point to the newN address.When i find a node that is null i want to make him point to a newN(a node with info==x and left and right children on null).How can i fix this?

public class Node {
public int info;
public Node left;
public Node right;

Node(int info) {
this.info = info;
}
}



public class BTree {
public Node root;

BTree() {
root = null;
}

public void add(int x) {
insert(root, x);
}

public boolean insert(Node r, int x) {
if (r == null) {
r = new Node(x);
return true;
}
else{
if (r.info == x) {
System.out.println("the value has already been added");
return false;
}
if (r.info < x)
insert(r.left, x);
if (r.info > x)
insert(r.right, x);
}

return false;
}

public void inOrder() {
inOrderTraverse(root);
}

public void inOrderTraverse(Node r) {
if (r != null) {
inOrderTraverse(r.left);
System.out.print(r.info + " ");
inOrderTraverse(r.right);
}

}

}



public class Main {
public static void main(String args[]){
BTree bt=new BTree();
bt.add(10);
bt.add(5);
bt.add(3);
bt.add(2);
bt.inOrder();
}
}


PS:I know there are no pointers in Java and all the function calls are made with the address , not the value.Isn't insert(Node r,int x) equivalent with insert(Node &r,int &r) from c++?

Answer

Basically, no insert(Node r, int x) is not equivalent to insert(Node &r, int &x). Java passes arguments by value, not by reference. More to the point here:

public boolean insert(Node r, int x) {
    if (r == null) {
        r = new Node(x);
        return true;
    }
    else{
        if (r.info == x) {
            System.out.println("the value has already been added");
            return false;
    }
        if (r.info < x)
            insert(r.left, x);
        if (r.info > x)
            insert(r.right, x);
    }

    return false;
}

You assume that assigning a value to r (new Node(x)) will assign a value to the location pointed to by r, but this is not how Java understands things. Assigning a value to r will overwrite the value of r, i.e., r now refers to the new Node, but only r as localised to the insert() function. So r no longer has any connection to the original value that was passed in.

You can implement something correctly much more simply:

public void add(int x) {
    if (this.root == null) {
        this.root = new Node(x);
    } else {
        r = this.root;
        if (x > r.info) {
             while (r != null && x > r.info) {
                 r = r.right;
             }

             r.right = new Node(x);
        }
        // similarly for x < root.info, etc.
}