在二叉树中查找给定键的 parent

Question

我试图在二叉树（不是 BST）中找到给定键的 parent。这段代码总是 returns null，谁能告诉我问题出在哪里？我认为问题是即使我 return parent，它仍然会 return null。谢谢:)

public Node getParent(int key,Node parent, Node r){
    if(r!=null){
        if(r.iData==key)
            return parent;
        getParent(key, r, r.leftChild);
        getParent(key, r, r.rightChild);
    }
        return null;
}

Answer 1

您正在递归到左右子树，但是当这些调用找到匹配项时您就忽略它。而是做类似

的事情

public Node getParent(int key, Node parent, Node r) {
    if (r!=null) {
        if (r.iData == key)
            return parent;
        Node p;
        p = getParent(key, r, r.leftChild);
        if (p != null)
            return p;
        p = getParent(key, r, r.rightChild);
        if (p != null)
            return p;
    }
    return null;
}

在二叉树中查找给定键的 parent

Find the parent of a given key in Binary Tree

java

tree

binary-tree