java - 如何查找值为 X 的节点的父节点

Question

我正在尝试编写一个名为 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。

Answer 1

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

如果我们假设您的其他树修改方法正确维护了 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);
        }
    }