Найти родителя заданного ключа в двоичном дереве

Question

Я пытаюсь найти родительский элемент данного ключа в двоичном дереве (а не BST). Этот код всегда возвращает значение null, может кто-нибудь сказать, где проблема? Я думаю, проблема в том, что даже если я верну родитель, он все равно вернет 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; 
}