java - Java 中具有 3 个子节点的树的迭代器实现

Question

对于大学，我应该将接口(interface)迭代器实现为具有 3 个子级的树的内部类。我的树实现如下所示:

import java.util.*;

public class TernaerTree <E> {

    private TernaerTree left;
    private TernaerTree right;
    private TernaerTree middle;
    private E value;

    public E getValue() {
        return value;
    }

    public TernaerTree(TernaerTree left, TernaerTree middle, TernaerTree right, E value) {
        this.left = left;
        this.right = right;
        this.middle = middle;
        this.value = value;
    }

    public static void main(String [] args){

        TernaerTree <String> baum = new TernaerTree<String>(new TernaerTree<String>(null,null,null,"Hallo"),new TernaerTree<String>(null,null,null,"Welt"),new TernaerTree<String>(null,null,null,"?"),"!");
    }

    public class WalkThroughIterator implements Iterator {

        @Override
        public boolean hasNext() {
        }

        @Override
        public Object next() {
        }

        @Override
        public void remove() {
            throw new UnsupportedOperationException("remove() is not supported.");
        }

    }

}

现在我应该实现 WalkthroughIterator。它应该按以下顺序遍历树:左、中、右和节点本身。迭代器应该使用递归子树的迭代器。

在主方法中，所有内容都应该打印在屏幕上。

希望有人能帮助我。

谢谢，托比亚斯

Answer 1

这似乎有效 - 它使用迭代器列表来跟踪内部树。一旦它们全部耗尽，它就会发出该元素。

public class TernaerTree<E> implements Iterable<E> {

    private TernaerTree left;
    private TernaerTree middle;
    private TernaerTree right;
    private E value;

    public E getValue() {
        return value;
    }

    public TernaerTree(TernaerTree left, TernaerTree middle, TernaerTree right, E value) {
        this.left = left;
        this.middle = middle;
        this.right = right;
        this.value = value;
    }

    @Override
    public Iterator<E> iterator() {
        return new WalkThroughIterator();
    }

    public class WalkThroughIterator implements Iterator<E> {

        // All the iterators of all of the sub-trees that weren't null.
        List<Iterator<E>> iterators = new LinkedList<>();
        // Have we delivered the element?
        private boolean deliveredElement = false;

        public WalkThroughIterator() {
            // Is there a 'left' tree?
            if (left != null) {
                iterators.add(left.iterator());
            }
            // a middle
            if (middle != null) {
                iterators.add(middle.iterator());
            }
            // a right
            if (right != null) {
                iterators.add(right.iterator());
            }
        }

        @Override
        public boolean hasNext() {
            // we've finished if we've delivered the element.
            return !deliveredElement;
        }

        @Override
        public E next() {
            // First consume the iterators.
            while (iterators.size() > 0) {
                // Grab the first one.
                Iterator<E> it = iterators.get(0);
                // Has it got an entry?
                if (it.hasNext()) {
                    // Return it's next.
                    return it.next();
                } else {
                    // It's exhaused - remove it.
                    iterators.remove(it);
                }
            }
            // We now deliver our element.
            deliveredElement = true;
            return value;
        }

        @Override
        public void remove() {
            throw new UnsupportedOperationException("remove() is not supported.");
        }

    }

}

public void test() {
    TernaerTree<String> baum = new TernaerTree<String>(new TernaerTree<String>(null, null, null, "Hallo"), new TernaerTree<String>(null, null, null, "Welt"), new TernaerTree<String>(null, null, null, "?"), "!");
    for (String s : baum) {
        System.out.println(s);
    }
}

我有一种感觉，您描述的需求是错误的，因为我希望该元素出现在 right 分支之前，但这是可以修复的。