在树数据结构中按id查找元素 - Find element by id in tree data structure

Find element by id in tree data structure

本文关键字：id 查找元素数据结构 | 更新日期: 2023-09-27

树样例:

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

我有一个函数，递归地搜索树中的元素。例如，我想找到元素#6

public function getChildById($root,$id){
        if (!empty($root->nodes)){
            foreach ($root->nodes as $node){
                echo $node->getId()."<br>";
                if ($node->getId()==$id){
                    //if i wrote here 'echo $node->getId(), it successful find current way and last id, but the result of that return is nothing'
                    return $node;
                }else{
                    //if i add here return , it newer find 6 elemement, it stops on 13
                    /*return*/ $this->getChildById($node, $id);  
                }
            }
        }
    }

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

事实确实在中间:当您不返回递归调用的值时，您将丢失收集到的信息。另一方面，当您返回递归调用的值时，它将不起作用，因为您将总是在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;
    }           
}