Двоичное дерево 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; 
} 

Вы, возможно, придется добавить некоторые проверки ошибок. Поскольку вы возвращаете общий тип, вам может быть отказано в исключении, если оно не найдено или уже находится в корне.