二分探索木を使って英単語と日本語のペアを辞書順にソートしたいのですが、出力が出ません

Question

実現したいこと・発生している問題

標準入力された複数の英単語・日本語のペアを二分探索木を使って辞書順にソートてから標準出力するプログラムをCで実現したいのですが、出力が何も表示されません。

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

root@LAPTOP-DJMEGTF2:~# valgrind ./a.out
==38== Memcheck, a memory error detector
==38== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==38== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==38== Command: ./a.out
==38== 
==38== error calling PR_SET_PTRACER, vgdb might block
sugar 砂糖
egg 卵
coffee コーヒー 
milk 牛乳
tea 紅茶    //入力の終了はこの場合Ctrl+Dで 知らせます 
==38== 
==38== HEAP SUMMARY:
==38==     in use at exit: 264 bytes in 15 blocks
==38==   total heap usage: 17 allocs, 2 frees, 4,368 bytes allocated 
==38==
==38== LEAK SUMMARY:
==38==    definitely lost: 200 bytes in 5 blocks
==38==    indirectly lost: 64 bytes in 10 blocks
==38==      possibly lost: 0 bytes in 0 blocks
==38==    still reachable: 0 bytes in 0 blocks
==38==         suppressed: 0 bytes in 0 blocks
==38== Rerun with --leak-check=full to see details of leaked memory 
==38== 
==38== For counts of detected and suppressed errors, rerun with: -v 
==38== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0) 
root@LAPTOP-DJMEGTF2:~# 

Valgrindで確認してみたところ、このように入力をノードとしてメモリに格納すること自体はちゃんとできているようなのですが、printfによる出力が何も出ない上に、freeでメモリ解放したはずが出来ていません。

該当のソースコード

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>

typedef char* String; //後で使いやすくできるよう、ここでStringタイプを定義しちゃいます。

typedef struct node_{
    struct node_* left; //左の子へのポインタ
    struct node_* right; //右の子へのポインタ
    struct node_* parent; //親へのポインタ
    String key; //探索に使うキー(この場合は英単語の見出し)
    String value; //付属値(この場合は対応する日本語)
}* node; //二分探索木のノードです。

typedef struct{
    node root; //根節点のポインタ
}* tree; //二分探索木の構造体を定義します

#define left(x) (x->left)
#define right(x) (x->right)
#define parent(x) (x->parent)
#define key(x) (x->key)
#define value(x) (x->value)
#define root(T) (T->root)
#define NEW(p, n){p = malloc((n)*sizeof(p[0]));}

int key_cmp(String p, String q){
    int c1, c2;
    int i=0;
    while(1){
        c1=p[i]; c2=q[i];
        if(c1<c2) return -1;
        if(c1>c2) return 1;
        if(c1==0) break;
        i++;
    }
    return 0;
} //英単語の見出しを比較する関数

node node_new(String eng, String jpn){
    node x;
    NEW(x, 1);
    left(x)=NULL;
    right(x)=NULL;
    parent(x)=NULL;
    key(x)=eng;
    value(x)=jpn;
    return x;
} //新しいノードを作成

tree tree_new(void){
    tree T;
    NEW(T, 1);
    root(T) = NULL;
    return T;
} //新しい二分探索木を作成

void tree_insert(tree T, node z){ //二分探索木Tにzを挿入する
    node x, y;
    y=NULL;
    x=root(T);
    if(x==NULL) {x=z; return;} //Tが空ならzを根節点にして終わり
    while(right(x) != NULL && left(x) != NULL){
        if (key_cmp(key(z), key(x)) < 0) {x=left(x);}
        else                        {x=right(x);}
    } //zを挿入する場所xを決める
    if(right(x) == NULL && left(x) == NULL) {y=x;} 
    else if(right(x) == NULL && left(x) != NULL) {x=left(x); y=parent(x);} 
    else {x=right(x); y=parent(x);} //yはxの親

    parent(z)=y; //zの親をyにする
    if (key(z) < key(y)) {left(y) = z;} //yの子をzにする
    else {right(y) = z;}
    printf("%s %s\n", key(y), value(y)); //デバッグ用。ここでも出力が出ません。。。
}

void inorder_tree_walk(node x){ //木の根からたどることにより全てのキーをソートされた順序で出力
    if (x != NULL){
        inorder_tree_walk(left(x));
        printf("%s %s\n", key(x), value(x));
        inorder_tree_walk(right(x));
    }
}

void free_nodes(node x){
    if (x != NULL){
        free_nodes(left(x));
        free_nodes(right(x));
        free(key(x));
        free(value(x));
        free(x);
    }
}   

void free_tree(tree T){
    free_nodes(root(T));
    free(T);
}

int main(int argc, char *argv[]){
    tree T;
    node x;
    char buf1[1000], buf2[1000];
    char* eng; //英単語の見出しに相当
    char* jpn; //日本語訳に相当
    T=tree_new();
    while(1){
        if (scanf("%s %s", buf1, buf2)<2) break;
        eng=strdup(buf1);
        jpn=strdup(buf2);
        x=node_new(eng, jpn);
        printf("%s %s\n", key(x), value(x)); //デバッグ用。ここはちゃんと出力が出ます。
        tree_insert(T, x);
    }
    inorder_tree_walk(root(T));
    free_tree(T);
    return 0;
}

試したこと

デバッグのためにprintfをtree_insertで使ってみたのですが、そこでも何も出力は出ないようです。となるとtree_insertで二分探索木に挿入するコードがどこかおかしいのかと思いま。

ちなみにnode_new(eng, jpn);の直後のprintfはちゃんと出力がでるので、ノードはちゃんと作れていると思います。

Answer 1

次の修正でどうなりますか？

     node x, y;
     y=NULL;
     x=root(T);
-    if(x==NULL) {x=z; return;} //Tが空ならzを根節点にして終わり
-    while(right(x) != NULL && left(x) != NULL){
-        if (key_cmp(key(z), key(x)) < 0) {x=left(x);}
-        else                        {x=right(x);}
-    } //zを挿入する場所xを決める
-    if(right(x) == NULL && left(x) == NULL) {y=x;} 
-    else if(right(x) == NULL && left(x) != NULL) {x=left(x); y=parent(x);} 
-    else {x=right(x); y=parent(x);} //yはxの親
-
-    parent(z)=y; //zの親をyにする
-    if (key(z) < key(y)) {left(y) = z;} //yの子をzにする
-    else {right(y) = z;}
-    printf("%s %s\n", key(y), value(y)); //デバッグ用。ここでも出力が出ません。。。
+    if (x == NULL) { root(T)=z; return; } //Tが空ならzを根節点にして終わり
+
+	while (1) {
+		if (key_cmp(key(z), key(x)) < 0) {
+			if (left(x)) x = left(x);
+			else { left(x) = z; parent(z) = x; return; }
+		}
+		else {
+			if (right(x)) x = right(x);
+			else { right(x) = z; parent(z) = x; return; }
+		}
+	}
 }

Comments

[aardvark]

ありがとうございます！できました。

Answer 2

void tree_insert(tree T, node z){ //二分探索木Tにzを挿入する
    node x, y;
    y=NULL;
    x=root(T);
    if(x==NULL) {x=z; return;} //Tが空ならzを根節点にして終わり
//               ^^^ ここで T->root が書き換えられていないのでは? T->root = z じゃないと
    ...

Comments

[aardvark]

コメントありがとうございます。
確かに、そこは見落としておりました。