实现一个二叉排序树的迭代器

Sat 01 March 2014 by XiaomengZhao

二叉搜索树的中序遍历是有序的。在该篇文章中，我们实现了一个二叉搜索树的迭代器，每次调用该迭代器的next方法可以返回有序的数字。迭代器的好处是，可以对调用者屏蔽底层数据结构的复杂性，调用者不用考虑底层数据存储是用数组实现，还是链表实现，或者是二叉搜索树实现。

Java迭代器需要实现以下接口：

public interface BinaryTreeIterator {
    // Are there other nodes to see in this traversal? 
    boolean hasNext();
    // Return the value of the key in the next node in the 
    // traversal, and advance the position of the iterator.
    TreeNode next();
}

下面就是我们实现了这以借口。对树的中序遍历进行了一些修改。

public class InorderIterator implements BinaryTreeIterator{
    Stack<TreeNode> s = new Stack<TreeNode>();
    public InorderIterator(TreeNode root){
        s.push(root);
        TreeNode temp = root;
        while(temp != null){
            if(temp.left != null){
                s.push(temp.left);
            }
            temp = temp.left;
        }
    }

    @Override
    public boolean hasNext() {
        if(s.isEmpty()){
            return false;
        }
        return true;
    }

    @Override
    public TreeNode next(){
        TreeNode r = s.pop();
        if(r.right == null){
            return r;
        }
        //如果右节点不为空
        s.push(r.right);
        TreeNode temp = r.right;
        while(temp != null){
            if(temp.left != null){
                s.push(temp.left);
            }
            temp = temp.left;
        }
        return r;
    }
}

实现一个二叉排序树的迭代器

Comments