我希望创建一个使用二叉树和递归的PHP递归程序。
我想使用递归打印二叉树的每一层。我想通过遍历树,将节点推入具有级别作为参考点的哈希映射中。
以下是我已经完成的部分:
$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))
如何最好地实现二叉树递归算法?