Java二叉树preorderNext等遍历下一个节点功能异常求助

问题描述 #

实现二叉树并编写preorderNext、postorderNext、inorderNext函数，返回指定节点在对应遍历序列中的下一个节点。当前代码无编译错误，但返回结果错误，已确认searchR能正确找到目标节点，且不能使用集合类，需排查问题。

代码实现 #

BinaryTree类（含推测的Node定义） #

class Node {
    int value;
    Node left;
    Node right;
    Node parent;
    
    Node(int value) {
        this.value = value;
        this.left = null;
        this.right = null;
        this.parent = null;
    }
}

public class BinaryTree {
    Node root;
    
    private Node addR(Node c, int x) {
        if (c == null) {
            return new Node(x);
        }
        if (x < c.value) {
            c.left = addR(c.left, x);
        }
        else if (x > c.value) {
            c.right = addR(c.right, x);
        }
        else {
            return c;
        }
        return c;
    }
    
    public void add(int x) {
        root = addR(root, x);
    }
    
    public Node preorderNext(Node n) {
        if (n.left != null) {
            System.out.println(n.left.value);
            return n.left;
        }
        else if (n.right != null) {
            System.out.println(n.right.value);
            return n.right;
        }
        else {
            System.out.println("Empty");
            return null;
        }
    }
    
    public Node postorderNext(Node root, Node n) {
        if (n == root) {
            System.out.println("Empty");
            return null;
        }
        Node parent = n.parent;
        if(parent.right == null || parent.right == n) {
            System.out.println(parent.value);
            return parent;
        }
        Node c = parent.right;
        while (c.left != null) {
            System.out.println(c.left);
            c = c.left;
        }
        System.out.println(c.value);
        return c;
    }
    
    public Node inorderNext(Node root, Node n) {
        if (n.right != null) {
            System.out.println(n.right.value);
            return minValue(n.right);
        }
        Node p = n.parent;
        while (p != null && n == p.right) {
            n=p;
            p=p.parent;
        }
        System.out.println(p.value);
        return p;
    }
    
    Node minValue(Node n) {
        Node c = n;
        while (c.left != null) {
            c = c.left;
        }
        return c;
    }
    
    public Node searchR(Node c, int x) {
        if(c==null) {
            return null;
        }
        if (x==c.value) {
            return c;
        }
        if (x<c.value) {
            c.left = searchR(c.right, x);
        }
        c.right = searchR(c.right, x);
        return c;
    }
}

主方法 #

public static void main(String[] args) {
    BinaryTree test = new BinaryTree();
    test.add(7);
    test.add(5);
    test.add(6);
    test.add(9);
    test.add(3);
    test.add(8);
    test.preorderNext(test.searchR(test.root, 5));
    test.postorderNext(test.root, test.searchR(test.root, 5));
    test.inorderNext(test.root, test.searchR(test.root, 5));
}

问题排查与修复 #

1. searchR方法逻辑与结构破坏错误 #

当前实现会错误修改树结构，且查找方向完全错误：

• 查找左子树时错误调用searchR(c.right, x)，应为searchR(c.left, x)
• 错误将查找结果赋值给c.left/c.right，会覆盖原有节点，破坏树结构
• 未处理x>c.value的独立分支

修复后的searchR：

public Node searchR(Node c, int x) {
    if (c == null) {
        return null;
    }
    if (x == c.value) {
        return c;
    } else if (x < c.value) {
        return searchR(c.left, x);
    } else {
        return searchR(c.right, x);
    }
}

2. addR方法未设置父节点 #

postorderNext、inorderNext依赖parent属性，但当前代码未绑定子节点与父节点的关联，导致parent始终为null。修复addR：

private Node addR(Node c, int x) {
    if (c == null) {
        return new Node(x);
    }
    if (x < c.value) {
        Node leftChild = addR(c.left, x);
        leftChild.parent = c; // 绑定父节点
        c.left = leftChild;
    } else if (x > c.value) {
        Node rightChild = addR(c.right, x);
        rightChild.parent = c; // 绑定父节点
        c.right = rightChild;
    }
    return c;
}

3. preorderNext方法逻辑不完整 #

当前仅处理节点有左/右子节点的情况，未处理叶子节点需要回溯父节点的场景（如测试树中节点3的前序后继应为6，但当前返回null）。修复后：

public Node preorderNext(Node n) {
    // 有左子节点，返回左子节点
    if (n.left != null) {
        return n.left;
    }
    // 有右子节点，返回右子节点
    if (n.right != null) {
        return n.right;
    }
    // 叶子节点，回溯父节点找未访问的右分支
    Node parent = n.parent;
    while (parent != null) {
        if (parent.left == n && parent.right != null) {
            return parent.right;
        }
        n = parent;
        parent = parent.parent;
    }
    // 是遍历的最后一个节点
    return null;
}

4. inorderNext方法空指针风险 #

当节点是中序遍历的最后一个节点时，p会变为null，执行System.out.println(p.value)会触发空指针异常。修复后：

public Node inorderNext(Node n) {
    if (n.right != null) {
        return minValue(n.right);
    }
    Node p = n.parent;
    while (p != null && n == p.right) {
        n = p;
        p = p.parent;
    }
    // 避免空指针
    if (p != null) {
        System.out.println(p.value);
    } else {
        System.out.println("Empty");
    }
    return p;
}

5. postorderNext方法调试打印错误 #

代码中System.out.println(c.left);打印的是Node对象引用而非节点值，可修改为：

while (c.left != null) {
    // System.out.println(c.left.value); // 可选调试打印
    c = c.left;
}

测试验证 #

修复后，测试树的遍历序列为：

• 前序：7 →5 →3 →6 →9 →8
• 中序：3 →5 →6 →7 →8 →9
• 后序：3 →6 →5 →8 →9 →7

调用对应方法可得到正确结果：

• preorderNext(5) 返回3
• postorderNext(5) 返回8
• inorderNext(5) 返回6

内容的提问来源于stack exchange，提问作者Dash Harber