C言語での２分木の挿入について

前提・実現したいこと

現在、大学の課題のアルゴリズムで２分木のところをやっているのですが、資料も全然説明がないので困っています。
C言語は基本的な知識しかなく、まだまだ未熟です。
このサイトを使うのは初めてなので、失礼なことがあったら申し訳ありません。

２時間くらいコードを見つめて考えていたんですが、やっぱりわからないです。
知りたいのはこのinsert関数でどのように処理をしているのかということです。
まず初めに、最初のstruct vertex f とnewpを宣言していますがこのfとnewpって何かわかりますか？
do~whileはまずdoの中身を実行してからwhile文の条件式に当てはまれば繰り返し実行するのですよね。
insert(10)ってところまではなんとなく？わかったのですが、insert(11)からf->dataやf->lがでてきて？？ってなりました。
fのdataなんかどこにも設定はされていないはずだし、比較する意味はあるのか？と全然わからないです。
この関数においてfやnewpはなんのことなのでしょうか？
lとrはなんとなくleftとrightなんだなというのはわかるのですが...

わからないコード

void insert(struct vertex *p, int x)   /* 2分木にxを挿入 */
{
    struct vertex *f, *newp;
    do {			/* insert(1) */
      f = p;			/* insert(2) */
      if (x < p->data)		/* insert(3) */
           p = p->l;		/* insert(4) */
      else 			/* insert(5) */
	   p = p->r;		/* insert(6) */
    } while (p != NULL);	/* insert(7) */

    p = newv();			/* insert(8) */
    p->data = x;		/* insert(9) */
    p->l = p->r = NULL;		/* insert(10) */
    if (x < f->data)		/* insert(11) */
         f->l = p;		/* insert(12) */
    else 			/* insert(13) */
	 f->r = p;		/* insert(14) */
}

該当のソースコード

