在完全三叉树中搜索一个元素

Question

我需要的功能：return如果找到键，则为树中节点的索引，否则return -1。

我的伪代码：

int search(Node node,int key){
   if(node->key==key){
      return node->index;
   }
   if(node->leftchild exists){
     search(node->leftchild,key);
   }
   if(node->middlechild exists){
     search(node->middlechild,key);
   }
   if(node->rightchild exists){
     search(node->rightchild,key);
   }
}

当我调用函数时，我将首先传递根：

int result = search(root,key);

我遗漏的部分：

After every recursion call has been made, if the condition node->key==key was never met, return -1

在上面用伪代码编写的函数中添加我缺少的部分的正确方法是什么？

Answer 1

首先，您的代码没有利用您进行的递归调用。 -1 更像是一个默认值。我建议对您的伪代码进行此修改：

int search(Node node,int key){
   if(node->key==key){
      return node->index;
   }
   int result = -1;
   if(node->leftchild exists){
      result = max(result, search(node->leftchild,key));
   }
   if(node->middlechild exists){
     result = max(result, search(node->middlechild,key));
   }
   if(node->rightchild exists){
     result = max(result, search(node->rightchild,key));
   }
   return result;
}

重要说明：此代码假定所有键都是 non-negative。如果此条件为真，您可能会看到只有在搜索找到节点时才会更新结果（returning -1 不会更改结果）。如果这个条件不成立，代码会因为很多 if 而变得不那么整洁，如果你想 return 一旦你找到一个节省性能的关键，它们也是必要的。此代码将是：

int search(Node node,int key){
   if(node->key==key){
      return node->index;
   }
   if(node->leftchild exists){
      int result = search(node->leftchild,key);
      if (result != -1) {
         return result;
      }
   }
   if(node->middlechild exists){
      int result = search(node->middlechild,key);
      if (result != -1) {
         return result;
      }
   }
   if(node->rightchild exists){
      int result = search(node->rightchild,key);
      if (result != -1) {
         return result;
      }
   }
   return -1;
}

这段代码有很多copy-paste，但是摆脱它的最佳方法取决于实际的编程语言和对键的限制。

在完全三叉树中搜索一个元素

Search for an element in a complete ternary tree

algorithm

tree

search