BST在数组遍历中-Java 学习之路

我在数组中有以下二叉树的实现;

数据一次分组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

但是，我想找到一个非递归的解决方案 .

这是我的一些伪代码，假设 tree is not empty

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;

我不认为这是对的，我想帮助弄清楚如何正确地做到这一点 .

1 回答

你还没有说明你的递归问题是什么，我们要了解你想要改进的行为 .

有很多解决方案，但几乎所有解决方案都具有与递归解决方案相同或更差的性能 . 实际上，最好的解决方案将是您在创建树时必须执行的操作 . 例如，您可以将每个节点的高度存储在每个节点的第四个数组索引中 . 然后对每个第四个索引进行一次微不足道的扫描，找出最大高度 . 如果节点具有与它们一起存储的父引用，那么它也会更容易，因此在高度检查期间不必计算 .

一种解决方案是使用堆栈模拟递归，但这与递归完全没有区别 .

另一个解决方案是遍历每个节点并根据它的父节点确定其高度，但不是以特定的遍历顺序确定 . 但是，由于您如何配置此配置，而没有用于存储层次结构的辅助数据结构，因此O（n ^ 2）的效率会降低 . 问题是如果没有完整的阵列扫描，你无法从孩子到其父母 . 然后你可以在线性时间内完成它（但递归也是线性时间，所以我不确定我们做得更好 . 从内存的角度来看，它也不会好得多） .

您能定义想要提高的效率类型吗？

这是每个 pseudocode ，但我很容易出现：

“没有递归的递归”解决方案：

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）时间 . 最坏的情况是一个完全 balancer 的树 - 使用logn叶子节点，每个log节点检查返回根目录为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
}

回复于 2024-05-06T15:21:36+08:00

BST在数组遍历中

1 回答

相关问题