C言語
1#include <stdio.h>
2#include <stdlib.h>
3
4
5struct vertex {        /*頂点を表す構造体の定義 */
6    int data;  
7    struct vertex *l, *r;
8};
9
10struct vertex *newv()  /* ヘッダのメモリー領域を確保 */
11{
12  return((struct vertex *) malloc(sizeof(struct vertex)));
13}
14
15struct vertex *create()   /* 空の2分木のセルを生成 */
16{
17    struct vertex *p;
18
19	p = newv();		/* create(1) */
20	p->data = 0;            /* create(2) */
21    	p->r = NULL;            /* create(3) */
22	p->l = NULL;            /* create(4) */
23    return(p);
24}
25
26
27
28void insert(struct vertex *p, int x)   /* 2分木にxを挿入 */
29{
30    struct vertex *f, *newp;
31    do {			/* insert(1) */
32      f = p;			/* insert(2) */
33      if (x < p->data)		/* insert(3) */
34           p = p->l;		/* insert(4) */
35      else 			/* insert(5) */
36	   p = p->r;		/* insert(6) */
37    } while (p != NULL);	/* insert(7) */
38
39    p = newv();			/* insert(8) */
40    p->data = x;		/* insert(9) */
41    p->l = p->r = NULL;		/* insert(10) */
42    if (x < f->data)		/* insert(11) */
43         f->l = p;		/* insert(12) */
44    else 			/* insert(13) */
45	 f->r = p;		/* insert(14) */
46}
47
48
49
50int member(struct vertex *p, int x)    /* 2分木内のセルの探索 */
51{
52    do {					/* member(1) */
53      if (x < p->data) 				/* member(2) */
54           p = p->l;				/* member(3) */
55       else 					/* member(4) */
56           p = p->r;				/* member(5) */
57    } while(p != NULL && x != p->data);		/* member(6) */
58    return(p != NULL);				/* member(7) */
59}
60
61void deleteb(struct vertex *p, int x)    /* 2分木内にあるセルを削除 */
62{
63    struct vertex *f, *q;
64
65    do {					/* deleteb(1) */
66      f = p;					/* deleteb(2) */
67      if (x < p->data)				/* deleteb(3) */
68           p = p->l;				/* deleteb(4) */
69      else 					/* deleteb(5) */
70	   p = p->r;				/* deleteb(6) */
71    } while(p != NULL && x != p->data);         /* ｘを探索 deleteb(7) */
72	if (p == NULL)                          /* ｘが見つからない deleteb(8) */
73        return;					/* deleteb(9) */
74    if (p->l == NULL || p->r == NULL){      	/* 一方の子がない  deleteb(10) */
75        if (p->r == NULL)			/* deleteb(11) */
76             q = p->l;				/* deleteb(12) */
77        else 					/* deleteb(13) */
78	     q = p->r;				/* deleteb(14) */
79        if (f->l == p)				/* deleteb(15) */
80             f->l = q;				/* deleteb(16) */
81        else 					/* deleteb(17) */
82	     f->r = q;				/* deleteb(18) */
83    }
84    else {                                      /* 二つの子がある deleteb(19) */
85        q = p->r;				/* deleteb(20) */
86        f = q;					/* deleteb(21) */
87        while(q->l != NULL){			/* deleteb(22) */
88           f = q;				/* deleteb(23) */
89           q = q->l;				/* deleteb(24) */
90        }					/* deleteb(25) */
91        p->data = q->data;			/* deleteb(26) */
92        if (q == f) 				/* deleteb(27) */
93             p->r = q->r;			/* deleteb(28) */
94        else 					/* deleteb(29) */
95	     f->l = q->r;			/* deleteb(30) */
96    }
97}
98
99
100
101void printtree_preorder(struct vertex *p)  /* 2分木を行きがけ順に印刷 */
102{
103    if(p == NULL)				/* printtree_preorder(1) */
104	return;					/* printtree_preorder(2) */
105    else{					/* printtree_preorder(3) */
106	  printf(" p->data = %d\n", p->data); 	/* printtree_preorder(4) */
107          printtree_preorder(p->l);		/* printtree_preorder(5) */
108          printtree_preorder(p->r);		/* printtree_preorder(6) */
109    }
110}
111
112
113  int main()
114{
115  int x;
116  struct vertex *root;
117
118  root = create();				/* main(1) */
119  printf("Next integer(0:end) = "); 		/* main(2) */
120  scanf("%d", &x);   				/* main(3) コンソールから整数を読み込む */
121  while (x != 0) {                		/* main(4) */
122    insert(root, x);                    	/* main(5) 2分木に挿入する */
123    printf("Next integer(0:end) = ");		/* main(6) */
124    scanf("%d", &x);				/* main(7) */
125  }
126      printtree_preorder(root->r);		/* main(8) */
127
128  printf("member(0:end) = ");			/* main(9) */
129    scanf("%d", &x);				/* main(10) */
130  while (x != 0 ){				/* main(11) */
131    if (member(root, x) == 1)			/* main(12) */
132	  printf("Yes\n");			/* main(13) */
133    else printf("No\n");			/* main(14) */
134	printf("member(0:end) = ");		/* main(15) */
135    scanf("%d", &x);				/* main(16) */
136  }
137
138  printf("add(0:end) = ");			/* main(17) */
139    scanf("%d", &x);				/* main(18) */
140  while (x != 0 ){				/* main(19) */
141    insert(root, x);				/* main(20) */
142	printtree_preorder(root->r);         	/* main(21) 2分木の印刷 */
143	printf("add(0:end) = ");		/* main(22) */
144    scanf("%d", &x);				/* main(23) */
145  }
146   
147  printf("delete(0:end) = ");			/* main(24) */
148    scanf("%d", &x);				/* main(25) */
149  while (x != 0 ){				/* main(26) */
150    deleteb(root, x);				/* main(27) */
151	printtree_preorder(root->r);         	/* main(28) 2分木の印刷 */
152	printf("delete(0:end) = ");		/* main(29) */
153    scanf("%d", &x);				/* main(30) */
154  }
155
156 } 
157

補足情報（FW/ツールのバージョンなど）

Cygwinで実行しています。

Daregada

2020/06/17 09:27

newp は実際には使われていないので無視。削除してもOK。

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

回答3件

何をしているかわからないのであれば、まず日本語の文章で理解してみてはいかがでしょうか。
コードを見ると、これは単なる二分木ではなく二分探索木ですね。

二分探索木 (Wikipedia)

の「操作」のあたりの文章を読んでからコードを読めばいいかと。

なお、insertの中のfは、最初のdo whileループの中で既存のノードをたどりつつ得られたpの値が設定されているので、f->dataは存在します。

投稿2020/06/17 09:45

編集2020/06/17 09:46

Daregada

総合スコア11990

yukihirotahu

2020/06/18 05:33

回答ありがとうございます。ちょっとずつわかりつつあるのですが、insert(4)とinsert(6)は何をしているのでしょうか？ p->lとp->rは両方ともNULLで何も入っていないですよね。それにｐの中にいれているのに、そのあとのinsert(8)でnewv()を使ったら上書きされて、探索した意味がなくなりませんか...? 初歩的な質問ですみません。

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