java - 可逆迭代器

Question

我想在java中创建一个可逆迭代器，它可以反向和正向运行二叉树。不好，但请向上指示以及我到目前为止所做的事情。

DIRECTIONS

able find the next node (the inorder successor) or the previous node (the inorder predecessor) from the current node. To find the next node, there are two cases.

The current node has a right child. In this case, the next node is the minimum node on the right side. Any ancestor of the current node will either have a smaller value or a larger value than any node on the right side (and the left side for that matter).

In this case, the next node can be found as follows. First set node to current.right, then while node.left is not null, set node to node.left. After the loop is finished, set next to node.

The current node does not have a right child. In this case, the next node is going to be an ancestor of the current node. The current node might be a right child of its parent, so the code needs to keep going up the parent field until it goes up a left link. It is possible that the current node is the maximum of the tree, so the next node might be null.

In this case, the next node can be found as follows. First set child to current and set parent to current.parent. While parent is not null and child == parent.right, set child to parent and set parent to parent.parent. After the while loop, set next to parent.

Finding the previous node is symmetric. In the above descriptions, switch left with right (and switch "minimum" with "maximum").

For the iterator() method, the first call to the next method should return the minimum element of the tree. For the iterator(T start) method, the first call to the next method should return the smallest element that is greater or equal to start.

// Returns an iterator over all the elements
public ReversibleIterator<T> iterator() {
    PublicBTNode<T> current = root;

    if(size==0)
        return null;
    if(current.right!=null){
        current.right=current;
        while(current.left!=null){
            current.left=current;
        }
    }
    return (ReversibleIterator<T>) new RIForLinkedList<T>(list);
}
// return an Iterator that starts with the first element
// that is greater than or equal to start
public ReversibleIterator<T> iterator(T start) {
    return null;

}

我认为我的迭代器是错误的，因为我对此有一些限制。:

限制

SortedBST 类和任何 ReversibleIterator 类不应使用数组或 ArrayList。应该在不创建新数组、ArrayList 或节点的情况下执行迭代。

但这是我的迭代器

enter code herepublic void iterator(PublicBTNode<T> node, ArrayList<T> list) {
    if (node == null)
        return;
    iterator(node.left, list);
    list.add(node.element);
    iterator(node.right, list);
}

Answer 1

此代码看起来错误:

if(current.right!=null){
    current.right=current;
    while(current.left!=null){
        current.left=current;
    }
}

我认为应该更像是这样:

    while(current.left!=null){
        current=current.left;
    }

这里不需要 current.right 部分。

但重要的部分是迭代器的实现，这是我们看不到的。