在 Java 中为二叉树编写通用迭代器

Question

我想为二叉树编写自定义迭代器。这个迭代器应该 return Node<?> 个对象。我在递归调用 fillList 的行中在文件 InorderIterator 中遇到编译错误：fillList(currentNode.getLeft());

错误是：Error:(14, 37) java: incompatible types: rclib.Node cannot be converted to T

有人可以解释一下为什么我的方法不起作用吗？或者如何修复它

Node.java

package rclib;

public class Node<T extends Comparable<T>> {
    T key;
    Node<T> left;
    Node<T> right;
    public Node(T key, Node left, Node right) {
        this.key = key;
        this.left = left;
        this.right = right;
    }

    public Node(T key) {
        this(key, null, null);
    }

    public Node<T> getLeft() {
        return left;
    }

    public Node<T> getRight() {
        return right;
    }

    public T getKey() {
        return key;
    }
}

InorderIterator.java

package rclib;
import java.util.*;

public class InorderIterator<T extends Node<?>> implements Iterator<T> {
    LinkedList<T> list;

    public InorderIterator(T root) {
        list = new LinkedList<T>();
        fillList(root);
    }

    public void fillList(T currentNode) {
        if (currentNode == null) return;
        fillList(currentNode.getLeft());
        list.add(currentNode);
        fillList(currentNode.getRight());
    }

    @Override
    public boolean hasNext() {
        return !list.isEmpty();
    }

    @Override
    public T next() {
        return list.removeFirst();
    }
}

AVLTree.java

package rclib;

public class AVLTree<T extends Comparable<T>> implements Iterable<Node<T>>{
    private Node<T> root;

    @Override
    public Iterator<Node<T>> iterator() {
        return new InorderIterator<Node<T>>(root);
    }
}

Answer 1

你也许应该这样做：

package rclib;
import java.util.*;

public class InorderIterator<T extends Comparable<T>> implements Iterator<Node<T>> {
    LinkedList<Node<T>> list;

    public InorderIterator(Node<T> root) {
        list = new LinkedList<Node<T>>();
        fillList(root);
    }

    public void fillList(Node<T> currentNode) {
        if (currentNode == null) return;
        fillList(currentNode.getLeft());
        list.add(currentNode);
        fillList(currentNode.getRight());
    }

    @Override
    public boolean hasNext() {
        return !list.isEmpty();
    }

    @Override
    public Node<T> next() {
        return list.removeFirst();
    }
}

Answer 2

您必须明确指定您使用的是 Node 而不是 ? extends Node，这最终可能不符合正确的用法。

public static class InorderIterator<T extends Comparable<T>> implements Iterator<Node<T>> {
    LinkedList<Node<T>> list;

    public InorderIterator(Node<T> root) {
        list = new LinkedList<>();
        fillList(root);
    }

    public void fillList(Node<T> currentNode) {
        if (currentNode == null) return;
        fillList(currentNode.getLeft());
        list.add(currentNode);
        fillList(currentNode.getRight());
    }

    @Override
    public boolean hasNext() {
        return !list.isEmpty();
    }

    @Override
    public Node<T> next() {
        return list.removeFirst();
    }
}

在 Java 中为二叉树编写通用迭代器

Writing a generic iterator in Java for Binary Tree

java

generics

iterator

iterable