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

Question

所以我想在二叉树中找到一个节点的父节点。假设我通过文本文件在树中输入 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);

}

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

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

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

Answer 1

似乎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);
}