Java二叉搜索树reset方法实现：正确性验证与测试求助

需求说明 #

为给定的遍历类型（中序in-order、前序pre-order、后序post-order）重置或初始化二叉搜索树的当前节点指针。假设树中至少存在一个元素，需根据遍历类型的起始位置设置指针，函数仅接受int类型的orderType作为参数。

已编写的代码 #

public class BinarySearchTree {
    TreeNode root;
    TreeNode current;

    public class TreeNode {
        Comparable data;
        TreeNode left;
        TreeNode right;

        public TreeNode(Comparable data) {
            this.data = data;
            this.left = null;
            this.right = null;
        }
    }

    public static final int INORDER = 1;
    public static final int PREORDER = 2;
    public static final int POSTORDER = 3;

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

代码正确性分析 #

• 前序遍历（PREORDER）：处理正确。前序遍历的第一个节点就是树的根节点，将current设为root符合要求。
• 中序遍历（INORDER）：处理正确。二叉搜索树的中序遍历顺序是左子树->根->右子树，第一个节点是整个树的最左叶子节点，代码中循环找最左节点的逻辑没问题。
• 后序遍历（POSTORDER）：处理错误。后序遍历顺序是左子树->右子树->根，第一个节点并不是最右节点，而是整个树的最左下叶子节点（若左子树存在）；若左子树不存在，则找右子树的最左下叶子节点；若左右子树都不存在则是根节点。当前代码直接找最右节点，会在多数场景下导致current指向错误节点。比如构造带左子树的二叉搜索树时，后序遍历第一个节点是最左叶子，但代码会指向最右节点，完全不符合预期。

修正后的后序遍历初始化逻辑 #

要找到后序遍历的第一个节点，需循环遍历到最左下的叶子节点，修正代码如下：

case POSTORDER:
    TreeNode node = root;
    // 优先遍历左子树，再遍历右子树，直到找到叶子节点
    while (true) {
        if (node.left != null) {
            node = node.left;
        } else if (node.right != null) {
            node = node.right;
        } else {
            // 找到叶子节点，终止循环
            break;
        }
    }
    current = node;
    break;

测试方案 #

通过构造不同结构的二叉搜索树，调用reset方法后验证current是否符合对应遍历的第一个节点：

测试用例1：单节点树 #

• 树结构：仅根节点5
• 预期结果：
  • 调用reset(PREORDER)，current.data为5
  • 调用reset(INORDER)，current.data为5
  • 调用reset(POSTORDER)，current.data为5

测试用例2：仅左子树的树 #

• 树结构：5 -> 3 -> 2（5为根，左子节点3，3的左子节点2）
• 预期结果：
  • reset(PREORDER)：current.data为5
  • reset(INORDER)：current.data为2
  • reset(POSTORDER)：current.data为2

测试用例3：仅右子树的树 #

• 树结构：5 -> 6 -> 7（5为根，右子节点6，6的右子节点7）
• 预期结果：
  • reset(PREORDER)：current.data为5
  • reset(INORDER)：current.data为5
  • reset(POSTORDER)：current.data为7

测试用例4：完整二叉搜索树 #

• 树结构：

  5
     / \
    3   7
   / \   \
  2   4   8
  

• 预期结果：
  • reset(PREORDER)：current.data为5
  • reset(INORDER)：current.data为2
  • reset(POSTORDER)：current.data为2

测试代码示例 #

可以编写JUnit测试类来自动化验证：

import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.*;

public class BinarySearchTreeTest {
    private BinarySearchTree bst;

    @BeforeEach
    void setUp() {
        bst = new BinarySearchTree();
    }

    @Test
    void testSingleNodeTree() {
        bst.root = bst.new TreeNode(5);
        bst.reset(BinarySearchTree.PREORDER);
        assertEquals(5, bst.current.data);

        bst.reset(BinarySearchTree.INORDER);
        assertEquals(5, bst.current.data);

        bst.reset(BinarySearchTree.POSTORDER);
        assertEquals(5, bst.current.data);
    }

    @Test
    void testLeftSubtreeOnly() {
        bst.root = bst.new TreeNode(5);
        bst.root.left = bst.new TreeNode(3);
        bst.root.left.left = bst.new TreeNode(2);

        bst.reset(BinarySearchTree.PREORDER);
        assertEquals(5, bst.current.data);

        bst.reset(BinarySearchTree.INORDER);
        assertEquals(2, bst.current.data);

        bst.reset(BinarySearchTree.POSTORDER);
        assertEquals(2, bst.current.data);
    }
}

内容的提问来源于stack exchange，提问作者Marcus Availo