在二叉搜索樹中找到節點的父節點

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