package bstpractice; import java.io.*; import java.util.*; class Node { public S

Question

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){

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

if(low == high);

else if(low < root){

if(low<root)

root=low;

}

else{

BuildBST(root, high);

}

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

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 <=x){

if (startIndx == x);

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

I assume the data array will always be sorted, and the goal is to make a balanced BST.

//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)
{
// break condition
if(low > high)
{
return -1;
}

// otherwise, divide and conquer
int mid = (low+high)/2;

int lowIndx = BuildBST(low, mid-1);
int highIndx = BuildBST(mid+1, high);

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

return mid;
}

I have included the following test methods to verify the BST is built correctly. You can call these in main().

private void printNodes()
{
System.out.println();
for(int i = 0; i < nodes.length; i++)
{
if(nodes[i] == null)
{
System.out.println(i+" null");
}
else
System.out.println(i+" "+nodes[i].lowIndx+" "+nodes[i].highIndx+" "+nodes[i].leftChildIndx+" "+nodes[i].rightChildIndx);
}
System.out.println();
}

// traversal
private void inOrder()
{
inOrder(root);
}
private void inOrder(int node)
{
System.out.println();
if(nodes[node].leftChildIndx >= 0)
{
inOrder(nodes[node].leftChildIndx);
}
System.out.print(data[node]+" ");
if(nodes[node].rightChildIndx >= 0)
{
inOrder(nodes[node].rightChildIndx);
}
System.out.println();
}

__________________

public static void main(String[] args)
{
int numNodes = 9;

BSTpractice bst = new BSTpractice(numNodes);

System.out.println();

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

bst.printNodes();
bst.inOrder();

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

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

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