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

Question

二分木のプログラムを以下のように作成したのですが,メモリの開放は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;
}

Comments

[episteme]

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

Answer 1

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

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);
    }
}

Answer 2

/*帰りがけ順*/
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は全滅 */

Answer 3

使用している開発環境が分らないのですが、ライブラリーによっては、メモリーリークを検出できます。
例えば 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);
}

これで充分ですね。

Comments

[episteme]

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

[Bull]

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

Answer 4

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 はもうアクセスできない
}

Comments

[episteme]

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

[tacsheaven]

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

[episteme]

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