查找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; 
    }   
}