二分探索木が動作しない

二分探索木を表現する関数を作成しています．1~100を順に配列に並べランダムに並び替えた後，それをまたほかの配列へ任意の数取り出すことでランダムな配列を作成し，その配列をinsertによって二分探索木に表現し，また，削除や挿入，探索も関数として表現します．この関数のどこを修正すれば正しく処理されるかを教えていただけると幸いです．

C
1#include <stdio.h>
2#include <stdlib.h>
3
4typedef struct node
5{
6    int data;
7    struct node *leftson;
8    struct node *rightson;
9} Node;
10Node *search(int x);
11void new (Node **w);
12void insert(int x);
13void nfree(Node *n);
14Node *v, *root;
15Node *search(int x)
16{
17    v = root;
18    while (v != NULL)
19    {
20        if (v->data == x)
21        {
22            return (v);
23        }
24        if (v->data > x)
25        {
26            v = v->leftson;
27        }
28        else
29        {
30            v = v->rightson;
31        }
32    }
33    printf("The element is not in S.\n");
34    return (NULL);
35}
36
37void new (Node **w)
38{
39    *w = (Node *)malloc(sizeof(Node));
40}
41
42void insert(int x)
43{
44    Node *p = NULL;
45    Node *w;
46    v = root;
47    while (v != NULL)
48    {
49        p = v;
50        if (v->data > x)
51        {
52            v = v->leftson;
53        }
54        else
55        {
56            v = v->rightson;
57        }
58    }
59    new (&w);
60    w->data = x;
61    w->rightson = NULL;
62    w->leftson = NULL;
63    if (p->data > x)
64    {
65        p->leftson = w;
66    }
67    else
68    {
69        p->rightson = w;
70    }
71}
72
73void delete (int x)
74{
75    Node *p, *q;
76    v = root;
77    while (v->data != x)
78    {
79        p = v;
80        if (v->data > x)
81        {
82            v = v->leftson;
83        }
84        else
85        {
86            v = v->rightson;
87        }
88    }
89    if (v->leftson == NULL || v->rightson == NULL)
90    {
91        if (v->leftson == NULL)
92        {
93            q = v->rightson;
94        }
95        else
96        {
97            q = v->leftson;
98        }
99        if (p->leftson == v)
100        {
101            p->leftson = q;
102        }
103        else
104        {
105            p->rightson = q;
106        }
107    }
108    else
109    {
110        q = v->rightson;
111        while (q->leftson != NULL)
112        {
113            p = q;
114            q = q->leftson;
115        }
116        v->data = q->data;
117        if (q == v->rightson)
118        {
119            v->rightson = q->rightson;
120        }
121        else
122        {
123            p->leftson = q->rightson;
124        }
125    }
126}
127
128void nfree(Node *n)
129{
130    if (n->leftson != NULL)
131    {
132        nfree(n->leftson);
133    }
134    if (n->rightson != NULL)
135    {
136        nfree(n->rightson);
137    }
138    free(n);
139}
140/*配列をランダムに並び替える*/
141void shuffle(int ary[], int max)
142{
143    int i, tmp, no;
144    for (i = 0; i < max; i++)
145    {
146        no = rand() % max;
147        tmp = ary[no];
148        ary[no] = ary[i];
149        ary[i] = tmp;
150    }
151}
152
153/*数字を順番に入力してシャッフルする*/
154void make_num(int ary[], int max)
155{
156    int i;
157    for (i = 1; i <= max; i++)
158    {
159        ary[i - 1] = i;
160    }
161    shuffle(ary, max);
162}
163
164/*先頭から何番目かの配列を新たに作る*/
165void make_ary(int B[], int A[], int num)
166{
167    int i;
168    for (i = 0; i < num; i++)
169        B[i] = A[i];
170}
171
172void printtree(Node *p, int d)
173{
174    if (p != NULL)
175    {
176        d++;
177        printtree(p->rightson, d);
178        printf("%*s%5d\n", 3 * d, " ", p->data);
179        printtree(p->leftson, d);
180    }
181}
182
183int main(void)
184{
185    int i;
186    int S[15], A[100];
187    int d = 0;
188    new (&root);
189    make_num(A, 100);
190    make_ary(S, A, 15);
191    printf("S={ ");
192    for (i = 0; i < 15; i++)
193    {
194        printf("%d,", S[i]);
195    }
196    printf("}\n");
197    root->data = 59;
198    for (i = 0; i < 7; i++)
199    {
200        insert(S[i]);
201    }
202    insert(45);
203    delete (23);
204    printtree(root, d);
205    return 0;
206}

以上のコードを実行したところコンパイルはでき，配列の確認はできるものの，その後の処理が表示されません．
59，45や23などの整数は実行時に表示された配列からrootとする値を決めています．

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

回答2件

delete で存在しない値を指定すると v = NULL でメンバを参照します。

これでどうでしょうか？

diff
1-    while (v->data != x)
2+    while (v != NULL && v->data != x)
3
4+	if (v == NULL) return;
5     if (v->leftson == NULL || v->rightson == NULL)
6
7     new (&root);
8+	root->leftson = roo->rightson = NULL;

投稿2021/06/13 17:55

kazuma-s

総合スコア8224

その後の処理が表示されません．

というのは具体的にどんな処理でしょうか？ちょっとこれがないと答えにくいです。が、一応ざっくりコードを見てみました。

見たところ、Nodeの構造体をアロケートしてる部分で、部分木のポインタの初期化ができていないんのかもしれません。

c
1void new (Node **w, int data)
2{
3    *w = (Node *)malloc(sizeof(Node));
4　　(*w)->leftson = NULL;
5    (*w)->rightson = NULL;
6    (*w)->data = data;
7}
8