以完整二叉树,数组格式获取所有节点
I need to get all the nodes at a certain level in a full binary tree from either the left or right subtree. I currently retrieve the binary tree from the DB as an array, for example: [1,2,3,4,5,6,7]
represents a tree like this:
我需要从左子树或右子树中获取完整二叉树中某个级别的所有节点。我目前从数据库中检索二进制树作为数组,例如:[1,2,3,4,5,6,7]表示这样的树:
1
/ \
/ \
2 3
/ \ / \
/ \ / \
4 5 6 7
So what I need to do is basically grab a level of the tree and return it as an array. Something like level(3,"left") -> [4,5]
or level(2, "right") -> [3]
. I was thinking about creating a BinaryTree object doing it recursively, but I can't think of a way to keep track of the level within the call without having to tag every node with a level or something like that as I'd like to keep the DB as clean as possible. Any ideas?
所以我需要做的是基本上抓住树的一个级别并将其作为数组返回。像水平(3,“左”) - > [4,5]或水平(2,“右”) - > [3]。我正在考虑创建一个递归执行它的BinaryTree对象,但我想不出一种方法来跟踪调用中的级别,而不必标记每个节点的级别或类似的东西,因为我想保持DB尽可能干净。有任何想法吗?
Edit: I really need all the nodes at a level for the left or right subtree, not the whole tree. I'm displaying a tournament, so I need to split it half and half. If I didn't have to split it, I could probably do this:
编辑:我真的需要左侧或右侧子树的所有节点,而不是整个树。我正在展示锦标赛,所以我需要将它分成两半。如果我不必拆分它,我可能会这样做:
function level($array, $level_num) {
return array_slice($array, pow(2, $level_num)-1, pow(2, $level_num));
}
I don't really know how to extend this for getting only the left or right subtree's level array.
我真的不知道如何扩展它只获得左或右子树的级别数组。
2 个解决方案
#1
0
I upvoted BeetleJuice's answer for using the "Shift Left" bitwise operator <<
-- it is the perfect building block for this task.
我赞成BeetleJuice使用“Shift Left”按位运算符< <的答案 - 它是完成此任务的完美构建块。< p>
This is as clean as I can make my coding attempt:
这很干净,因为我可以进行编码尝试:
Code: (Demo)
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'));
更多相关文章
- php中的错误级别
- MySQL的事务隔离级别以及设置
- 反驳"MySQL InnoDB (不行)的性能问题",千万级别记录来测试说明
- Mysql 查看及设置事物隔离级别
- mysql事务的默认隔离级别
- MySql日志与事务的隔离级别
- Google Maps API v3:如何设置缩放级别和地图中心到用户提交的位置
- linux 系统级别安全
- 通向SQLServer安全级别3的楼梯:主体和安全性