2分木のデータの追加

Question

###前提・実現したいこと
■概要
0~n-1のn個のデータを、ツリー構造としてリスト化
（リスト化の方法）

操作：
0<=r<=1として、①②の場合分けによって右の子を見るか、左の子を見るか判断する。
①確率rで左の子を見る
⑴左の子が空であれば、左の子に接点を作成しデータを挿入
⑵左の子が空でなければ、左の子を見る
②確率1-rで右の子を見る
⑴右の子が空であれば、右の子に節点を作成しデータを挿入
⑵右の子が空でなければ、右の子を見る

※根が空であれば、根に節点を作成し、データを挿入する

その後、
・リストアップ後ツリーの深さ(根から最も深い葉までの辺の数）
・処理時間
をprintf関数によって出力する

###発生している問題・エラーメッセージ
表出している問題としては、カウンタが適切に作動しないこと。
具体的に、出力が常に１となる。

分析したところ、insert_data関数が再帰的に呼び出されていないのではと考えています。

・仮に上記が原因であった場合、ソースコードのどこに問題があるのか。
・もしくは、他に原因がある場合それは何か。ソースコードのどこに問題があるのか。
を教授願います。

また、プログラミング初心者で、他にもコードとして不適切な部分が多々あるかと思います。その部分についても加えて指摘していただけるとありがたいです。（デバッグはすでに済ませております）

よろしくお願いいたします。

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

typedef struct _node{
    int data;
    struct _node *left;
    struct _node *right;
}NODE;

int insert_data(int d,int r,NODE *node){       /*d：データ,r:設定する確率,node:注目節点*/
    int count = 0;
    int k;
    NODE *newnode,*p;
    
    newnode = (NODE *)malloc(sizeof(NODE));
    p=newnode;
    free(newnode);
    
    p -> left = NULL;
    p -> right = NULL;
    p -> data = d;                         /*新しいノードの生成と定義*/
    
        srand(time(NULL));
        k = rand() % 100;
        
        if(k<r){
            if(node->left==NULL){
               node->left = p;        /*node_leftを見て、空っぽであれば新しいnodeを作成*/
            }
            else{
              insert_data(d,r,node->left);
            }
        }
         
        else if(r<k+1){
            if(node->right==NULL){
                node->right = p;
            }
            else if(node->right!=NULL){
               insert_data(d,r,node->right);
            }
        }
    
    count++;
    
    return count;

}

int main(void){
    
    NODE *main_node;
    main_node->left=NULL;
    main_node->right=NULL;
    main_node->data=0;      /*リストの根(root)をあらかじめ生成*/
   
    int i=1, n;
    int main_count=1;
    int s,t;
    clock_t start,end;
    double req_time;
    
    printf("nの値は：\n");
    scanf("%d",&n);
    printf("sの値は?\n");
    scanf("%d",&s);                         /*１〜１００の数字を作る→作成した乱数と比較する*/
    
    start = clock();                /*計測開始*/
    
    for(i=1;i<n;i++){
    
        t = insert_data(i,s,main_node);        /*データを次々に生成し、リストに挿入していく*/
        
        if(main_count<t){
            main_count = t;        /*最も深いところまで行っていたら（カウンタの数が現状で最大であれば）main_countに代入*/
        }
    }

    end = clock();                            /*計測終了*/
    
    req_time=(double)(end-start)/CLOCKS_PER_SEC;
    printf("処理に%.6f秒かかりました。\n",req_time);
    printf("木の深さは：%d\n",main_count);
    
    return 0;
    
}

###試したこと
誤っているのではと考える部分としては、
・ノードの作成方法（malloc関数の使用法）
・そもそもリストが上記概要の条件に沿って、適切に作成されていない
と考えています。

###補足情報(言語/FW/ツール等のバージョンなど)
・言語：C言語
・現在独学で、アルゴリズム・データ構造について学んでおります。

Answer 1

プログラミングとはコードを書いて、動かして、意図した動作でない場合は「デバッグする」ことです。これらはワンセットになっているものです。コードを書いてデバッグしないならそれはプログラミングの半分しかしていないことになります。

デバッグはすでに済ませております

プログラムが正しく動かないうちはデバッグが済んでいるといういいかたはしません。

ご質問には「自分のコードを眺めて、どこがおかしいのかを推測した」意見は書かれています。それも机上デバッグというものなので「デバッグ」の一種ではあるのですが、机上デバッグだけでプログラムの誤りを全て見つけることは（ベテランのプログラマーなら可能かも知れませんが）初心者の場合は相当困難です。プログラミングの知識が不足しているからです。

それなりの経験を積んだプログラマーであっても、計算機で実際に動かしながらプログラムの動作や途中のデータを調べつつ、判明した事実に基づいて誤りを推測していかないと、なかなかバグを見つけられないことが多いです。

計算機を動かしてデバッグしてもなかなか原因がつかめないこともあるでしょう。そういうときは「これこれのデバッグをして、この行を実行した際にこの変数の値はこうなっていた」というような自分のデバッグ結果とともに質問してください。そうすれば「どういうふうにすれば答えに結び付くか」のアドバイスが得られやすくなります。

---

一つだけ計算機を動かしても見つけるのが困難な間違い（バグ）を指摘します。mallocで確保した領域は「使っている間はfreeしてはいけません」。free(newnode)の後でp->leftなどでmallocで確保した領域そのものにアクセスしています。アクセスする可能性があるならその領域は使っていることになります。よってfreeしてはいけません。

Answer 2

具体的に、出力が常に１となる

ちゃんとロジックは理解できていませんが、insert_data()はリカーシブルコールされていますので
呼ばれる毎にインスタンスが作成されcountに0が設定され、戻る際には+1されて戻り値となります。
ですので1となります。
これを避けるには、insert_data()にパラメータとして渡すか、グローバル変数とする方法が考え
られます。

また、mainのNODE *main_node;は、
NODE *main_node = (NODE *)malloc(sizeof(NODE));とされた方がよろしいかと。

似て非なるソースですが

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

typedef struct _node{
    int data;
    struct _node *left;
    struct _node *right;
}NODE;

int count;

int insert_data(int d, int r, NODE *node){       /*d：データ,r:設定する確率,node:注目節点*/
    int k;
        NODE *p;

    k = rand() % 100;

    if(k<r){
        if(node->left==NULL){
            p = (NODE *)malloc(sizeof(NODE));
            node->left = p;        /*node_leftを見て、空っぽであれば新しいnodeを作成*/
            p->left  = NULL;
            p->right = NULL;
            p->data  = d;
        }else{
           insert_data(d,r,node->left);
        }
    } else if(r<k+1){
        if(node->right==NULL){
            p = (NODE *)malloc(sizeof(NODE));
            node->right = p;
            p->left  = NULL;
            p->right = NULL;
            p->data  = d;
        }else{
            insert_data(d,r,node->right);
        }
    }

    count++;
    return count;

}

int print_data(NODE *node){
    count++;
    if(node->left  != NULL) print_data(node->left);
    if(node->right != NULL) print_data(node->right);
    printf("no.%d (%d)\n",node->data, count);
    count--;
}

int main(void){

    NODE *main_node = (NODE *)malloc(sizeof(NODE));
    main_node->left=NULL;
    main_node->right=NULL;
    main_node->data=0;      /*リストの根(root)をあらかじめ生成*/

    int i=1, n;
    int main_count=1;
    int s,t;
    clock_t start,end;
    double req_time;

    printf("nの値は：\n");
    scanf("%d",&n);
    printf("sの値は?\n");
    scanf("%d",&s);                         /*１〜１００の数字を作る→作成した乱数と比較する*/

    start = clock();                /*計測開始*/

    for(i=1;i<n;i++){

        count = 1;
        insert_data(i,s,main_node);        /*データを次々に生成し、リストに挿入していく*/
        printf("c:%d\n",count);

        if(main_count<count){
            main_count = count;  /*最も深いところまで行っていたら（カウンタの数が現状で最大であれば）main_countに代入*/
        }
    }

    end = clock();                            /*計測終了*/

    req_time=(double)(end-start)/CLOCKS_PER_SEC;
    printf("処理に%.8f秒かかりました。\n",req_time);
    printf("木の深さは：%d\n",main_count);

    count = 0;
    print_data(main_node);

    return 0;
}

Answer 3

問題点は多々ありそうですが、パッと見ておかしいところを３点。

1. mallocしたあとすぐにfreeしている
2. count変数がinsert_data関数のローカル変数なので、単に1プラスして返却しているだけ
3. insert_data関数内でinsert_data関数を再帰呼び出しているが、戻り値を受け取っていない

1は動的メモリの理解不足です。
2と3は、再帰呼び出しの理解不足です。