Last time guys, my SearchPath seems to be the buggy one now. Parameters, and met

Question

Last time guys, my SearchPath seems to be the buggy one now. Parameters, and methods most stay the same. Thanks in advance guys.

package bstpractice;

import java.io.*;

import java.util.*;

class Node {

public String name;

//data[low] or data[high] are the data items represented by the subtree

//data[mid] is the lowIndx+highIndx +1 / 2

public int lowIndx, highIndx, leftChildIndx, rightChildIndx;

public Node(int lowIndx, int highIndx, int leftChildIndx, int rightChildIndx){

this.lowIndx = lowIndx; this.highIndx = highIndx;

this.leftChildIndx = leftChildIndx; this.rightChildIndx = rightChildIndx;

}

public String toString(){

return("lowIndx=" + lowIndx + " highIndx=" + highIndx +

((leftChildIndx >= 0) ? ("leftChildIndx=" + leftChildIndx) : "") +

((rightChildIndx >= 0) ? ( "rightChildIndx=" + rightChildIndx) : ""));

}

}

public class BSTpractice {

int root;

int [] data = {-3, 2, 11, 12, 18, 23, 31, 32, 35, 42, 44};

Node[] nodes;

public BSTpractice(int numNodes){

nodes = new Node[numNodes];

root = BuildBST(0, numNodes-1);

}

//This is the function im having problems with.

//This is supposed to be a recursive function, that returns the root node num.

//His example is: nodes[1]: lowIndx=0 highIndx=1 leftChildIndx=0

private int BuildBST(int low, int high)

{

if(low > high){ return -1; }

int root = (low+high+1)/2;

int lowIndx = BuildBST(low, root-1);

int highIndx = BuildBST(root+1, high);

nodes[root] = new Node(lowIndx, highIndx, lowIndx, highIndx);

System.out.println("nodes[" + root + "]: " + nodes[root].toString());

return(root);

}

//This is supposed to be an non-recursive function

//It returns the Binary Tree search path

// This should print out X=12 found at data[3]

// searchPathDataIndices (0, 8, 12): [4, 2, 3]

public ArrayList<Integer> SearchPath(int startIndx, int endIndx, int x){

ArrayList<Integer> searchPathDataIndices = new ArrayList<Integer>();

int origStartIndx = startIndx, origEdIndx = endIndx;

//this while-loop will all the loop to be terminated immediately after the test fails.

while (startIndx <=endIndx){

if (startIndx == );

else if (startIndx < x){

searchPathDataIndices.add(endIndx,x);

x++;

}

else if(startIndx > x){

searchPathDataIndices.add(startIndx,x);

}

}

return (searchPathDataIndices);

}

public static void main(String[] args) {

Scanner scan = new Scanner(System.in);

int numNodes = 9;

BSTpractice bst = new BSTpractice(numNodes);

System.out.println();

System.out.print("data[]: " + Arrays.toString(bst.data));

System.out.println(" (only the first " + numNodes + "items used)");

System.out.print("Hit return-key to continue successive runs of SearchPath:");

scan.nextLine();

bst.SearchPath(0, numNodes-1, 12);

scan.nextLine();

bst.SearchPath(0, numNodes-1, 20);

scan.nextLine();

bst.SearchPath(0, numNodes-1, 10);

scan.nextLine();

bst.SearchPath(0, numNodes-1, -5);

scan.nextLine();

bst.SearchPath(0, numNodes-1, 43);

scan.nextLine();

bst.SearchPath(0, numNodes-1, 32);

scan.nextLine();

}

}

Explanation / Answer

//This is supposed to be an non-recursive function
//It returns the Binary Tree search path
// This should print out X=12 found at data[3]
// searchPathDataIndices (0, 8, 12): [4, 2, 3]
public ArrayList<Integer> SearchPath(int startIndx, int endIndx, int x)
{
ArrayList<Integer> output = new ArrayList<Integer>();

int curr = root;
while(curr >= startIndx && curr <= endIndx)
{
output.add(curr);
// use this instead if you want to see the values of the nodes
//output.add(data[curr]);

// check if found
if(data[curr] == x)
break;

// if not, continue search
if(x < data[curr])
curr = nodes[curr].leftChildIndx;
else
curr = nodes[curr].rightChildIndx;
}

// don't print here, print in main()
//System.out.println(output);
return output;
}

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.