标题翻译
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) < 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();
}
}
答案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<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;
}
}
专注分享java语言的经验与见解，让所有开发者获益！
评论