0

二分木を完全にする最適化メソッドを実装しようとしています。私の方法では、ツリーを にソートしてint*から、配列の中間点を新しい配列に追加し、それぞれの半分を再帰することでこれを行います。

ただし、コードが実際に出力するのは、左側のツリーに沿って最大の深さまで下降した後に重複を生成することです。

16 8 4 2 1 0 0 3 3 6 5 5 7 7 12 10 9 9 11 11 14 13 13 15 15 24 20 18 17 17 19 19

なぜこれが起こっているのか、一生理解できません。

私のコード:

// bth is "binary tree helper [method]"
void bth_optimizearray(int* in, int* out, int min, int max, int* i) {
    // `in' is sorted, `out' should be optimized
    // `i' is the current index in `out'

    int len /* of subarray */ = max - min;
    if (len < 1) {
        // empty subarray
        return;
    }
    if (len == 1) {
        // just add it
        out[(*i)++] = in[min];
    } // else

    // Add the midpoint
    int midpos = min + ((max - min) >> 1);
    out[(*i)++] = in[midpos];
    bth_optimizearray(in, out, min, midpos, i);
    bth_optimizearray(in, out, midpos + 1, max, i);
}

void bt_optimize(bintree *tree) {
    int treesize = bt_size(tree);

    int *ordered = malloc(treesize * sizeof(int));
    {
        int i = 0;
        void visit(node *n) {
            ordered[i++] = n -> key;
        }
        bt_traverse(tree, INORDER, visit);
    }


    int *optimized = malloc(treesize * sizeof(int));
    {
        int *i = malloc(sizeof(int));
        (*i) = 0;
        bth_optimizearray(ordered, optimized, 0, treesize, i);
    }

    // Free all nodes (but don't call freetree; that would free the tree too)
    void freenode(node *n) {
        free(n);
    }
    bt_traverse(tree, INORDER, freenode);
    tree -> root = NULL;

    {
        int i;
        for (i = 0; i < treesize; i++) {
            printf("%d ", optimized[i]);
            bt_add(tree, optimized[i]);
        }
    }
}

このコードでbintreeは、 がstruct { node *root; int size; }あり、他のすべてのメソッドは正常に機能します。

完全なコードもGitHubにありますが、このbt_optimizeメソッドはoptimizeブランチのみにあります。

これは C++ ではなく C です。

助言がありますか？

4

2 に答える 2

1

min = max - 1 の場合、「out[(*i)++]」ステートメントが 2 回実行されるようです。

if (len == 1) {
    // just add it
    out[(*i)++] = in[min];
    // -- Should place a "return;" here?
} // else

// Add the midpoint
int midpos = min + ((max - min) >> 1);
out[(*i)++] = in[midpos];
于 2013-09-10T06:45:26.770 に答える