二进制搜索树迭代器 - 在/前/后/顺序

我有一个类BinarySearchTree它有两个数据元素，Node root和int size。类别Node具有四个数据元素Node left, right, up和int data。二进制搜索树迭代器 - 在/前/后/顺序

我想创建一个Iterator类，它的构造函数接受它将要使用的遍历类型。只有在调用next时，它才会遍历下一个元素。

MyIterator应该在MyIterator中应该包含哪些数据元素，以免混乱？我想也许有Stack<Node>，但这感觉像一个非常糟糕的解决方案。我能做些什么来掩盖所有三种可能的模式？没有任何方法可以在Iterator内部没有额外的数据结构（队列/堆栈/映射）的情况下做到这一点？

public class MyIterator 
{ 
    private BinarySearchTree tree; 
    private Node current; 
    private int mode; 

    public MyIterator(BinarySearchTree tree, int mode) 
    { 
     // mode = 1 -> IN ORDER TRAVERSAL 
     // mode = 2 -> PREORDER TRAVERSAL 
     // mode = 3 -> POSTORDER TRAVERSAL 

     this.tree = tree; 
     this.mode = mode; 
    } 

    public boolean hasNext() 
    { 
     ... 
    } 

    public void next() 
    { 
     ... 
    } 
}

来源

2017-06-21 Hatefiend

莫里斯Inorder树遍历和它的变化是我正在寻找的结构/算法。

来源

2017-06-21 11:26:12 Hatefiend

您的问题听起来像是战略模式的用例。你的迭代器的构造函数应该获得实际的ModeStrategy作为参数而不是普通的int。该策略存储在类属性中。 ModeStrategy可能是一种接口看起来像这样：

public interface ModeStrategy { 
    boolean hasNext(BinarySearchTree tree, Node current); 
    void next(BinarySearchTree tree, Node current); 
} 

public class MyIterator { 
    private final ModeStrategy mode; 
    // other fields omitted 
    public MyIterator(BinarySearchTree tree, ModeStrategy mode) { 
     this.mode = mode; 
    } 
    // your methods delegate to mode 
}

来源

2017-06-21 07:36:54 Markus

这是我的意图，但我正在使用'int'来简化问题到核心问题，这是数据元素/算法将进入迭代器 – Hatefiend

最好的办法是引入一个工厂模式以及实现拆分为自己的Iterator秒。

final class IteratorFactory { 
    enum Mode { 
    IN_ORDER, PRE_ORDER, POST_ORDER; 
    } 

    private IteratorFactory() { 
    } 

    public static <T> Iterator<T> get(Mode mode, BinarySearchTree<T> tree) { 
    Objects.requireNonNull(mode); 
    Objects.requireNonNull(tree); 
    switch(mode) { 
     case IN_ORDER: return new InOrderIterator<T>(tree); 
     case PRE_ORDER: return new PreOrderIterator<>(tree); 
     case POST_ORDER: return new PostOrderIterator<>(tree); 
     default: throw new AssertionError("Can't happen"); 
    } 
    } 

    private static class InOrderIterator<T> implements Iterator<T> { 
    //... 
    } 
    private static class PreOrderIterator<T> implements Iterator<T> { 
    //... 
    } 
    private static class PostOrderIterator<T> implements Iterator<T> { 
    //... 
    } 
}

来源

2017-06-21 07:44:30 Flown

我宁愿不拆分实现。相反，我宁愿有实例变量来涵盖所有情况的需求。这是出于问题范围之外的原因。 – Hatefiend

你在问MyIterator中应该包含哪些数据元素，以免混乱？如果你不分担你的担忧，那已经是凌乱的恕我直言。 – Flown

二进制搜索树迭代器 - 在/前/后/顺序

回答

相关问题