如何在getNextItem方法中调用二叉树三种遍历的后继节点函数？

下面是整合了三种遍历后继节点逻辑的完整代码，重点实现了getNextItem方法，同时保留了你已实现的各遍历后继函数：

public class BinaryTree {
    public static final int INORDER = 1;
    public static final int PREORDER = 2;
    public static final int POSTORDER = 3;
    TreeNode root;
    TreeNode currentNode; // 当前节点，用于getNextItem获取其后继

    class TreeNode {
        int data;
        TreeNode left, right, parent;

        TreeNode(int data) {
            this.data = data;
            left = right = parent = null;
        }
    }

    TreeNode insert(TreeNode node, int data) {
        if (node == null) {
            return (new TreeNode(data));
        } else {
            TreeNode temp = null;

            if (data <= node.data) {
                temp = insert(node.left, data);
                node.left = temp;
                temp.parent = node;
            } else {
                temp = insert(node.right, data);
                node.right = temp;
                temp.parent = node;
            }

            return node;
        }
    }

    public Comparable getNextItem(int orderType) {
        TreeNode successor = null;
        // 基于currentNode获取对应遍历的后继节点
        switch (orderType) {
            case INORDER:
                successor = inOrderSuccessor(currentNode);
                break;
            case PREORDER:
                successor = preorderSuccessor(currentNode);
                break;
            case POSTORDER:
                successor = postorderSuccessor(currentNode);
                break;
            default:
                throw new IllegalArgumentException("无效的遍历类型");
        }
        // 后继存在则返回其数据（自动装箱为Integer，实现Comparable），否则返回null
        return successor != null ? successor.data : null;
    }

    TreeNode inOrderSuccessor(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 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 n) {
        if (n == null)
            return null;

        TreeNode parent = n.parent;
        if (parent == null) // 处理根节点没有后继的情况
            return null;
            
        if (parent.right == null || parent.right == n)
            return parent;

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

        return curr;
    }


    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();
        TreeNode root = null, temp = null;
        root = tree.insert(root, 20);
        root = tree.insert(root, 8);
        root = tree.insert(root, 22);
        root = tree.insert(root, 4);
        root = tree.insert(root, 12);
        root = tree.insert(root, 10);
        root = tree.insert(root, 14);
        
        temp = root.left.right.right; // 节点14
        tree.currentNode = temp; // 设置当前节点
        
        // 使用getNextItem测试三种遍历的后继
        Integer inSuc = (Integer) tree.getNextItem(BinaryTree.INORDER);
        System.out.println("Inorder successor of " + temp.data + " is " + inSuc);
        
        Integer preSuc = (Integer) tree.getNextItem(BinaryTree.PREORDER);
        System.out.println("Preorder successor of " + temp.data + " is " + preSuc);
        
        Integer postSuc = (Integer) tree.getNextItem(BinaryTree.POSTORDER);
        System.out.println("Postorder successor of " + temp.data + " is " + postSuc);
    }
}

关键实现说明 #

1. getNextItem方法逻辑：
   • 利用类成员变量currentNode作为当前遍历节点，无需额外传入节点参数；
   • 根据orderType分支调用对应的后继节点函数；
   • 处理后继节点为null的边界情况，返回null；
   • 返回值为Comparable，利用Java自动装箱将int转为Integer实现该接口。
2. 修复的细节：
   • 移除了TreeNode中冗余的root成员变量（原代码中未使用）；
   • 在postorderSuccessor中增加了根节点无父节点的判断，避免空指针异常；
   • 在main方法中新增了currentNode的赋值逻辑，让getNextItem能正确获取当前节点。

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