实现一个二叉排序树的迭代器
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;
}
}
树的前中后的非递归遍历
Sat 01 March 2014
by XiaomengZhao
树的前序遍历
没从栈中取出一个元素，就visit该元素，然后先压栈它的右元素，然后压栈它的左元素。因为栈是先进后出，左元素肯定要比右元素先出来。
public class PreOrderTraversal {
public List<Integer> preorderTraversal(TreeNode root) {
// write your code here
ArrayList<Integer> result = new ArrayList<Integer>();
if(root == null)
return null;
Stack<TreeNode> s = new Stack<TreeNode>();
s.push(root);
while(s.size() != 0){
TreeNode p = s.pop();
s.add ...实现一个二叉排序树的迭代器
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 ...