c-如何在非变量二叉树中搜索给定节点的父节点

Question

我有在二进制树中搜索节点的代码。如何找到KEY作为参数提供的节点的父节点？

这是正常搜索二进制树的代码-

struct Tree* search(struct Tree *root, int KEY)
{
struct Tree *temp;
if(root == NULL) return NULL; //Base condition
else
{
if(root-> data == KEY) return root;
else
{
temp = search(root-> Lchild, KEY);
if(temp != NULL) return temp;
else return(search(root-> Rchild, KEY));
}
}
return NULL;
}

Answer 1

返回的是值与KEY匹配的Tree节点的地址，而不是它的父节点。假设该树中的所有节点值都是不同的，那么如果父节点(左或右子节点(的值与KEY匹配，则必须按照以下代码返回父节点Tree节点地址。

struct Tree* search(struct Tree *root, int KEY){
if(root == NULL){
return NULL;
}
if(root->Lchild != NULL && root->Lchild->data == KEY){
return root;
}
if(root->Rchild != NULL && root->Rchild->data == KEY){
return root;
}
struct Tree *left = search(root->Lchild, KEY);
struct Tree *right = search(root->Rchild, KEY);
if(left != NULL){
return left;
}else if(right != NULL){
return right;
}
return NULL;
}