c++ - 二分木 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;
}

エラーチェックを追加する必要がある場合があります。ジェネリック型を返すため、見つからない場合、または既にルートにある場合は、例外をスローする必要がある場合があります。