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

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之外，程序就停止运行了。

各位有什么想法关于这个错误是由什么引起的吗？感谢阅读。

- Hòa Ngô

---

你确定你的树结构构建正确吗？使用调试器来深入了解问题。 - Mat

Answer 1

看起来 45 没有左节点，它是 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);
}

- AndyG

---

谢谢您的帮助。我现在明白了我的问题。 - Hòa Ngô

Answer 2

您的问题是：

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

因为在你检查左侧和右侧是否为空之前，上面提到的部分可能会为空。

你可能希望将代码更改为以下内容：

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

}

个人认为：你也可以在每个节点中创建一个指向父节点的指针。这可以极大地提高某些操作的速度！

- Thomas Sparber

---

谢谢。我现在明白了，我会尝试创建指向父级的指针来加快速度。 - Hòa Ngô

Answer 3

您也可以编写以下简单的迭代版本来实现此子程序：

public Node parent(Node root, int childValue){
  Node parent = NULL;
  while(root != NULL && root.value != childValue) {
       parent=root;
       if(root.value > childValue)
         root = root.left;
       else
         root=root.right;
  }
  return parent

- Alparslan

Answer 4

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

- Antoniet Ama Aggrey

Answer 5

以下代码片段应该可以解决问题：

public Node parent(Node root, int childValue){
  if(root == null)
    return null;
  Node left = root.left;
  Node right = root.right;
  if(left != null && left.value == childValue)
    return root;
  else if(right != null && right.value == childValue)
    return root;
  else if(left != null && left.value > childValue)
    return parent(left, childValue);
  else if(right != null && right.value < childValue)
    return parent(right, childValue);
   else
     return null;
 }

- rbsomeg