C言語での2分木ソートアルゴリズムでセグメンテーション違反が取り除けない

C言語で2分木を使った昇順ソートアルゴリズムを作成しています。
小さい順に表示しようとするとセグメンテーション違反が起こってしまいます。原因がわからないので教えていただきたいです。

ソース

#include <stdio.h>
#include <stdlib.h>
#include <string.h>


struct tree {
    int value;
    struct tree *left;
    struct tree *right;
};

// ノードを追加
int append(int input, struct tree *current_node) {
    if (input < current_node->value) {
        if (current_node->left != NULL) {
            append(input, current_node->left);
        } else {
            struct tree new = {input, NULL, NULL};
            current_node->left = &new;
        }
    
    } else {
        if (current_node->right != NULL) {
            append(input, current_node->right);
        } else {
            struct tree new = {input, NULL, NULL};
            current_node->right = &new;
        }
    }
}


// 小さい順に表示
void sort(struct tree *current_node) {
    if (current_node->left != NULL) {
        sort(current_node->left);
    }
    printf("%d, ", current_node->value);
    if (current_node->right != NULL) {
        sort(current_node->right);
    }
}



int main() {
    int sequence[] = {2, 4, 6, 1, 8, 2, 10, 0};
    int n = sizeof(sequence) / sizeof(int);
    struct tree root = {
        sequence[0],
        NULL,
        NULL
    };
    for (int i = 1; i < n; i++) {
        append(sequence[i], &root);
    }
    sort(&root);
    printf("\n");
}

発生している問題・エラーメッセージ

sort()関数のところでセグメンテーション違反が起こっています。

試したこと

gdbでステップ実行をしてみたのですが、sort()にはいった段階でそれぞれのノードのvalueの値が-129660088のようにおかしくなっていました。

環境

WSL2, Ubuntu20.04LTS, gcc version9.3.0,

行動規範の内容に同意します

回答2件

ベストアンサー

append の struct tree new = { input, NULL, NULL }; の new は
自動変数で、この場でメモリが確保され input で初期化されますが、
current_node->left = &new; または current_node->right = &new; の
あとの } で、new のメモリが解放され、他の用途に使用されます。
current_node->left や current_node->right は、正しいデータの存在しない
メモリを指すことになります。

malloc でメモリ領域を確保しないといけません。

diff
1+struct tree *new_node(int input)
2+{
3+	struct tree *new = malloc(sizeof(struct tree));
4+	new->value = input;
5+	new->left = new->right = NULL;
6+	return new;
7+}
8+
9 // ノードを追加
10-int append(int input, struct tree *current_node) {
11+void append(int input, struct tree *current_node) {
12     if (input < current_node->value) {
13         if (current_node->left != NULL) {
14             append(input, current_node->left);
15         } else {
16-            struct tree new = {input, NULL, NULL};
17-            current_node->left = &new;
18+            current_node->left = new_node(input);
19         }
20 
21     } else {
22         if (current_node->right != NULL) {
23             append(input, current_node->right);
24         } else {
25-            struct tree new = {input, NULL, NULL};
26-            current_node->right = &new;
27+            current_node->right = new_node(input);
28         }
29     }
30
31+void freeAll(struct tree *p)
32+{
33+	if (p->left) freeAll(p->left);
34+	if (p->right) freeAll(p->right);
35+	free(p);
36+}
37 
38 int main() {
39     int sequence[] = {2, 4, 6, 1, 8, 2, 10, 0};
40     int n = sizeof(sequence) / sizeof(int);
41-    struct tree root = {
42-        sequence[0],
43-        NULL,
44-        NULL
45-    };
46+    struct tree *root = new_node(sequence[0]);
47     for (int i = 1; i < n; i++) {
48-        append(sequence[i], &root);
49+        append(sequence[i], root);
50     }
51-    sort(&root);
52+    sort(root);
53     printf("\n");
54+    freeAll(root);
55 }