이진 트리 getParent 함수

Question

노드에서 재귀 적으로 검색하고 발견 된 노드가있는 경우 하위 노드가있는 노드를 반환합니다. 그렇지 않으면 0을 반환합니다.

Node<T> * BinaryTree<T>::searchParent (T key , Node<T> * p) const 
{ 
    if (p == 0) 
     return 0; 

    if (p->left && p->left->info == key) 
     return p; 
    else if (p->right && p->right->info == key ) 
     return p; 

    Node<T> * q = searchParent (key , p->left); 

    if (q == 0) 
     return searchParent (key , p->right); 

    return q; 
} 

지금 난 단지 노드 데이터가 주어진다면, 찾아 주어진 노드의 부모의 데이터를 반환이 기능을 구현합니다.

T BinaryTree<T>::getParent(T node) 

그러나 재귀 적으로 또는 비 반복적으로 구현할 수 없습니다.

Answer 1

기본적인 아이디어는 :

T BinaryTree<T>::getParent(T node) 
{ 
    return searchParent(node, root)->info; 
} 

당신은 몇 가지 오류 검사를 추가 할 수 있습니다. 제네릭 형식을 반환하기 때문에 찾을 수 없거나 이미 루트에있는 경우 예외를 throw해야합니다.