1

宿題をやろうとしているのですが、なかなか難しいです。

リーフ間のパスを別の整数バイナリ ツリー (つまり、ツリーは整数を保持します) に出力する再帰関数を作成します。

int printPath(Tree* t, int a, int b)。

注: 次の状況に対処する必要があります。

  • ツリーには a および/または b はありません。その場合は -1 を返します。

  • 存在する場合は、その値を持つノードとその値を持つノードの間のすべての値を出力しaますb。0 を返します。

私はこのコードを試しました：

int print1(Tree* tree, int a, int b) {
    int cnt;
    int c = MAX(a, b), d = MIN(a, b);
    a = d;
    b = c;
    if (!tree)
        return -1;
    /*
     if (tree->key.id > b || tree->key.id < a) {
         if(tree->key.id > b)
             cnt = print(tree->left, a, b);
         else
             cnt = print(tree->right, a, b);
     }*/

    if (tree->key.id == a || tree->key.id == b) {
        if (tree->key.HWGrade) {
            printf("e) , %d -> ", tree->key.id);
            tree->key.HWGrade = 0;
        }
        return 0;
    }

    if (tree->key.id > b) {
        cnt = print1(tree->left, a, b);
        if (tree->key.HWGrade) {
            printf("c) , %d -> ", tree->key.id);
            tree->key.HWGrade = 0;
        } else
            return 0;
    } else {
        if (tree->key.id > a) {
            cnt = print1(tree->left, a, b);
            if (tree->key.id != a && tree->key.id != b && !cnt) {

                if (tree->key.HWGrade) {
                    printf("d) , %d -> ", tree->key.id);
                    tree->key.HWGrade = 0;
                } else
                    return 0;
            }
        }
    }

    if (tree->key.id < a) {
        cnt = print1(tree->right, a, b);
        if (tree->key.id != a && tree->key.id != b && !cnt) {
            if (tree->key.HWGrade) {
                printf("a) , %d -> ", tree->key.id);
                tree->key.HWGrade = 0;
            } else
                return 0;
        }
    } else {
        if (tree->key.id < b) {
            cnt = print1(tree->right, a, b);
            if (tree->key.id != a && tree->key.id != b && !cnt) {
                if (tree->key.HWGrade) {
                    printf("b) , %d -> ", tree->key.id);
                    tree->key.HWGrade = 0;
                } else
                    return 0;
            }
        }
    }

    if (cnt == 0)
        return 0;
    return -1;
}

しかし、うまくいかないようです。

使用された構造:

typedef struct {
    int id;
    int HWGrade;
    int ExamGrade;
} MatamStudent;

typedef struct Tree{
    int Data;
    struct Link* list;
    MatamStudent key;
    struct Tree *left;
    struct Tree *right;
} Tree;

UbuntuでEclipseでGCCを使用しています。

4

2 に答える 2

1

ツリーをソートする必要があると言われている配列の場所がわかりません。直感的なアルゴリズムは次のようになります。

  • aルートからこのノードまでのパスをp1(サイズ) で検索して保存しますn。
  • bルートからこのノードまでのパスをp2(サイズ) で検索して保存しますm。
  • 2 つのパスを比較します。2 つの値p1[i]とp2[i]が異なる場合、p1からp1[m]へp1[i]、2 番目のパスで からp2[i]へ移動できますp[m]。

アルゴリズムは で実行されます。O(S)ここSで、 は葉の数です。

#include <stdio.h>

size_t mid, i;
int p1[MAX_LEAVES];
int p2[MAX_LEAVES];
int n = searchTree(p1, tree, a);
int m = searchTree(p2, tree, b);

if (n == 0 || m == 0)
    return -1;

for (mid = 0; mid < n && mid < m && p1[mid] == p2[mid]; mid++)
    ;

for (i = n - 1; i >= mid; i--)
    printf("%d ", p1[i]);

for (i = mid; i < m; i++)
    printf("%d ", p2[i]);

putchar('\n');

return 0;
于 2013-05-30T17:25:34.060 に答える