Найти элемент по идентификатору в структуре данных дерева

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