Find the node that has next value of current node value in Binary Search Tree
I have BST of BTNode<E>
's each has double number and I have the following fields:
BTNode <E> root
: a pointer to the root of the tree
BTNode <E> current
: a pointer to the current node
I want to write a method Next() that make the current points to node that has next value of current node value
Here is wha开发者_StackOverflow社区t I have done so far:
public boolean Next()
{
// List<E> tempList = new ArrayList<E>(); // Creating new list (I defined this at the begining of the class)
E tempValue = current.getElement(); // Gets the value of current element
makeSortedList(root); //
E[] tempArray = (E[]) tempList.toArray(); // Convert the list to an array
int index = Arrays.binarySearch(tempArray, tempValue); // Find the position of current node value in the array
if(index >= count) // count is no. of nodes in the tree
{
E targetValue = tempArray[index + 1]; // Store the target value in a temporary variable
search(targetValue); // This method searches for the node that has targetValue and make that node as the current node
return true;
}
else return false;
}
// This method takes the values of the tree and puts them in sorted list
private void makeSortedList(BTNode<E> myNode)
{
if(myNode != null)
{
makeSortedList(myNode.getLeft());
tempList.add(myNode.getElement());
makeSortedList(myNode.getRight());
}
}
Could you help me write this method?
Did you check that the index returned by Arrays.binarySearch() is what you expect? Also the elements should be sorted before calling it. And it is not clear from you code example how you handle the case when the value is not found within the array. Assuming it is always in the array why are you then retrieving the value @index+1?
精彩评论