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

Question

我在执行在二叉搜索树中查找特定节点的父节点的任务时遇到问题。解决方案应该很简单，但我不知道为什么我的代码不起作用...我尝试了不同的方法，还在网上搜索了任何解决方案，但一无所获。我很感激任何帮助!

typedef struct Treenode{
    int key;
    struct Treenode* lChild;
    struct Treenode* rChild;
}node;

node * getParent(node *root, int key){
    if (root == NULL) return NULL;
    else if (root->rChild->key == key || root->lChild->key == key) return root;
    else if (root->key > key) getParent(root->lChild, key);
    else getParent(root->rChild, key);
    return root;
}

Answer 1

else if (root->key > key) getParent(root->lChild, key);
else getParent(root->rChild, key);

在这两种情况下，您应该返回 getParent(...);。否则递归调用的结果将被简单地丢弃。