在树数据结构中通过 id 查找元素

Question

树样本：

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

            }
        }
    }

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

Answer 1

真相确实在中间：当你不return递归调用的值时，你会丢失你收集的信息。另一方面，当你 return 递归调用的值时，它将不起作用，因为你将 always return 在你的 foreach循环。

因此，有时您需要 return 它：仅当您在递归部分有匹配项时。如果没有成功，你不应该 return 并继续 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;
    }           
}

在树数据结构中通过 id 查找元素

Find element by id in tree data structure

php

tree

php-5.3