迭代器 遍历 二叉树

Question

如何实现迭代器的 next（）去前序遍历一个二叉树？最好是线性时间的。

Answer 1

需要用一个栈来保存路径吧假如有个栈A
有个二叉树T
有个printNode(Node n)方法Class BTreeEnum
{
    Tree t;
    Stack A;
    Node n;
    Node nextNode;
    public BTreEnum()
    {
       n=t.root;
       nextNode=n;
    }
    public Node next()
    {
      return nextNode;
      if(nextNode.left!=null)
      {
         nextNode=nextNode.left;
A.add(nextNode);
      }
      else if(nextNode.right!=null)
      {
nextNode=nextNode.right;
A.add(nextNode);
      }
else if(nextNode!=n)
{
nextNode=A.pop().right;
}
nextNode=null;
    }
}这里只是部分的实现，有些还可能不符合语法，但是由于在网吧，只能写到这样了，自己改改应该行的