PHP二叉树递归算法

Question

我想使用二叉树和递归创建一个 PHP 递归程序。

我想使用递归逐层打印二叉树。我想遍历树，将节点插入以级别为引用点的 HashMap 中。

这是我目前所拥有的:

$binary_tree = array(array(1 => array(2 => array(4,5),4=>array(5,6))));

            1
            |
    ------------------
    |                |
    2                4
    |                |
----------        ----------
|        |        |        |
4        5        5        6

最终结果应该是这样的:

$data[0] = array(1);  
$data[1] = array(2,4);  
$data[2] = array(4,5,5,6);  

我可以轻松地遍历数组并打印出对应于级别(数组索引)的数字。

这是函数，这是错误的，但我的第一个镜头:

function recurse_tree($data,$level=0){
    $final = array();
    $tmp = array()
    // first check if data is array
    if(is_array($data)){
        // loop through data 
        foreach($data as $elm){
            // push data to the tmp array
            $tmp[] = recurse_tree($elm,$level+1);
        }
        // not an array
    } else {
            // push data to the final array. can we push to the tmp array.
            array_push($final[level],$elm);
    }
    // merge final and tmp array and return
    return ($final + $tmp);
 }

我对递归和解决问题的经验都不太丰富，所以我写下了下面发生的步骤。我现在遇到的问题是，在第 9 步我不确定如何处理键 2 和 4，然后最终处理根节点，键 1。另外，当我到达第 5-8 步时，我处于第 4 级，这是正确的，但是根据树，它是 2 级。

$flattened_tree = recurse_tree($data);

// STEPS:  
1./ called recurse_tree  
    data: array(array(1 => array(2 => array(4,5),4=>array(5,6))));  
    level: 0  
    final:  array();  
    tmp:  array();  
2./ called recurse_tree:  
    data: array(1 => array(2 => array(4,5),4=>array(5,6)));  
    level: 1  
    final: array();  
    tmp: array();  
3./ called recurse_tree:  
    data: array(2 => array(4,5),4=>array(5,6));  
    level: 2
    final: array();  
    tmp: array();
4./ called recurse_tree:
    data: array(4,5)
    level: 3
    final: array();  
    tmp: array();
5./ called recurse_tree:
    data: 4
    level: 4
    final: array(4 => 4)
    tmp: array()
6./ called recurse_tree:
    data: 5
    level: 4
    final: array(4 => 5)
    tmp: array(4 => 4)
7./ called recurse_tree:
    data: 5
    level: 4
    final: array(4=> 5)
    tmp: array(4 => array(4,5))
8./ called recurse_tree:
    data: 6
    level: 4
    final: array(4 => 6)
    tmp: array(4 => array(4,5,5))         

实现二叉树递归算法的最佳方法是什么？

Answer 1

如果我没理解错的话，这就是你想要的:

function tree(array $data, &$tree = array(), $level = 0) {
    // init
    if (!isset($tree[$level])) $tree[$level] = array();

    foreach ($data as $key => $value) {
        // if value is an array, push the key and recurse through the array
        if (is_array($value)) {
            $tree[$level][] = $key;
            tree($value, $tree, $level+1);
        }

        // otherwise, push the value
        else {
            $tree[$level][] = $value;
        }
    }
}

像这样使用它:

$binary_tree = array(1 => array(2 => array(4,5),4=>array(5,6)));
tree($binary_tree, $output);
var_dump($output);

这给你:

array(3) {
  [0]=>
  array(1) {
    [0]=>
    int(1)
  }
  [1]=>
  array(2) {
    [0]=>
    int(2)
    [1]=>
    int(4)
  }
  [2]=>
  array(4) {
    [0]=>
    int(4)
    [1]=>
    int(5)
    [2]=>
    int(5)
    [3]=>
    int(6)
  }
}