查找id元素在树数据结构

Question

树样本：

  root 
     /| \ 
      1 2 4 
     / /|\ 
     3  5 6 7 
    /\ 
     13 14 

我有一个功能，在树中搜索元素递归。例如我想找到元素＃6

我写了一些评论，请帮助我，我做错了什么？

Answer 1

事实确实在中间：当您不返回递归调用的值时，您将丢失收集的信息。另一方面，当您返回递归调用的值时，它将不起作用，因为您将在foreach循环的第一次迭代中返回总是。

所以，你需要有时候返回它：只有当你在递归部分有一个匹配时。如果没有成功，则不应返回并继续foreach循环：

public function getChildById($root, $id){ 
    if (!empty($root->nodes)){ 
     foreach ($root->nodes as $node){ 
      if ($node->getId()==$id){ 
       return $node; 
      } else { 
       $found = $this->getChildById($node, $id); 
       if ($found) return $found; 
      }   
     } 
    } 
} 

看到它在eval.in运行。

请注意，在根目录上进行匹配测试比较常见，所以在函数的开始处。它涉及到同样的事情，除了如果该值是你调用该函数的根，它也被发现！

public function getChildById($root, $id){ 
    if ($root->getId()==$id) return $root; 
    foreach ($root->nodes as $node){ 
     $found = $this->getChildById($node, $id); 
     if ($found) return $found; 
    }   
}