试图找到二进制树中的节点的父节点

Question

我试图实现一个函数，该函数查找二叉树中给定节点的父节点，但函数始终返回根节点。我不知道如何使它工作。我一直在努力几天。

Tree* NodeParent(Tree* a, char c) 
{ 
    Tree *parent = a; 

    if (!EmptyTree(a)) 
    { 
     if ((!EmptyTree(a->Left) && info(a->Left) == c) 
      || (!EmptyTree(a->Right) && info(a->Right) == c)) 
      return parent = a; 

     else 
     { 
      NodeParent(a->Left, c); 
      NodeParent(a->Right, c); 
     } 
    } 

    return parent; 
} 

此外，树结构

struct tree 
{ 
    char c; 
    Tree* Left; 
    Tree* Right; 
} 

Answer 1

 return parent = a; 

不是C（或至少，它不是你认为C在这里所做的）。

你只是想要像

return a; 

Answer 2

您需要将递归调用的返回值采集到NodeParent(a->Left, c)和NodeParent(a->Right, c) ...你可以尝试这样的事：

Tree* NodeParent(Tree* a, char c) { 
    Tree *parent; 

    // a is empty tree -> return NULL 
    if (EmptyTree(a)) { 
     return NULL; 

    // in this case, a is the parent 
    } else if ((!EmptyTree(a->Left) && info(a->Left) == c) 
     || (!EmptyTree(a->Right) && info(a->Right) == c)) { 
     return a; 

    // search to the left 
    } else if ((parent = NodeParent(a->Left, c)) != NULL) { 
     return parent; 

    // search to the right 
    } else if ((parent = NodeParent(a->Right, c)) != NULL) { 
     return parent; 

    // c not found in sub-trees 
    } else { 
     return NULL; 
    } 
}