在二叉树中查找节点的父节点

Question

我正在尝试编写一个方法来查找给定节点的父节点.这是我的方法.
我创建了一个BinaryNode最初引用root 的对象r.

    public BinaryNode r=root;
    public BinaryNode parent(BinaryNode p){
    BinaryNode findParent=p;        
        if (isRoot(findParent) || r==null){
                return null;
        }
        else{
            if(r.left==findParent || r.right==findParent)
                return r;
            else{
                if (r.element<findParent.element)
                    return parent(r.right);
                else
                    return parent(r.left);
            }
        }
    }  

这段代码不能正常工作.我认为这是因为r是一个空对象.因为当我这样做

if (isRoot(findParent) || r==null){
                System.out.println(r==null);
                return null;}  

r==null评估为true.如何发生,因为我已插入节点

public static void main (String args[]){
        BinaryTree t=new BinaryTree();
        t.insert(5);
        t.insert(t.root,4);
        t.insert(t.root,6);
        t.insert(t.root,60);
        t.insert(t.root,25);
        t.insert(t.root,10);  

并且root不为null.
有人可以指出为什么会发生这种情况,以及我为了找到父节点而尝试做的事情在逻辑上是否正确.

Answer 1

问题是你必须跟踪当前节点,同时保持你想要找到的父节点.据我了解你的代码,你保留变量,但从不改变它
我建议使用辅助函数.这看起来像这样:

public BinaryNode parent(BinaryNode p){
    parentHelper(root,p)
}
private BinaryNode parentHelper(BinaryNode currentRoot, BinaryNode p) {        
    if (isRoot(p) || currentRoot==null){
            return null;
    }
    else{
        if(currentRoot.left==p || currentRoot.right==p)
            return currentRoot;
        else {
            if (currentRoot.element<p.element) {
                return parentHelper(currentRoot.right,p);
            }
            else {
                return parentHelper(currentRoot.left,p);
            }
        }
    }
}