公众号merlinsea
- 迭代器
- 对于底层存储结构不是顺序存储的数据集合而言，遍历这样的数据结构最好使用迭代器遍历。
- 迭代器中就好比有一个指针，这个指针是会随着我们的遍历跟着我们动态移动的，因此java中针对LinkedList，HashMap这种数据结构推荐使用迭代器进行遍历。
- 二叉树迭代器
- 二叉树的迭代器遍历这颗二叉树是有一定顺序的，一旦我们创建了这个迭代器，那么就只能按照这个顺序进行遍历。比如我们创建了一个先序遍历迭代器，那就只能按照先序遍历的规则来进行迭代。
- 迭代器的设计要饱含初始化功能，正向遍历、反向遍历，判断是否有下一个元素的操作。
- 当迭代器中涉及两个相反方向遍历的时候，最好是使用栈这种数据结构来保存之前的遍历信息【相当于存储快照】，需要注意的是，我们所有这些信息都会随着我们的遍历操作进行动态更新
- 先序遍历的迭代器代码实现
public class PreOrderIterator { private Stack<BTNode> stack; // 存的是上一次输出节点快照 private Stack<BTNode> lastOutputNodeStack; public PreOrderIterator(BTNode root){ stack = new Stack<>(); lastOutputNodeStack = new Stack<>(); if(root != null){ stack.push(root); lastOutputNodeStack.push(null); } } public boolean hasNext(){ // stack 为空 ---> true --> 没有next ---》 false return !stack.isEmpty(); } public BTNode next(){ BTNode top = stack.pop(); if(top.right!=null){ stack.push(top.right); } if(top.left!=null){ stack.push(top.left); } lastOutputNodeStack.push(top); return top; } public boolean hasPre(){ BTNode pre = lastOutputNodeStack.peek(); return pre != null; } public BTNode pre(){ // 删除之前入栈的节点 BTNode lastOutputNode = lastOutputNodeStack.peek(); if(lastOutputNode.left!=null){ stack.pop(); } if(lastOutputNode.right!=null){ stack.pop(); } stack.push(lastOutputNode); // 更新一下lastOutputNodeStack; return lastOutputNodeStack.pop(); } }
- 中序遍历迭代器代码实现
public class InOrderIterator { private Stack<BTNode> stack; private Stack<BTNode> lastOutputNodeStack; public InOrderIterator(BTNode root){ stack = new Stack<>(); lastOutputNodeStack = new Stack<>(); BTNode p = root; while(p!=null){ stack.push(p); p = p.left; } lastOutputNodeStack.push(null); } public boolean hasNext(){ return !stack.isEmpty(); } public BTNode next(){ BTNode p = stack.pop(); BTNode node = p.right; // 为了方便下一次直接输出 while(node != null){ stack.push(node); node = node.left; } lastOutputNodeStack.push(p); return p; } public boolean hasPre(){ BTNode pre = lastOutputNodeStack.peek(); return pre != null; } public BTNode pre(){ // 获取之前的输出节点 BTNode pre = lastOutputNodeStack.pop(); // 将stack恢复原状 BTNode p = pre.right; while(p!=null){ stack.pop(); p = p.left; } stack.push(p); return pre; } }
- 后序遍历迭代器代码实现
public class PostOrderIterator { // 线性复杂度 private Stack<BTNode> stack; private Stack<BTNode> lastOutputNodeStack; public PostOrderIterator(BTNode root){ stack = new Stack<>(); lastOutputNodeStack = new Stack<>(); BTNode p = root; while(p!=null){ stack.push(p); p = p.left; } lastOutputNodeStack.push(null); } public boolean hasNext(){ //stack.isEmpty()---> true ---> 空 ---》 没有下一个节点---》 fasle return !stack.isEmpty(); } public BTNode next(){ BTNode p = stack.peek(); if(p.right == null || p.right == lastOutputNodeStack.peek()){ stack.pop(); lastOutputNodeStack.push(p); return p; } // 先处理p的右子树 ---》 递归 ---》 尾递归 ---》 迭代 while(p.right!=null){ p = p.right; while(p!=null){ stack.push(p); p = p.left; } p = stack.peek(); } p = stack.pop(); lastOutputNodeStack.push(p); return p; } public boolean hasPre(){ BTNode pre = lastOutputNodeStack.peek(); return pre != null; } public BTNode pre(){ BTNode lastOutputNode = lastOutputNodeStack.pop(); // 把stack恢复到原状 if(lastOutputNode.right == null || lastOutputNode.right == lastOutputNodeStack.peek()){ stack.push(lastOutputNode); return lastOutputNode; } BTNode p = lastOutputNode; BTNode lastNode = null; while(p.right!=null){ p = p.right; while(p!=null){ lastNode = stack.pop(); p = p.left; } p = stack.peek(); } // 用于处理最后next函数中最后执行pop()的操作 stack.push(lastNode); return lastOutputNode; } }
- Main函数的调用
public class Main { public static void main(String[] args) { BTNode root = create(); // InOrderIterator inOrderIterator = new InOrderIterator(root); // while(inOrderIterator.hasNext()){ // System.out.println(inOrderIterator.next()); // } // System.out.println(); // while(inOrderIterator.hasPre()){ // System.out.println(inOrderIterator.pre()); // } // PreOrderIterator preOrderIterator = new PreOrderIterator(root); // while(preOrderIterator.hasNext()){ // System.out.println(preOrderIterator.next()); // } // System.out.println(); // while(preOrderIterator.hasPre()){ // System.out.println(preOrderIterator.pre()); // } // PostOrderIterator iterator = new PostOrderIterator(root); while(iterator.hasNext()){ System.out.println(iterator.next()); } System.out.println(); while(iterator.hasPre()){ System.out.println(iterator.pre()); } } public static BTNode create(){ BTNode a = new BTNode(0,"A"); BTNode b = new BTNode(1,"B"); BTNode c = new BTNode(2,"C"); BTNode d = new BTNode(3,"D"); BTNode e = new BTNode(4,"E"); BTNode f = new BTNode(5,"F"); BTNode m = new BTNode(6,"M"); BTNode n = new BTNode(7,"N"); a.left = b; a.right = c; b.left = d; c.left = e; c.right = f; // d.right = m; // m.left = n; return a; } }
