自定义的TreeSet类,如何编写迭代器

huangapple 未分类评论44阅读模式
标题翻译

Custom treeSet class, how to write iterator

问题

我正在尝试创建自己的二叉搜索树但我无法想出任何实现工作迭代器具有 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();
    }

}
英文翻译

I am trying to create my own binary search tree. But I can't think of any way to implement a working iterator that has hasNext(), next().
I got the idea the only way to traverse a Binary search tree was through recursion. But how could I possibly save a recursion call if I am trying to use next, so it resumes when next gets called again and returns the value?
Is there any other way

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) &lt; 0) {
                if(left == null) {
                    left = new BST(newWord);
                } else {
                    left.add(newWord);
                }
            } else if (newWord.compareTo(value) &gt; 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&lt;Word&gt; {

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

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

    @Override
    public Iterator&lt;Word&gt; iterator() {
        return new TreeWordSetIterator();
    }

}

答案1

得分: 0

如果这是一个用于学习目的的练习,也许最好的方法就是去查看TreeSet是如何实现的。如果这是一个用于生产环境的练习,请立即停止,并且只在真正需要时扩展TreeSet。

英文翻译

If this is an exercise for the purpose of learning, maybe the best way is to just go look how TreeSet does it. If this is an exercise for production use, stop it right here right now and extend TreeSet if you really need to.

答案2

得分: 0

我是这样解决的,虽然不够华丽。直到有人能够提供更好的解决方案:

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;
    }
}
英文翻译

I solved it this way, it's not glamourous. Until someone can provide a better solution

    private class TreeWordSetIterator implements Iterator&lt;Word&gt; {
    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 &lt; size()) {
            return true;
        } else {
            return false;
        }
    }

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

    }
}

huangapple
  • 本文由 发表于 2020年3月17日 03:16:26
  • 转载请务必保留本文链接:https://java.coder-hub.com/60711972.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定