c言語で二分探索木を実装したいです

回答ではありません。
https://paiza.io/ja/projects/new?language=c
上記URLがwebで実行可能なCコンパイラです。
こちらで、実行してみてください。
エラーがたくさん出ます。
会員にならなくても、とりあえず、実行はできるみたいです。
但し、本格的に使うなら、会員になったほうが良いかも知れません。

蛇足ですが、下記が私の環境でコンパイルした結果です。(ソースはgoo1.cとしています)
（Mingw gcc version 8.3.0 (x86_64-posix-seh, Built by strawberryperl.com project)）

D:\goo\c>vgcc goo1.c
<gcc goo1.c -o goo1.exe --input-charset=cp932 --exec-charset=cp932>
goo1.c: In function 'search':
goo1.c:20:17: error: 'key' redeclared as different kind of symbol
     struct node key;
                 ^~~
goo1.c:18:18: note: previous definition of 'key' was here
 NODE *search(int key)
              ~~~~^~~
goo1.c:26:13: error: invalid operands to binary == (have 'struct node' and 'int')
     if (key == p->data)
             ^~ ~~~~~~~
goo1.c:30:5: error: 'else' without a previous 'if'
     else if (key < (p->data)) {
     ^~~~
goo1.c:30:18: error: invalid operands to binary < (have 'struct node' and 'int')
     else if (key < (p->data)) {
                  ^ ~~~~~~~~~
goo1.c:33:10: error: expected '}' before 'else'
          else
          ^~~~
goo1.c: In function 'insert':
goo1.c:44:9: error: 'key' redeclared as different kind of symbol
     int key;
         ^~~
goo1.c:42:18: note: previous definition of 'key' was here
 NODE *insert(int key)
              ~~~~^~~
goo1.c:57:5: error: expected '}' before 'else'
     else
     ^~~~
goo1.c:63:14: warning: implicit declaration of function 'malloc' [-Wimplicit-function-declaration]
      if((new=malloc(sizeof(NODE)))=NULL)
              ^~~~~~
goo1.c:63:14: warning: incompatible implicit declaration of built-in function 'malloc'
goo1.c:63:14: note: include '<stdlib.h>' or provide a declaration of 'malloc'
goo1.c:2:1:
+#include <stdlib.h>

goo1.c:63:14:
      if((new=malloc(sizeof(NODE)))=NULL)
              ^~~~~~
goo1.c:63:35: error: lvalue required as left operand of assignment
      if((new=malloc(sizeof(NODE)))=NULL)
                                   ^
goo1.c:64:6: warning: implicit declaration of function 'error'; did you mean 'perror'? [-Wimplicit-function-declaration]
      error("out of memory!!");
      ^~~~~
      perror
goo1.c: In function 'delete':
goo1.c:79:9: error: 'key' redeclared as different kind of symbol
     int key;
         ^~~
goo1.c:77:16: note: previous definition of 'key' was here
 int delete(int key)
            ~~~~^~~
goo1.c:103:14: warning: implicit declaration of function 'deletemin'; did you mean 'delete'? [-Wimplicit-function-declaration]
           *p=deletemin(&x->right);
              ^~~~~~~~~
              delete
goo1.c:103:13: warning: assignment to 'NODE *' {aka 'struct node *'} from 'int' makes pointer from integer without a cast [-Wint-conversion]
           *p=deletemin(&x->right);
             ^
goo1.c:104:23: error: lvalue required as left operand of assignment
           &(*p)->right=x->right;
                       ^
goo1.c:105:22: error: lvalue required as left operand of assignment
           &(*p)->left=x->left;
                      ^
goo1.c:108:7: warning: implicit declaration of function 'free' [-Wimplicit-function-declaration]
       free(x);
       ^~~~
goo1.c:108:7: warning: incompatible implicit declaration of built-in function 'free'
goo1.c:108:7: note: include '<stdlib.h>' or provide a declaration of 'free'
goo1.c: At top level:
goo1.c:125:7: error: conflicting types for 'deletemin'
 NODE *deletemin(NODE **p)
       ^~~~~~~~~
goo1.c:103:14: note: previous implicit declaration of 'deletemin' was here
           *p=deletemin(&x->right);
              ^~~~~~~~~
goo1.c:137:1: warning: return type defaults to 'int' [-Wimplicit-int]
 preorder(NODE *p)
 ^~~~~~~~
goo1.c: In function 'preorder':
goo1.c:141:5: warning: 'return' with no value, in function returning non-void
     return;
     ^~~~~~
goo1.c:137:1: note: declared here
 preorder(NODE *p)
 ^~~~~~~~
goo1.c:150:1: warning: implicit declaration of function 'inorder'; did you mean 'preorder'? [-Wimplicit-function-declaration]
 inorder(NODE *p)
 ^~~~~~~
 preorder
goo1.c:150:9: error: expected expression before 'NODE'
 inorder(NODE *p)
         ^~~~
goo1.c:150:17: error: expected ';' before '{' token
 inorder(NODE *p)
                 ^
                 ;
 {
 ~
goo1.c:230:1: error: expected declaration or statement at end of input
 }

インラインで回答します。

① まず、
NODE *search(int key)
教科書に書いてあったこの宣言の仕方がよく分かりません

型名なしの関数の宣言の仕方を調べると一つだけ解説しているサイトが見つかり、自動的にint型になると書　　いてあったのですが正しいのでしょうか？
(回答：正しいです。 sub(int key) と int sub(int key)は同じとみなされます。

引数があり、戻り値がある場合はvoid型ではない、（回答：正しい 例 int sub(int key)の場合）
引数があり、戻り値がない場合はvoid型、（回答：正しい 例 void sub(int key)の場合）
引数がなし、戻り値がある場合もvoid型、（回答：誤り 例 int sub(void) は引数なしのint型を返す関数）
引数がなし、戻り値がない場合もvoid型   回答：正しい 例 void sub(void)の場合）
と学びました

preorder(NODE *p)
postorder(NODE *p)
inorder(NODE *p)
これらの関数は引数があり、戻り値がない場合なのでvoid型、
回答：正しい。正確には
void preorder(NODE *p)
void postorder(NODE *p)
void inorder(NODE *p)
と記述すべきです。

int delete(int key)
この関数も引数があり、戻り値がない場合なのでvoid型だと思われるのですがなぜint型なのでしょうか
回答：戻り値はあります。int型です。あなたのソースの中で
return 1;
return 0;
の個所で、0又は1のint型のデータを戻り値として返しています。

NODE *search(int key)
NODE *insert(int key)
NODE *deletemin(NODE **p)
これらの関数は引数があり、戻り値がある場合はvoid型ではない、int型だと思います。
回答：誤り　NODE型へのポインターが戻り値です。NODE型へのポインター型です。int型ではありません。

②keyの扱い方についてです

if (key == p->data)
ここの部分で教科書では関数を使って比べていましたがむずかしいので不等号を使って比べることにしました
keyは値ですが、p->dataは番地ですよね
回答：p->dataは値です。
printf("追加する数字を入力してください\n");
scanf("%d",&a);
で入力した数値が格納されます。
p->dataのpは番地（ポインター）です。p->dataは値です。
従ってif (key == p->data)は何の問題もありません。

同じように値同士で扱うにはどのようにしたら良いのでしょうか
構造体の場合、アロー演算子は番地、ドットが実体だと習いましたがエラーが出てしまいます

③関数の値渡しについてです
case 1:
printf("追加する数字を入力してください\n");
scanf("%d",&a);
insert(a);
break;
case 5:
printf("指定した値の番地を出力します\n");
scanf("%d",&key1);
search(key1);
break;

case 6:
printf("指定した値を削除します\n");
scanf("%d",&key2);
delete(key2);
break;

ここの部分で出力する場合の値と指定した値の変数名はそれぞれ変えたほうが良いですよね？
回答：a,key1,key2は全てint型なので同じにしても良いが、変えておいた方が、良いでしょう。
意味的に異なる変数は、別々に確保したほうが判りやすくなります。

④探索した値の番地を出力する際に、

/* もしキーと注目している節のデータとが等しければポインタを関数として返す */
printf("探索した値の番地です>>%d\n",p->data);
return p;
としていますが、めちゃくちゃな状態です
探索した値の番地を返す場合、 return pはどのように扱えば良いのか悩みます。
回答：p->dataは探索した値のデータです。したがって
printf("探索した値のデータです>>%d\n",p->data);
printf("探索した値の番地（アドレス）です>>%p\n",p);
return p;
とします。
ポインター(p)を印字する場合は %pを使用します。