我需要帮助在 Java 中为二叉搜索树创建 getNextItem 方法

Question

我有一个 public Comparable getNextItem(int orderType) 方法，我用它来调用其中的许多方法，但它对我来说不能正常工作。我在 JUnit 测试中测试它失败了。我还提供了我收到的错误代码。

public Comparable getNextItem(int orderType) {
    TreeNode current = root;
    if (current == null) {
        return null;
    }
    TreeNode result = root;
    switch (orderType) {
        case INORDER: // In-order
            result = inOrderSuccessor(current, current);
            break;
        case PREORDER: // Pre-order
            result = preOrderSuccessor(current, current);
            break;
        case POSTORDER: // Post-order
            result = postOrderSuccessor(current, current);
            break;
    }
    return result.data;
}

TreeNode inOrderSuccessor(TreeNode root, TreeNode n) {
    if (n.right != null) {
        return minValue(n.right);
    }
    TreeNode p = n.parent;
    while (p != null && n == p.right) {
        n = p;
        p = p.parent;
    }
    return p;
}

TreeNode minValue(TreeNode node) {
    TreeNode current = node;
    while (current.left != null) {
        current = current.left;
    }
    return current;
}

TreeNode preOrderSuccessor(TreeNode root, TreeNode n) {
    if (n.left != null)
        return n.left;

    if (n.right != null)
        return n.right;
    TreeNode curr = n, parent = curr.parent;
    while (parent != null && parent.right == curr) {
        curr = curr.parent;
        parent = parent.parent;
    }
    if (parent == null)
        return null;
    return parent.right;
}

TreeNode postOrderSuccessor(TreeNode root, TreeNode n) {
    if (n == root)
        return null;

    TreeNode parent = n.parent;
    if (parent.right == null || parent.right == n)
        return parent;

    TreeNode curr = parent.right;
    while (curr.left != null)
        curr = curr.left;

    return curr;
}

public void reset(int orderType) {
    if (root == null) {
        return;
    }
    switch (orderType) {
        case PREORDER:
            current = root;
            break;
        case INORDER:
            TreeNode node = root;
            while (node.left != null) {
                node = node.left;
            }
            current = node;
            break;
        case POSTORDER:
            node = root;
            while (node.right != null) {
                node = node.right;
            }
            current = node;
            break;
    }
}

import static org.junit.Assert.*;
import org.junit.Test;

public class BSTImplTest6 {


    @Test
    public void testReset() {
        BSTImpl bst = new BSTImpl();
        bst.insert(5);
        bst.insert(3);
        bst.insert(8);
        bst.insert(1);

        bst.reset(BSTInterface.INORDER);
        assertEquals(1, bst.getNextItem(BSTInterface.INORDER));
        assertEquals(3, bst.getNextItem(BSTInterface.INORDER));
        assertEquals(5, bst.getNextItem(BSTInterface.INORDER));
        assertEquals(8, bst.getNextItem(BSTInterface.INORDER));

        bst.reset(BSTInterface.PREORDER);
        assertEquals(5, bst.getNextItem(BSTInterface.PREORDER));
        assertEquals(3, bst.getNextItem(BSTInterface.PREORDER));
        assertEquals(1, bst.getNextItem(BSTInterface.PREORDER));
        assertEquals(8, bst.getNextItem(BSTInterface.PREORDER));

        bst.reset(BSTInterface.POSTORDER);
        assertEquals(1, bst.getNextItem(BSTInterface.POSTORDER));
        assertEquals(3, bst.getNextItem(BSTInterface.POSTORDER));
        assertEquals(8, bst.getNextItem(BSTInterface.POSTORDER));
        assertEquals(5, bst.getNextItem(BSTInterface.POSTORDER));
    }

}

这是错误代码

java.lang.AssertionError: 预期：1 实际：8

at org.junit.Assert.fail(Assert.java:89)
at org.junit.Assert.failNotEquals(Assert.java:835)
at org.junit.Assert.assertEquals(Assert.java:120)
at org.junit.Assert.assertEquals(Assert.java:146)
at a4.BSTImplTest6.testReset(BSTImplTest6.java:17)
at java.base/jdk.internal.reflect.DirectMethodHandleAccessor.invoke(DirectMethodHandleAccessor.java:104)
at java.base/java.lang.reflect.Method.invoke(Method.java:578)
at org.junit.runners.model.FrameworkMethod$1.runReflectiveCall(FrameworkMethod.java:59)
at org.junit.internal.runners.model.ReflectiveCallable.run(ReflectiveCallable.java:12)
at org.junit.runners.model.FrameworkMethod.invokeExplosively(FrameworkMethod.java:56)
at org.junit.internal.runners.statements.InvokeMethod.evaluate(InvokeMethod.java:17)
at org.junit.runners.ParentRunner$3.evaluate(ParentRunner.java:306)
at org.junit.runners.BlockJUnit4ClassRunner$1.evaluate(BlockJUnit4ClassRunner.java:100)
at org.junit.runners.ParentRunner.runLeaf(ParentRunner.java:366)
at org.junit.runners.BlockJUnit4ClassRunner.runChild(BlockJUnit4ClassRunner.java:103)
at org.junit.runners.BlockJUnit4ClassRunner.runChild(BlockJUnit4ClassRunner.java:63)
at org.junit.runners.ParentRunner$4.run(ParentRunner.java:331)
at org.junit.runners.ParentRunner$1.schedule(ParentRunner.java:79)
at org.junit.runners.ParentRunner.runChildren(ParentRunner.java:329)
at org.junit.runners.ParentRunner.access$100(ParentRunner.java:66)
at org.junit.runners.ParentRunner$2.evaluate(ParentRunner.java:293)
at org.junit.runners.ParentRunner$3.evaluate(ParentRunner.java:306)
at org.junit.runners.ParentRunner.run(ParentRunner.java:413)
at org.junit.runner.JUnitCore.run(JUnitCore.java:137)
at com.intellij.junit4.JUnit4IdeaTestRunner.startRunnerWithArgs(JUnit4IdeaTestRunner.java:69)
at com.intellij.rt.junit.IdeaTestRunner$Repeater$1.execute(IdeaTestRunner.java:38)
at com.intellij.rt.execution.junit.TestsRepeater.repeat(TestsRepeater.java:11)
at com.intellij.rt.junit.IdeaTestRunner$Repeater.startRunnerWithArgs(IdeaTestRunner.java:35)
at com.intellij.rt.junit.JUnitStarter.prepareStreamsAndStart(JUnitStarter.java:235)
at com.intellij.rt.junit.JUnitStarter.main(JUnitStarter.java:54)

进程结束，退出代码为 -1