Я хочу создать рекурсивную программу 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, im на уровне 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))
Каков наилучший способ реализации алгоритма рекурсии двоичного дерева?
Если я правильно понимаю, это то, что вы хотите:
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) } }
Эта функция в представлении дерева классов
у вас есть возврат массива, который имеет все значение узла, а затем вы можете упорядочить его под древовидным представлением.
function getTreeDataFromReg($setid) { if(!empty($setid)) { for($in=0 ;$in<7;$in++ ) { if($setid[$in]>0) { $result=$this->selectQuery( "tbl_registration"," * "," fl_reg_id ='".$setid[$in]."'", " fl_placment_side ASC "); $setar=mysql_fetch_array($result); $leftid=$setar['fl_left_id']; $rightid=$setar['fl_right_id']; }else { $leftid=0; $rightid=0; } switch($in) { case 0: $setid[1]=$leftid; $setid[2]=$rightid; break; case 1: $setid[3]=$leftid; $setid[4]=$rightid; break; case 2: $setid[5]=$leftid; $setid[6]=$rightid; break; case 3: $setid[7]=$leftid; $setid[8]=$rightid; break; case 4: $setid[9]=$leftid; $setid[10]=$rightid; break; case 5: $setid[11]=$leftid; $setid[12]=$rightid; break; case 6: $setid[13]=$leftid; $setid[14]=$rightid; break; } } } return $setid; } function printTreeView($parentid) { $setid=array($parentid); $setarra=$this->getTreeDataFromReg($setid); return $setarra; }
Что создает двоичное дерево:
0 / \ 1 2 / \ / \ 3 4 5 6 /\ / \ /\ /\