Home > database >  Binary Search Tree, In-order transversal return generic array
Binary Search Tree, In-order transversal return generic array

Time:11-23

public class Bst<E extends Comparable<E>> {

private BstNode<E> root;

    public Bst(E data) {
       root = new BstNode<>(data);
    }

    public void add(E data) {
        root = arr(data,root);
    }

    private BstNode<E> add(E data, BstNode<E> startNode) {
        if (startNode == null) {
            startNode = new BstDupNode<>(data);
        } else if (data.compareTo(startNode.data) < 0) {
            startNode.left = add(data, startNode.left);
        } else {
            startNode.right = add(data, startNode.right);
        }
        return startNode;
    }
   
    public E[] getAllData(E[] template) {
        index = 0;
        inorderTraversal(template, root, index);
        return template;
    }

    private int index;

    private void inorderTraversal(E[] template, BstNode<E> startNode, int index) {
        if (startNode != null) {
            inorderTraversal(template,startNode.left, index);
            template[index  ] = startNode.data;
            inorderTraversal(template, startNode.right, index);
        }
    }


    private static class BstNode<E extends Comparable<E>> {
        public int count;
        public E data;
        public BstNode<E> left , right;

        public BstDupNode(E data) {
            this.data = data;
            left = right = null;
        }
    }

    public static void main(String[] args) {
        Bst<Integer> hello = new BstDup<>(7);
        hello.add(8);
        hello.add(3);
        hello.add(1);
        hello.add(6);
        hello.add(4);
        hello.add(10);
        hello.add(14);
   }
}

I am getting results like

[7, 8, 10, 14, null, null, null, null, null, null, null]

I don't know why the index is set back to zero from time to time. Because since I set up the global variable, it should be kept counting up as reclusive continues, or at least that is how I think. I want to understand in the end not just answer if you can provide some explanation I will be greatly appreciated it. Thank you.

CodePudding user response:

Java uses pass-by-value, meaning that a method gets the values of its parameters, but these are separate from the caller's copies; so when you reassign a method parameter, the caller doesn't see that reassignment.

For example, a method like this:

void increment(int i) {
      i;
}

has no effect whatsoever: the method increments its copy of i, but nothing uses that copy.

In your case, the problem is that your inorderTraversal method takes a parameter index by value — so it has its own copy — and then it increments that copy, which is fine, but its caller never sees that change.

To fix this, I'd recommend having inorderTraversal return the updated index:

    private int inorderTraversal(E[] template, BstNode<E> startNode, int index) {
        if (startNode != null) {
            index = inorderTraversal(template,startNode.left, index);
            template[index  ] = startNode.data;
            index = inorderTraversal(template, startNode.right, index);
        }
        return index;
    }
  • Related