java - 如何找到具有X值的节点的父级

我正在尝试编写一个名为findParent(Int x)的函数，该函数在二进制搜索树中查找具有值x的节点的父节点的值。

main

BSTTest mytree = new BSTTest();

mytree.add(25);
mytree.add(55);
mytree.add(15);
mytree.add(12);
mytree.add(54);
mytree.add(13);
mytree.add(56);
mytree.add(60);
mytree.add(57);
mytree.add(53);

System.out.println("Root: " + mytree.getRoot());
System.out.println("Level: " + mytree.findLevel(13));
System.out.println("Parent: " + mytree.findParent(53));

private class Node{
    private int key;
    private Node left;
    private Node right;
    private Node parent;

    public Node(int x) {// Node constructor
        key = x;
        left = null;
        right =null;
        parent = null;
    }
}

public int findParent(int x) {
    return findParent(root,x);
}

private int findParent(Node N, int x) {
    Node nextNode = null;

    if(x < N.key && N.left != null) {
        nextNode = N.left;
        nextNode.parent = N;
        return findParent(nextNode,x);
    }
    else if(x > N.key && N.right != null) {
        nextNode = N.right;
        nextNode.parent = N;
        return findParent(nextNode, x);
    }
    else if(x < N.key && N.left == null) {
        return N.key;
    }
    else if(x > N.key && N.right ==null) {
        return N.key;
    }
    else {
        return N.parent.key;
    }
}

出于某种原因，当我运行此代码时，我能够在树的左侧获取节点的父级值，但在右侧无法。
例如，当我找到13的父值时，我得到12是正确的，但是当我寻找53的父值时，我得到55而不是54。

最佳答案

该方法应该是只读的。修改其中的父链接有点令人惊讶。代码意外并不是一件好事。

如果我们假设您的其他树修改方法正确地维护了parent链接（您的问题可能是findParent有时没有这样做），并且将该方法设置为只读，那么：

public int findParent(int x) {
        return findParent(root,x);
    }
    private int findParent(Node N, int x) {
        if(x < N.key && N.left != null) {
            return findParent(N.left, x);
        }
        else if(x > N.key && N.right != null) {
            return findParent(N.right, x);
        }
        else if(x != N.key) {
            return N.key;
        }
        else {
            return N.parent.key;
        }
    }

并不是说它实际上需要父链接才能工作：

public int findParent(int x) {
        return findParent(root,x,null);
    }
    private int findParent(Node N, int x, Node parent) {
        if (N == null || N.key == x) {
            if (parent != null) {
                return parent.key;
            } else {
                return ???; // you were asked for parent of root, no idea what result you want here
            }
        }
        if(x < N.key) {
            return findParent(N.left, x, N);
        } else {
            return findParent(N.right, x, N);
        }
    }