Мне нужно получить все узлы на определенном уровне в полном двоичном дереве из левого или правого поддерева. В настоящее время я извлекаю двоичное дерево из БД в виде массива, например: [1,2,3,4,5,6,7] представляет дерево, подобное этому:
1 / \ / \ 2 3 / \ / \ / \ / \ 4 5 6 7
Так что мне нужно сделать, это в основном захватить уровень дерева и вернуть его как массив. Что-то вроде level(3,"left") -> [4,5] или level(2, "right") -> [3] . Я думал о создании объекта BinaryTree, который делает это рекурсивно, но я не могу придумать способ отслеживания уровня внутри вызова без необходимости отмечать каждый узел уровнем или чем-то подобным, поскольку я хотел бы сохранить БД как можно чище. Есть идеи?
Изменить: мне действительно нужны все узлы уровня для левого или правого поддерева, а не всего дерева. Я показываю турнир, поэтому мне нужно разделить его на полтора раза. Если бы мне не пришлось разбить его, я, вероятно, мог бы это сделать:
function level($array, $level_num) { return array_slice($array, pow(2, $level_num)-1, pow(2, $level_num)); }
Я не знаю, как это расширить, чтобы получить только массив уровней левого или правого поддерева.
Я поддержал ответ BeetleJuice на использование побитового оператора «Shift Left» << – это идеальный строительный блок для этой задачи.
Это так же чисто, как я могу сделать мою попытку кодирования:
Код: ( Демо )
function getForkinValues($array,$level,$side='left'){ // left side fork is default if($level==1) return current($array); $length=$level>2?1<<($level-2):1; // number of elements to return $index=(1<<$level-1)-1; // first index to return if($side=='right') $index+=$length; // shift to correct index for 'right' if(!isset($array[$index+$length-1])) return 'Error: Insufficient Array Length'; return array_slice($array,$index,$length); } $array=['A','B','C','D','E','F','G']; var_export(getForkinValues($array,3,'right'));
// Adjust depth as needed $depth = 3; // using bit arithmetic. '<< 3' means multiply by 2 three times. $start = 1 << $depth-1; // 1 * (2 * 2) because depth is 3 $end = (1 << $depth) -1; // 1 * (2 * 2 * 2) - 1 // if depth=3, this is [4,5,6,7] $fullLevel = range($start, $end); print_r($fullLevel); if($depth > 1): $leftBranch = array_slice($fullLevel,0,count($fullLevel)/2); $rightBranch = array_slice($fullLevel,count($fullLevel) / 2); print_r($leftBranch); // [4,5] print_r($rightBranch); // [6, 7] endif;