Java中的樹迭代器

Question

我已經實現了一個代碼，它在樹中添加元素，並按遞增順序打印它們。不過，我的目標是學習迭代器，並希望用迭代器函數替換inOrder()函數。我怎樣才能做到這一點？

import java.util.InputMismatchException; 
import java.util.Scanner; 
import javax.xml.soap.Node; 

class Tree 
{ 
    public final int mVal; 
    public Tree mLeft; 
    public Tree mRight; 
    public Node next; 
    public Tree(int val) 
    { 
     mVal = val; 
    } 
    public void add(int val) 
    { 
     if (val < mVal) 
     { 
      if (mLeft == null) 
      mLeft = new Tree(val); 
     else 
      mLeft.add(val); 
     } 
     else 
     { 
      if (val > mVal) 
      { 
      if (mRight == null) 
      mRight = new Tree(val); 
      else 
      mRight.add(val); 
      } 
     } 
    } 

    public String inOrder() 
    { 
      return ((mLeft == null) ? "" : mLeft.inOrder()) 
      + mVal + " " 
      + ((mRight == null) ? "" : mRight.inOrder()); 
    } 

    public static void main(String[] args) 
    { 
     Tree t = new Tree(8); 
     Scanner scanner = new Scanner(System.in); 
     boolean continueLoop = true; // determines if more input is needed 
     for (int i = 1; i < 9; ++i) 
      { 
      try // read two numbers and calculate quotient 
      { 
      System.out.print("Please enter a random integer : "); 
      int stackInt = scanner.nextInt(); 
      t.add(Integer.valueOf(stackInt)); 
      } // end try 
      catch (InputMismatchException inputMismatchException){ 
      System.err.printf("\nException: %s\n", inputMismatchException); 
      scanner.nextLine(); //discard input so user can try again 
      System.out.println("You must enter integers. Please try again.\n"); 
      } // end catch 
     } 
     System.out.println("Values in order = "+ t.inOrder()); 
    } 
} 

Answer 1

看看這張圖

第一步：如果節點具有左子，請留下孩子和做第一步與孩子

第二步：節點沒有離開孩子（或者我們已經訪問過左邊的孩子），將它添加到inorder list

第三步：第一步與右子

我沒有測試它

@Override 
public String toString() { 
    return String.valueOf(mVal); 
} 
public String inOrder(Tree root) { 
    List<Tree> inOrder = new ArrayList<>(); 
    inOrderRecursively(root, inOrder); 
    return inOrder.toString(); 
} 

private void inOrderRecursively(Tree Node, List<Tree> inOrder) { 
    if (Node.mLeft != null) { 
     inOrderIt(Node.mLeft, inOrder); 
    } 
    inOrder.add(Node); 
    if (Node.mRight != null) { 
     inOrderIt(Node.mRight, inOrder); 
    } 
} 

問候