- iOS/Objective-C 元类和类别
- objective-c - -1001 错误,当 NSURLSession 通过 httpproxy 和/etc/hosts
- java - 使用网络类获取 url 地址
- ios - 推送通知中不播放声音
假设一个完整的二叉树,每个节点都可以用它在给定的树遍历算法中出现的位置来寻址。
例如,一棵高度为 3 的简单完整树的节点索引如下所示:
广度优先(又名水平顺序):
0
/ \
1 2
/ \ / \
3 4 5 6
后订单部优先:
6
/ \
2 5
/ \ / \
0 1 3 4
给出树的高度和后序遍历中的索引。
我如何根据这些信息计算广度优先索引?
最佳答案
我认为它必须迭代/递归计算。话虽如此,有人会在 37 秒内通过简单的单行计算来对我投反对票。尽管如此,它可以通过递归思考来解决。考虑深度优先后序遍历的简单树(基于 1):
3
/ \
1 2
从递归的角度来看,这就是您需要考虑的全部内容。您位于子树 (3) 的根部、子树 (1) 的左侧部分或右侧 (2)。如果你在根部,那么你就完成了。否则,左右子树相同,右子树中的后序遍历索引等于对应的左子树索引+子树中的节点数。
以下代码在 O(log n)
中执行此计算。对于深度为 10(1023 个节点)的树,它最多计算 10 次迭代(递归)的索引值。
它跟踪给定节点的深度,并根据它是处理左子树还是右子树来计算广度优先行位置。请注意,这使用基于 1 的索引值。我发现用这些术语来思考它更简单(深度为 2 的树中有 3 个节点,后序遍历中最顶层的节点是 3)。另请注意,它认为树深度为 1 时只有一个节点(我不确定这是否是典型约定)。
// Recursively compute the given post-order traversal index's position
// in the tree: Its position in the given level and its depth in the tree.
void ComputePos( int treedepth, int poindex, int *levelposition, int *nodedepth )
{
int nodes;
int half;
// compute number of nodes for this depth.
assert( treedepth > 0 );
nodes = ( 1 << ( treedepth )) - 1;
half = nodes / 2; // e.g., 7 / 2 = 3
//printf( "poindex = %3d, Depth = %3d, node count = %3d", poindex, treedepth, nodes );
(*nodedepth)++;
if ( poindex == nodes ) {
// This post-order index value is the root of this subtree
//printf( " Root\n" );
return;
}
else if ( poindex > half ) {
// This index is in the right subtree
//printf( " Right\n" );
poindex -= half;
*levelposition = 2 * *levelposition + 1;
}
else {
// Otherwise it must be in the left subtree
//printf( " Left\n" );
*levelposition = 2 * *levelposition;
}
treedepth -= 1;
ComputePos( treedepth, poindex, levelposition, nodedepth );
}
int main( int argc, char* argv[] )
{
int levelposition = 0; // the 0-based index from the left in a given level
int nodedepth = 0; // the depth of the node in the tree
int bfindex;
int treedepth = atoi( argv[1] ); // full depth of the tree (depth=1 means 1 node)
int poindex = atoi( argv[2] ); // 1-based post-order traversal index
ComputePos( treedepth, poindex, &levelposition, &nodedepth );
//printf( "ComputePos( %d, %d ) = %d, %d\n", treedepth, poindex, levelposition, nodedepth );
// Compute the breadth-first index as its position in its current
// level plus the count of nodex in all the levels above it.
bfindex = levelposition + ( 1 << ( nodedepth - 1 ));
printf( "Post-Order index %3d = breadth-first index %3d\n", poindex, bfindex );
return 0;
}
这是为以下树(深度 4)计算的值,它显示了后序遍历索引值(从 1 开始)。
15
/ \
/ \
/ \
/ \
/ \
7 14
/ \ / \
/ \ / \
3 6 10 13
/\ / \ /\ / \
1 2 4 5 8 9 11 12
[C:\tmp]for /l %i in (1,1,15) do po2bf 4 %i
Post-Order index 1 = breadth-first index 8
Post-Order index 2 = breadth-first index 9
Post-Order index 3 = breadth-first index 4
Post-Order index 4 = breadth-first index 10
Post-Order index 5 = breadth-first index 11
Post-Order index 6 = breadth-first index 5
Post-Order index 7 = breadth-first index 2
Post-Order index 8 = breadth-first index 12
Post-Order index 9 = breadth-first index 13
Post-Order index 10 = breadth-first index 6
Post-Order index 11 = breadth-first index 14
Post-Order index 12 = breadth-first index 15
Post-Order index 13 = breadth-first index 7
Post-Order index 14 = breadth-first index 3
Post-Order index 15 = breadth-first index 1
关于algorithm - 将后序二叉树遍历索引转换为层序(广度优先)索引,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/4494752/
序 大家好呀,我是summo,这次来写写我在上班空闲(摸鱼)的时候做的一个小网站的事。去年阿里云不是推出了个活动嘛,2核2G的云服务器一年只要99块钱,懂行的人应该知道这个价格在业界已经是非常良心了
我尝试根据给定的级别顺序(BFS 顺序)构造 BST。我知道这是可能的,但我不知道我该怎么写。问题是我必须使用 BFS 序列。所以,我不能在这里使用递归,我必须迭代地编写我的程序......我发现这有
我是一名优秀的程序员,十分优秀!