二叉树：有序迭代器：Java

Question

我该如何去编写一个迭代器，以“按顺序”方式遍历二叉树的每个值？我应该使用堆栈。 BinaryNode是一个简单的节点类，指针指向“左”和“右”节点。以下是我迄今为止：

class InOrderIterator implements Iterator<T> { 

    private Stack<BinaryNode> stack; 

    public InOrderIterator(BinarySearchTree<T>.BinaryNode root) { 
     stack = new Stack<BinaryNode>(); 
     stack.push(root); 
    } 

    @Override 
    public boolean hasNext() { 
     while (!this.stack.isEmpty() && stack.peek() == NULL_NODE) 
      this.stack.pop(); 
     return !this.stack.isEmpty(); 
    } 

    @Override 
    public T next() { 
     //TODO 

     if (!this.hasNext()) 
      throw new NoSuchElementException("No more nodes in tree!"); 

     BinaryNode current = this.stack.pop(); 
     BinaryNode output = null; 

     while(current != NULL_NODE){ 
      this.stack.push(current); 
      current = current.left; 
     } 

     if(current == NULL_NODE){ 
      if(!this.stack.isEmpty()){ 
       output = this.stack.pop(); 
       return output.data; 
      } 
     } 
     return null; 
    } 
} 

我有基本的算法了，但我似乎无法将其转换为Java代码。

Answer 1

想想不变式。你有一堆节点。节点在堆栈上意味着什么？

可能我建议：堆栈上的一个节点表示一个“半树”，一个节点及其整个右子树，堆栈保存所有半树，它们组成了所有未返回的节点从下一个（）开始。

那些半棵树应该按什么顺序堆栈？回答这个问题会给你不变的条件，即代码运行时将保留的属性。

让你自己知道你的不变量意味着堆栈的顶端必须是next（）将要返回的下一个。当你弹出它返回时，你将不得不以某种方式在返回之前处理其正确的子树。从你的不变，它应该是显而易见的如何做到这一点。

如果你不自觉地明确地思考你的变量是什么意思以及你的不变量是什么，你的编码工作将会是无向的。你会围绕着写意大利面代码。一旦你完成了这些，代码将自己编写。

Answer 2

public class BinaryTreeNode { 
    private int element; //element stored at this node 

    private BinaryTreeNode left, right; 

    public BinaryTreeNode() { } 

    public BinaryTreeNode(int element) { 
     setElement(element); 
     setLeft(null); 
     setRight(null); 
    } 

    //returns the elements stored at this position 
    public int element() { 
     return element; 
    } 

    //sets the elements stored at this position 
    public void setElement(int e) { 
     element = e; 
    } 

    //return the left child of this position 
    public BinaryTreeNode getLeft() { 
     return left; 
    } 

    //set the left chid of this position 
    public void setLeft(BinaryTreeNode l) { 
     left = l; 
    } 

    //return the right child of this position 
    public BinaryTreeNode getRight() { 
     return right; 
    } 

    //sets the right child of this position 
    public void setRight(BinaryTreeNode r) { 
     right = r; 
    }  

} 

---

public class TestBTN { 

    /** 
    * @param args the command line arguments 
    */ 
    public static void main(String[] args) { 
     BinaryTreeNode root = null, right, left, node = null; 

     int arrayInt[] = {25, 20, 7, 13, 33, 50, 45, 17, 30, 55}; 

     for (int i = 0; i < arrayInt.length; i++) { 
      if (root == null) { 
       root = node = new BinaryTreeNode(arrayInt[0]); 
      }//endIf 
      else { 
       node = new BinaryTreeNode(arrayInt[i]); 
       BinaryTreeNode s, p; 
       p = s = root; 
       while (s != null) { 
        p = s; 
        if (node.element() > s.element()) { 
         s = s.getRight(); 
        } else { 
         s = s.getLeft(); 
        } 
       }//endWhile 
       if (node.element() > p.element()) { 
        p.setRight(node); 
       } else { 
        p.setLeft(node); 
       } 
      }//emdElse 
     }//endFor 

     //printing 
     //Print(root); 
     //PostOrder(root); 
     //PreOrder(root); 
     InOrder(root); 
     //System.out.println("\nBinaryTreeNode"); 

    }//endMain 

    private static void Print(BinaryTreeNode node) { 
     if (node != null) { 
      System.out.print(node.element() + " "); 
      Print(node.getLeft()); 
      Print(node.getRight()); 
     }//endIf 
    }//endPrint 

    static void PostOrder(BinaryTreeNode ptr) { 
     if(ptr != null) { 
      PostOrder(ptr.getLeft()); 
      PostOrder(ptr.getRight()); 
      System.out.print(ptr.element()+" "); 
     }//endIf 
    }//endPost 

    static void PreOrder(BinaryTreeNode ptr) { 
     if(ptr != null) { 
      System.out.print(ptr.element()+" "); 
      PreOrder(ptr.getLeft()); 
      PreOrder(ptr.getRight()); 

     } 
    }   

    static void InOrder(BinaryTreeNode ptr) { 
     if(ptr != null) { 
      InOrder(ptr.getLeft()); 
      System.out.print(ptr.element()+" "); 
      InOrder(ptr.getRight()); 
     } 
    } 
}