我有一个二叉树在数组中的实现:
32
/
2 -5
/
-331 399
数据一次分组3个索引。index%3==0
为节点值,index%3==1
为左节点值的索引,index%3==2
为右节点值的索引。如果左或右索引引用为0,则没有该方向的节点。
我在试着找出这棵树的深度(高度)。我已经递归地写了
height(node):
if node == null:
return 0
else:
return max(height(node.L), height(node.R)) + 1
我想找到一个非递归的解,然而。
下面是我的一些伪代码,假设树不是空的int i = 0; int left = 0; int right = 0;
while (i != n ){
if ( a[i+1] != 0 ){
left++;
}
else if ( a[i+2] != 0 ){
right++;
}
i = i + 3;
}
return max ( left, right ) + 1;
我认为这是不对的,我需要一些帮助来弄清楚如何正确地做到这一点。
您还没有说明递归的问题是什么,以便我们理解您想要改进的行为。
有很多解决方案,但几乎所有的解决方案都具有与递归解决方案相同或更差的性能。实际上,最好的解决方案是你在创建树的时候必须要做的事情。例如,可以将每个节点的高度存储在每个节点的第四个数组索引中。然后每四个索引扫描一次就能找到最大高度。如果节点存储了父引用,那么在高度检查期间不必计算父引用,这也会使操作更容易。
一个解决方案是用堆栈模拟递归,但这与递归没有什么不同。
另一种解决方案是遍历每个节点并根据其父节点确定其高度,但不按照特定的遍历顺序。但是,由于您的配置方式,如果没有二级数据结构来存储层次结构,那么它的效率将会降低O(n^2)。问题是,如果不进行完整的数组扫描,就无法从子节点获取父节点。然后你可以在线性时间内完成(但递归也是线性时间,所以我不确定我们做得更好。从内存的角度来看,它也不会更好)。
你能说明你想提高哪种效率吗?
这里是每个伪代码,但我依赖于一些不容易呈现的数据结构:
"无递归的递归"解:
int get_height(int * tree, int length) {
Stack stack;
int max_height = 0;
if (length == 0) {
return 0;
}
// push an "array" of the node index to process and the height of its parent.
// make this a struct and use that for real c code
stack.push(0,0);
while(!stack.empty()) {
int node_index, parent_height = stack.pop();
int height = parent_height + 1;
if (height > max_height) {
max_height=height;
}
if (tree[node_index+1] != 0 )
stack.push(tree[node_index+1], height);
if (tree[node_index+2] != 0 )
stack.push(tree[node_index+2], height);
}
return max_height;
}
现在正在做一个非常慢的解决方案,不使用额外的内存,但它真的很糟糕。就像递归地写斐波那契一样。原始算法遍历每个节点并执行O(n)次最坏情况检查,运行时间为O(n^2)(实际上没有我最初想象的那么糟糕)
很久以后,我添加了一个优化,跳过所有的节点与子。这真的很重要,因为它减少了很多呼叫。最好的情况是,如果树实际上是一个链表,在这种情况下,它运行在O(n)时间内。最坏的情况是一个完全平衡的树——有logn个叶节点,每个叶节点做logn次检查,返回到O((log(n)^2)的根节点。这也没那么糟糕。"真的很慢,但没有额外的内存"解决方案(但现在更新到不那么慢):
int get_height(int * tree, int length) {
int max_height = 0;
for (int i = 0; i < length; i+=3) {
// Optimization I added later
// if the node has children, it can't be the tallest node, so don't
// bother checking from here, as the child will be checked
if (tree[i+1] != 0 || tree[i+2] != 0)
continue;
int height = 0;
int index_pointing_at_me;
// while we haven't gotten back to the head of the tree, keep working up
while (index_pointing_at_me != 0) {
height += 1;
for (int j = 0; j < length; j+=3) {
if (tree[j+1] == tree[i] ||
tree[j+2] == tree[i]) {
index_pointing_at_me = j;
break;
}
}
}
if (height > max_height) {
max_height = height;
}
}
return max_height;
}
改进了以前的解决方案,但使用O(n)内存-这假设父数组总是在子数组之前(我想这在技术上是不需要的)
int get_height(int * tree, int length) {
if (length == 0)
return 0;
// two more nodes per node - one for which node is its parent, the other for its height
int * reverse_mapping = malloc((sizeof(int) * length / 3) * 2)
reverse_mapping[1] = 1; // set height to 1 for first node
// make a mapping from each node to the node that points TO it.
// for example, for the first node
// a[0] = 32
// a[1] = 3
// a[2] = 6
// store that the node at 3 and 6 are both pointed to by node 0 (divide by 3 just saves space since only one value is needed) and that each child node is one taller than its parent
int max_height = 0;
for (int i = 0; i < length; i+=3) {
int current_height = reverse_mapping[(i/3)*2+1];
if (current_height > max_height)
max_height = current_height;
reverse_mapping[(tree[i+1]/3)*2] = i;
reverse_mapping[(tree[i+1]/3)*2 + 1] = current_height + 1;
reverse_mapping[(tree[i+2]/3)*2] = i;
reverse_mapping[(tree[i+2]/3)*2 + 1] = current_height + 1;
}
return max_height
}