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

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

}

在这种情况下，我没有考虑到根如果用户输入的值节点。

事情是，当我输入15,17,7，根节点左分支的所有值，它出来了。但是当我想从右分支（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); 
} 

Answer 2

你的问题是：

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

因为在检查之前是否还有AND权利为空。在上面提到的部分，一个可能是空

您也许想改变你的代码是这样的：

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

    //Added check 
    if(pRoot->pleft && pRoot->pleft->value == value) 
    return pRoot; 

    //Added check 
    if(pRoot->pright && pRoot->pright->value == value) 
    return pRoot; 

    //Check also needed here 
    if(pRoot->pleft && pRoot->value > value) 
    return searchforparentnode(pRoot->pleft,value); 

    //Check also needed here 
    if(pRoot->pright && pRoot->value < value) 
    return searchforparentnode(pRoot->pright,value); 

} 

恕我直言：您还可以创建一个指向每个节点的父节点。这可能会加速某些事情！

Answer 3

public Node nodeParent(Node root, Node n){ 
     if(root==null){ 
      return null; 
     } 
     Node p=root; 
     if(p.left==null && p.right==null){ 
      return null; 
     } 
     if(p.left!=null && p.key>n.key){ 
      p=p.left; 
      if(p.left.key==n.key){ 
      return p; 
     } 
     } 
     if(p.right!=null && p.key<n.key){ 
      p=p.right; 
      if(p.right.key==n.key){ 
      return p; 
     } 
     } 
     if(p.left!=null && p.right!=null){ 
      if(p.key<n.key){ 
       p=p.right; 
      }else{ 
       p=p.left; 
      } 
     } 
     return p; 
    }