以完整的二叉树，数组格式将所有节点置于一个级别 [英] Getting all nodes at a level in full binary tree, array format

问题描述

我需要从左或右子树中获取完整二进制树中某个级别的所有节点.我目前从数据库中以数组的形式检索二叉树，例如: [1,2,3,4,5,6,7]代表这样的树:

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

所以我需要做的基本上是获取树的某个级别并将其作为数组返回. level(3,"left") -> [4,5]或level(2, "right") -> [3]之类的东西.我当时正在考虑以递归方式创建一个BinaryTree对象，但是我想不出一种方法来跟踪调用中的级别，而不必为每个节点添加级别或类似的标记，因为我想保持数据库越干净越好.有什么想法吗?

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?

实际上，我确实需要为左或右子树设置一个级别的所有节点，而不是整个树.我正在显示一个锦标赛，所以我需要将其一分为二.如果我不必拆分它，则可以这样做:

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.

推荐答案

我赞成BeetleJuice使用按左移"按位运算符<<的答案-这是完成此任务的完美构建块.

I upvoted BeetleJuice's answer for using the "Shift Left" bitwise operator << -- it is the perfect building block for this task.

这很干净，我可以尝试进行编码:

This is as clean as I can make my coding attempt:

代码:( 演示)

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'));

这篇关于以完整的二叉树，数组格式将所有节点置于一个级别的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！