質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

89.21%

二分木のメモリ開放の方法

解決済

回答 4

投稿

  • 評価
  • クリップ 0
  • VIEW 850

masuter0413

score 45

二分木のプログラムを以下のように作成したのですが,メモリの開放はFREE_Memory()でちゃんとできているでしょうか.

#include <stdio.h>
#include<stdlib.h>
#include<string.h>
#define N 30

typedef struct node {
    struct node *left, *right;
    char label[N];
}TREE;
TREE *root = NULL;//ポインタ初期化

                      //ノードの新規作成
TREE *NewNode(char *str) {
    TREE *bp;
    bp = (TREE *)malloc(sizeof(TREE));//メモリ確保
    bp->left = NULL;
    bp->right = NULL;
    strcpy(bp->label, str);           //文字列格納
    return bp;
}
/*ツリー組み立て*/
TREE *construct_tree(TREE*node, char *str) {
    int len1 = 0, len2 = 0;  //文字列の長さ
    if (node == NULL) {      //受け取ったrootがNULLのとき
        node = NewNode(str); //新しくノード(root)作成
    }
    else {
        len1 = strlen(node->label);//nodeに格納されている文字列の長さ
        len2 = strlen(str);        //文字列strの長さ
        if (len2 < len1) {         //文字列の長さ比較
            node->left = construct_tree(node->left, str);//文字列strの方が短いとき左に登録
        }
        else {
            node->right = construct_tree(node->right, str);//文字列strの方が長いとき右に登録
        }
    }
    return node;
}

/* 部分木の全ての値を出力 */
TREE*print_tree(TREE *node, int depth) {
    if (node == NULL) {
        return NULL;
    }
    print_tree(node->right, depth + 1);//一番右の子から表示していく                                 
    { int i; for (i = 0; i < depth; ++i) printf("     "); } // depth分の空白
    printf("%s\n\n", node->label);
    print_tree(node->left, depth + 1);//左の子表示
    return node;
}


/*行きがけ順*/
void preorder(TREE*p) {
    if (p == NULL)return;
    fprintf(stdout, "立ち寄った節:%s\n", p->label);
    preorder(p->left);
    preorder(p->right);
}
/*通りがけ順*/
void inorder(TREE*p) {
    if (p == NULL)return;
    inorder(p->left);
    fprintf(stdout, "立ち寄った節:%s\n", p->label);
    inorder(p->right);
}
/*帰りがけ順*/
void postorder(TREE*p) {
    if (p == NULL)return;
    postorder(p->left);
    postorder(p->right);
    fprintf(stdout, "立ち寄った節:%s\n", p->label);
}

/*ツリーを表示する関数*/
void Print_All() {
    print_tree(root, 0);//ツリーの先頭と空白の数(深さ)を与える
    printf("********** OUTPUT (preorder 行きがけ順)!! **********\n");
    preorder(root);
    printf("********** OUTPUT (inorder 通りがけ順)!! **********\n");
    inorder(root);
    printf("********** OUTPUT (postorder 帰りがけ順)!! **********\n");
    postorder(root);
}

TREE *Free_Memory(TREE *p) {
    if (p == NULL) {
        return NULL;
    }
    Free_Memory(p->right);
    free(p->right);
    Free_Memory(p->left);
    return p;
}

int main() {
    FILE*fp;    //ファイルポインタ
    char str[N];//読み込む文字列
                //ファイルオープン処理
    if ((fp = fopen("food.txt", "r")) == NULL) {
        fprintf(stderr, "%s\n", "error: can't read file.");
        return EXIT_FAILURE;
    }
    fscanf(fp, "%s", str);  //最初の文字列読み込み
    root = NewNode(str);//rootを作成,pはrootへのポインタ
    while (fscanf(fp, "%s", str) != EOF) {//ファイルエンドまで文字列読み込み
        construct_tree(root, str);        //ツリー組み立て
    }
    Print_All();                          //ツリーを各方法で表示
    return 0;
}
  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

