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;
}

您可能需要添加一些错误检查。由于您返回的是泛型类型，因此如果未找到或已经在根目录中，您可能不得不抛出异常。