обратимый итератор - PullRequest
Новая
       11

обратимый итератор

0 голосов
/ 18 апреля 2011

Я предполагаю сделать обратимый итератор в Java, который предполагает запуск через двоичное дерево в обратном направлении и вперед. заболел, но не в том направлении и что я сделал до сих пор.

DIRECTIONS

может найти следующий узел (порядок) преемник) или предыдущий узел ( по порядку предшественника) от текущего узел. Чтобы найти следующий узел, есть два случая.

У текущего узла есть правильный дочерний элемент. В в этом случае следующий узел минимальный узел на правой стороне. любой предок текущего узла будет либо имеют меньшее значение или большее значение, чем любой узел на правая сторона (и левая сторона для этого иметь значение).

В этом случае следующий узел может быть найдено следующим образом. Первый набор узлов current.right, тогда пока node.left не нуль, установите для узла значение node.left. После цикл завершен, установите рядом с узел.

Текущий узел не имеет права ребенок. В этом случае следующий узел будет предком нынешнего узел. Текущий узел может быть правый потомок своего родителя, поэтому код должен продолжать идти родитель поле, пока он не поднимется вверх по левой ссылке. Это возможно, что текущий узел максимум дерева, поэтому следующий узел может быть нулевым.

В этом случае следующий узел может быть найдено следующим образом. Сначала установите ребенка на текущий и установите родителя в current.parent. Пока родитель не null and child == parent.right, установить дочерний родительский и установить родительский для parent.parent. После цикла пока установить рядом с родителем.

Нахождение предыдущего узла симметричны. В приведенных выше описаниях, переключиться влево с правой (и переключатель «минимум» с «максимум»).

Для метода iterator () первый вызов следующего метода должен вернуть минимальный элемент дерева. За метод итератора (T 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 не должны использовать массивы или ArrayLists. Итерация должна выполняться без создания новых массивов, списков массивов или узлов.

но вот мой итератор 

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);
}

1 Ответ

1 голос
/ 18 апреля 2011

Этот код выглядит неправильно: 

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

Я думаю, что это должно быть примерно так: 

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

current.right часть, которая вам здесь не нужна.

Но важной частью является реализация вашего итератора, которого мы не видим.

...