質問への追記・修正、ベストアンサー選択の依頼

  • episteme

    2019/05/07 11:42

    テストコードちょこっと書けばわかるやん。mallocのたびに+1 / freeのたびに-1 するカウンタを仕込んでおいて、最終的に0になればOK.

    キャンセル

回答 4

checkベストアンサー

0

/*帰りがけ順*/
void postorder(TREE*p) {
    if (p == NULL)return;
    postorder(p->left);
    postorder(p->right);
    fprintf(stdout, "立ち寄った節:%s\n", p->label);
}

をちょびっといぢって:

/*帰りがけ順*/
void do_postorder(TREE*p, void(*fun)(TREE*)) {
    if (p == NULL)return;
    do_postorder(p->left);
    do_postorder(p->right);
    fun(p);
}

を定義すれば、帰りがけになんかすることができるから

void free_node(TREE* p) { free(p); }
...
do_postroder(root, &free_node); /* これでrootを根とするTREEは全滅 */

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

0

TREE *Free_Memory(TREE *p) {
    if (p == NULL) {
        return NULL;
    }
    Free_Memory(p->right);
    free(p->right);
    Free_Memory(p->left);
    return p;
}


ぱっと見、あるノードの下の枝を解放してますけど、

  • 右の枝は解放しているけど、左の枝は?
  • 自分自身は?

というあたりで、解放できてないような気がしますが。

TREE *Free_Memory(TREE *p) {
  if (p == NULL) {
    return NULL;
  }
  Free_Memory(p->right);
  Free_Memory(p->left);
  free(p_right);
  free(p_left);
  free(p);
  return p;  // ただしこの p はもうアクセスできない
}

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2019/05/07 11:32

    それだと二重解放にならん? freeするのは p だけでいいように思える。

    キャンセル

  • 2019/05/07 11:36

    あー、確かに。free(p->left) と free(p->right) は(Free_Memory 内で自身を free する以上は)いらないか。

    キャンセル

  • 2019/05/07 12:37

    うん、結局帰りがけ順:void postorder(TREE*p) が全TREEを辿れるなら、そいつの fprintf を free に置き換えるだけかと。

    キャンセル

0

使用している開発環境が分らないのですが、ライブラリーによっては、メモリーリークを検出できます。
例えば VC++ ですと、<crtdbg.h>をインクルードしてmain の最初で_CrtSetDbgFlag(_CRTDBG_LEAK_CHECK_DF | _CrtSetDbgFlag(_CRTDBG_REPORT_FLAG));
などとしておくと、malloc したメモリーを free しないで終了するとその旨を報告してくれます。(デバッグビルド時のみ)
テストデータを適当に作って Free_Memory を呼ぶように修正して実行してみましたが、メモリーの解放はできてないです。

修正方法ですが、「p->left あるいは p->right が NULL でなかったら、それぞれを Free_Memory で解放してから p を free で解放する」でいいと思います。

void Free_Memory(TREE * p) {
    if (p == NULL) {
        return;
    }
    if (p->left) {
        Free_Memory(p->left);
    }
    if (p->right) {
        Free_Memory(p->right);
    }
    free(p);
}

指摘されましたので、修正します。

void Free_Memory(TREE * p) {
    if (p == NULL) {
        return;
    }
    Free_Memory(p->left);
    Free_Memory(p->right);
    free(p);
}


これで充分ですね。

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2019/05/07 18:18

    if (p->left) , if (p->right) は不要スね。
    呼ばれた先の if ( p == NULL ) { return; } で門前払いだから。

    キャンセル

  • 2019/05/07 18:26

    あっ、そうですね。
    結局、tacsheaven さんの回答で充分でした。

    キャンセル

0

最低限度これで良いのでは?

void Free_Memory(TREE *p) {//そもそも戻り値いらない
    if (p) {
        Free_Memory(p->left);
        Free_Memory(p->right);
        free(p);
    }
}


解放を先にするのならこんな感じ。

void Free_Memory(TREE *p) {//そもそも戻り値いらない
    if (p) {
        TREE *pleft = p->left, *pright = p->right;
        free(p);
        Free_Memory(pleft);
        Free_Memory(pright);
    }
}

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 89.21%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

同じタグがついた質問を見る