java - 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

看这张图

第一步:如果节点有左子节点，则访问左子节点并对该子节点执行第一步

第二步:节点没有左子节点(或者我们已经访问过左子节点)，将其添加到中序列表

第三步:第一步右 child

我没有测试

@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);
    }
}

问候