Пользовательский класс treeSet, как написать итератор - PullRequest
Новая
       69

Пользовательский класс treeSet, как написать итератор

0 голосов
/ 16 марта 2020

Я пытаюсь создать свое собственное двоичное дерево поиска. Но я не могу придумать, как реализовать работающий итератор, который имеет hasNext (), next (). Я понял, что единственный способ пройти через бинарное дерево поиска - это рекурсия. Но как я могу сохранить рекурсивный вызов, если я пытаюсь использовать next, чтобы он возобновлялся, когда next вызывается снова и возвращает значение? Есть ли другой способ 

import java.util.Iterator;

public class TreeWordSet implements WordSetInterface {
    private BST root = null;

    private class BST {
        Word value;
        BST left = null;
        BST right = null;

        BST(Word word) {
            value = word;
        }

        void add(Word newWord) {
            if (newWord.compareTo(value) < 0) {
                if(left == null) {
                    left = new BST(newWord);
                } else {
                    left.add(newWord);
                }
            } else if (newWord.compareTo(value) > 0) {
                if (right == null) {
                    right = new BST(newWord);
                } else {
                    right.add(newWord);
                }
            }
        }
    }

    @Override
    public void add(Word word) {
        if (root == null) {
            root = new BST(word);
        } else {
            root.add(word);
        }
    }

    @Override
    public boolean contains(Word word) {
        return false;
    }

    @Override
    public int size() {
        return 0;
    }

    private class TreeWordSetIterator implements Iterator<Word> {

        @Override
        public boolean hasNext() {
            return false;
        }

        @Override
        public Word next() {
            return null;
        }
    }

    @Override
    public Iterator<Word> iterator() {
        return new TreeWordSetIterator();
    }

}

Ответы [ 2 ]

0 голосов
/ 16 марта 2020

Я решил это таким образом, это не гламурно. Пока кто-то не может предложить лучшее решение 

    private class TreeWordSetIterator implements Iterator<Word> {
    Word arr[] = new Word[size()];
    int i = 0;
    TreeWordSetIterator(){
        traverse(root);
        i = 0;
    }

    private void traverse(BST currentNode) {
        if (currentNode == null) {
            return;
        }
        traverse(currentNode.left);
        arr[i] = currentNode.value;
        i++;
        traverse(currentNode.right);
    }

    @Override
    public boolean hasNext() {
        if (i < size()) {
            return true;
        } else {
            return false;
        }
    }

    @Override
    public Word next() {
        Word current = arr[i];
        i++;
        return current;

    }
}
0 голосов
/ 16 марта 2020

Если это упражнение с целью изучения, возможно, лучше всего просто go посмотреть, как это делает TreeSet. Если это упражнение для производственного использования, остановите его прямо здесь и прямо сейчас и расширьте TreeSet, если вам действительно нужно.

...