开发者

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?

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