Java 中有 3 children 的树的迭代器实现

Question

对于大学，我应该将接口迭代器实现为具有 3 Children 的树的内部 Class。我对树的实现如下所示：

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

我建议你让 TernaerTree 实现可迭代。那会让事情变得容易得多。您可以 return iterator() 中的 WalkThroughIterator 迭代器，您将为 iterable 实现该迭代器。这样就少了很多混乱。

那么你就可以把树的所有基本功能都作为TernaerTree的一部分。

Answer 2

最简单的方法（如果你不太关心复杂性/性能），你可以添加一个构造函数并按照你想要的递归顺序构建节点的线性 AST（例如，列表）。

public class WalkThroughIterator implements Iterator {

    private List<E> values = new ArrayList<E>();
    private int currentElement = 0;

    public WalkThroughIterator(TernaerTree<E> tree) {
        buildList(tree);
    }

    private void buildList(TernaerTree<E> node) {

        if (node == null)
            return;

        buildList(node.left); //probably be best to add a getLeft() method etc
        buildList(node.middle);
        buildList(node.right);
        values.add(node.getValue());
    }

    @Override
    public boolean hasNext() {
        return (currentElement < values.size());
    }

    @Override
    public Object next() {
        return values.get(currentElement++);
    }

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

}

然后只需将 getIterator 方法添加到您的树对象中即可：

public WalkThroughIterator getIterator() {
       return new WalkThroughIterator(this);
}

或者简单地用根实例化一个新的 WalkThroughIterator 对象。

（顺便说一句，请注意，如果您让对象实现 Iterable 然后按照上面的建议实现，您可以使用 for-each 循环遍历树。）

Answer 3

这似乎可行 - 它使用 iterator 的列表来跟踪内部树。一旦所有这些都耗尽，它就会发出元素。

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 分支之前出现，但这是可以修复的。

Java 中有 3 children 的树的迭代器实现

Iterator implementation for tree with 3 children in Java

java

tree

iterator