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，访问左child并执行第一步 与 child

第二步：节点没有左child（或者我们已经访问过左child），将其添加到inorder list

第三步：第一步右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);
    }
}

问候

Java 中的树迭代器

Tree iterator in Java

java

tree

iterator