查找二叉搜索树中某个节点的父节点

所以我想找到二叉树中一个Node的父节点。 假设我通过文本文件在树中输入30,15,17,45,69,80,7。

这棵树应该是

                 30
             15       45
          7      17       69
                               80

这是我的代码：

Node*  BST::searchforparentnode(Node* pRoot, int value)
{
   if(pRoot->pleft == NULL && pRoot->pright == NULL)
    return NULL;

   if(pRoot->pleft->value == value || pRoot->pright->value == value)
    return pRoot;

   if(pRoot->value > value)
    return searchforparentnode(pRoot->pleft,value);

   if(pRoot->value < value)
    return searchforparentnode(pRoot->pright,value);

}

在这种情况下，我不考虑用户是否输入根节点的值。

事情是，当我输入 15,17,7，根节点左分支中的所有值时，结果都正常。但是当我想从右分支 (69,80) 找到除 45 之外的值的父节点时，程序停止运行。

知道是什么导致了这个错误吗？谢谢阅读。

看起来45没有left节点，它是NULL，所以检查pRoot->pleft->value == value是未定义的行为。

             30
            /  \
         15     45
        /   \     \
      7      17    69
                     \
                      80

所以你需要做一个检查，比如：

Node*  BST::searchforparentnode(Node* pRoot, int value)
{
    if(pRoot->pleft == NULL && pRoot->pright == NULL)
       return NULL;

    if( (pRoot->pleft != NULL && pRoot->pleft->value == value)
        || (pRoot->pright != NULL && pRoot->pright->value == value))
       return pRoot;

    if(pRoot->value > value)
       return searchforparentnode(pRoot->pleft,value);

    if(pRoot->value < value)
       return searchforparentnode(pRoot->pright,value);
}

然而，另一件事要检查的是如果pRoot本身就是NULL:

Node*  BST::searchforparentnode(Node* pRoot, int value)
{
    if (pRoot == NULL)
       return NULL;

    if(pRoot->pleft == NULL && pRoot->pright == NULL)
       return NULL;

    if( (pRoot->pleft != NULL && pRoot->pleft->value == value)
        || (pRoot->pright != NULL && pRoot->pright->value == value))
       return pRoot;

    if(pRoot->value > value)
       return searchforparentnode(pRoot->pleft,value);

    if(pRoot->value < value)
       return searchforparentnode(pRoot->pright,value);
}