c言語 二分木探索の出力について

Question

C言語で以下のプログラムを書いています。

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

28
insert 20
insert 19
insert 50
find 61
find -100
find 20
print
insert 1000000000
insert 1
insert 18
insert 5
insert 3
insert 7
insert 30
insert 25
insert 40
insert 41
insert 42
find 3
find 7
find 42
find 20
find 1000000000
find 23
find 2
find 60
find 100
print

入力が上のようなときの出力を

no
no
yes
19 20 50
20 19 50
yes
yes
yes
yes
yes
no
no
no
no
1 3 5 7 18 19 20 25 30 40 41 42 50 1000000000
20 19 1 18 5 3 7 50 30 25 40 41 42 1000000000

のようにしたいのですが、自分の書いたコードだと少し違った表示になってしまいます。

自分の書いたコード

#include<stdio.h>
#include<stdlib.h>
#define MAX 500000

 typedef struct node{
    int key;
    struct node *right;
    struct node *left;
}node;

node *mk_node(int);
node *insert(node *,int);/*今回はMAXの要素数が決められていないのでmallocで確保する必要がある*/
void prn0(void);
void prn1(node *);
void prn2(node *);
node *search(node *,int);
int N;
int j=0;
int result[MAX];

int main(){
int i,data,fin_data;
for( i = 0 ; i < MAX ; i++){
    result[i] = 0;
}

char order[20];
node *root = NULL;
node *res;
scanf("%d",&N);

for( i = 0 ; i < N ; i++ ){
   scanf("%s",order);



      if(order[0]=='i'){
        scanf("%d",&data);
         root = insert(root,data);
      }

      else if(order[0]=='f'){
        scanf("%d",&fin_data);
      res = search(root,fin_data);
      if(res!=NULL){
        result[j]=1;
      j++;
      }
      
      if(res==NULL) {
        result[j]=-1;
        j++;
      }
      }
      

      else if(order[0]=='p'){
        prn0();
        prn1(root);
        printf("\n");
        prn2(root);
        printf("\n");
    /*二通りの方法で出力するために関数を呼び出す*/
      }

}

return 0;
}

node *insert(node *new_node,int data){
    if(new_node == NULL){
        new_node = mk_node(data);
    }
    else if(new_node -> key < data){
        new_node -> right = insert(new_node -> right,data);
    }
    else{
        new_node -> left = insert(new_node -> left,data);
    }
    return new_node;
}

node *search(node *Node,int fin_data){
  while( Node != NULL ){
    if(Node->key == fin_data)return Node;
    if(Node->key > fin_data){
        Node = Node->left;
    } 
    else{
    Node = Node -> right;
  }

  }
return NULL;
}






node *mk_node(int data){
node *new_node;

new_node = (node*)malloc(sizeof(node));
   if(new_node == NULL){
    printf("メモリ確保失敗\n");
    }
    new_node->key = data;
    new_node->left = NULL;
    new_node->right = NULL;
    return new_node;
}


void prn0(void){
    int i;
    for( i = 0; i < j ; i++){
        if(result[i]==1)printf("yes\n");
        else printf("no\n");
}
}

void prn1(node *Node)
{    
    if(Node != NULL){
       //if(cun > 0)printf(" ");
        prn1(Node -> left);
        printf(" %d",Node -> key);
        prn1(Node->right);
    }
    }

void prn2(node *Node){ 
    if(Node != NULL){
        printf(" %d",Node->key);
        prn2(Node -> left);
        prn2(Node -> right);
    }
    }

自分で書いたコードを実行すると

28
insert 20
insert 19
insert 50
find 61
find -100
find 20
print
no
no
yes
 19 20 50
 20 19 50
insert 1000000000
insert 1
insert 18
insert 5
insert 3
insert 7
insert 30
insert 25
insert 40
insert 41
insert 42
find 3
find 7
find 42
find 20
find 1000000000
find 23
find 2
find 60
find 100
print
no
no
yes
yes
yes
yes
yes
yes
no
no
no
no
 1 3 5 7 18 19 20 25 30 40 41 42 50 1000000000
 20 19 1 18 5 3 7 50 30 25 40 41 42 1000000000

すべての命令を読み取った後に、その命令に対する結果を出力したいです。
自分の書いたコードを実行すると、一つ目のprint命令が読み取られた時点でに表示まで行ってしまいます…

補足

print以外の命令に対しては正常に機能しています

Comments

[jimbe]

>こんな感じになってしまいます。

それで、どこまで調査されているのでしょうか。

[bennkyoutyu]

説明不足で申し訳ないです。
printの命令以外は正常に機能しているので、insertとfindは大丈夫だと思います。
すべての命令を入力し、実行後のそれぞれの命令にたいする出力という形にしたいです。

[jimbe]

本当に、「すべての命令を入力し、実行後のそれぞれの命令にたいする出力」が求められているのでしょうか。
もしそうなら、そのままコード化すれば良いでしょう。つまり、入力だけを全て行って保存し、それから全てに対して順に insert/find/print することです。
最大 500000 件を保存するのにどれだけのメモリが必要になるか、慎重に決めてください。

Answer 1

恐らくこの問題は、入力と出力を別として考えて良いと思います。
つまり、 insert は即 insert 処理を行い、 find/print は即それぞれの表示を行って、結果として画面上は入力と出力が混在しますが、入力の行/出力の行それぞれ"だけ"を見たらしたい風になっていれば良いのではないでしょうか。

リンク先の例でいえば、実行して入力していった結果の画面は

> a.out
10
insert 30
insert 88
insert 12
insert 1
insert 20
find 12
yes ← find の出力
insert 17
insert 25
find 16
no ← find の出力
print
 1 12 17 20 25 30 88 ← print の出力
 30 12 1 20 17 25 88 ← print の出力
>

で Ok なのでは無いかということです。

Comments

[bennkyoutyu]

無事解決しました。ありがとうございました。