我正在尝试在常规搜索树中实现查找键功能，其中节点可以有任意数量的子节点。代码如下

Question

shared_ptr<节点<T、 S>gt；树<T、 S>：findKeyHelper(shared_ptr<node<T，S>>currNode，T密钥)｛

if (currNode->key==key){
return currNode;
}
else {
if (currNode->child==NULL){
if (currNode->sibling==NULL){
return NULL;
}
else {
findKeyHelper(currNode->sibling,key);
}
}
else {
findKeyHelper(currNode->child,key);
}
}

}

在一个子树用完后，我如何让函数搜索其他子树。

Answer 1

我认为您正在使用树的左子、右同级表示来实现恒定数量的子级。您的程序需要进行几次修改。可以使用递归搜索其他子树。递归之所以有效，是因为子树和树本身具有相同的结构(子树是树的小实例)

if (currNode!= NULL && currNode->key == key){ 
return currNode;
}

您需要检查current指针。如果是current == NULL，那么current->key将给出无法取消引用NULL指针的错误。

else {
if(currNode->sibling != NULL)
findKeyHelper(currNode->sibling, key);
if(currNode->child != NULL)
findKeyHelper(currNode->child, key);
}

程序首先检查current是否为NULL。如果是，则终止；否则在current节点中搜索值。如果发现，返回current；如果没有，必须确定是否有兄弟姐妹或孩子需要寻找。如果零件解决了这个问题。请注意，当子树不是NULL时会发生递归调用。您的问题主要在else部分得到解决

编辑：我修改了您的程序，并了解了它不起作用的原因。仅当节点的子级为NULL时，才对兄弟调用递归过程。但事实并非如此：当节点的子节点不是NULL时，您就不会访问兄弟姐妹。这就是问题所在，您可以通过提取
来解决它

if (currNode->sibling==NULL){
return NULL;
}
else {
findKeyHelper(currNode->sibling,key);
}

在if-block语句中，您的程序将工作。现在正确的程序看起来像：

if (currNode!= NULL && currNode->key==key){
return currNode;
}
if(currNode->child == NULL) ;
else {
findKeyHelper(currNode->child, key);
}
if (currNode->sibling==NULL)
;
else
findKeyHelper(currNode->sibling, key);

由于空体if语句没有任何作用，您可以删除它们，这就是我上面所做的。