Ｃ言語関係掲示板過去ログ１３３８

過去ログ

No．１３３８　単語を二分探索木に挿入し、中・先・後走査でプリント

No.18086		自己参照構造体投稿者---oohasi(2004/11/14 17:51:29)
		使用者に１行文字を入力してもらい、単語に分解し、それらの単語を二分探索木に挿入し、それを中・先・後走査でプリントしたいのですがうまくいきません。どなたか、知恵を貸していただけたらと思います。自分なりのプログラムは、 <pre>#include <stdio.h> #include <stdlib.h> #include <string.h> struct treeNode { /自己参照構造体/ struct treeNode leftPtr; char data; struct treeNode rightPtr; }; typedef struct treeNode TreeNode; typedef TreeNode TreeNodePtr; /関数プロトタイプ/ void insertNode( TreeNodePtr , char * ); void inOrder( TreeNodePtr ); void preOrder( TreeNodePtr ); void postOrder( TreeNodePtr ); int main() { char buff[256]; char ptr; TreeNodePtr rootPtr = NULL; / 入力された文字列を二分木に挿入する / printf( "二分木に挿入する値:\n" ); gets( buff ); ptr = strtok( buff, " " ); while ( ptr != NULL ) { ptr = strtok( NULL, " " ); insertNode( &rootPtr, ptr ); } / 二分木を先順走査でなぞる / printf( "\n\n先順走査の結果:\n" ); preOrder( rootPtr ); / 二分木を中順走査でなぞる / printf( "\n\n中順走査の結果:\n" ); inOrder( rootPtr ); / 二分木を後順走査でなぞる / printf( "\n\n後順走査の結果:\n" ); postOrder( rootPtr ); return 0; } void insertNode( TreeNodePtr treePtr, char value ) { if ( treePtr == NULL ) { /* treePtr is NULL / treePtr = malloc( sizeof( TreeNode ) ); if ( treePtr != NULL ) { ( treePtr )->data = value; ( treePtr )->leftPtr = NULL; ( treePtr )->rightPtr = NULL; } else{ printf( "空きメモリがないため%d は挿入できません。\n", value ); } } else{ if ( value < ( treePtr )->data ){ insertNode( &( ( treePtr )->leftPtr ), value ); } else if ( value > ( treePtr )->data ){ insertNode( &( ( treePtr )->rightPtr ), value ); } } } /二分木を中順走査でなぞる/ void inOrder( TreeNodePtr treePtr ) { if ( treePtr != NULL ) { inOrder( treePtr->leftPtr ); printf( "%3d", treePtr->data ); inOrder( treePtr->rightPtr ); } } /二分木を先順走査でなぞる/ void preOrder( TreeNodePtr treePtr ) { if ( treePtr != NULL ) { printf( "%3d", treePtr->data ); preOrder( treePtr->leftPtr ); preOrder( treePtr->rightPtr ); } } /二分木を後順走査でなぞる/ void postOrder( TreeNodePtr treePtr ) { if ( treePtr != NULL ) { postOrder( treePtr->leftPtr ); postOrder( treePtr->rightPtr ); printf( "%3d", treePtr->data ); } } です。お願いします。

No.18089

Re:自己参照構造体
投稿者---RAPT(2004/11/14 21:31:06)

まずは整形。読み難くって仕方がない。

# 折角HTML変換ツール使った後があるのに、確認画面で確認しないから
# 最悪の投稿文になってしまう。読み直せば気付くはずなのに…。

```
使用者に１行文字を入力してもらい、
```
※注：空白区切りで複数の単語を入力してもらう
```
単語に分解し、
```

それらの単語を二分探索木に挿入し、

それを中・先・後走査でプリントしたい



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

struct treeNode { /*自己参照構造体*/
    struct treeNode *leftPtr;
    char data;
    struct treeNode *rightPtr;
};

typedef struct treeNode TreeNode;
typedef TreeNode *TreeNodePtr;
/*関数プロトタイプ*/
void insertNode( TreeNodePtr *, char * );
void inOrder( TreeNodePtr );
void preOrder( TreeNodePtr );
void postOrder( TreeNodePtr );

int main()
{ 
    char buff[256];
    char *ptr;
    TreeNodePtr rootPtr = NULL;
    
    /* 入力された文字列を二分木に挿入する */
    printf( "二分木に挿入する値:\n" );
    gets( buff );
    ptr = strtok( buff, " " );
    while ( ptr != NULL ) {
        ptr = strtok( NULL, " " );
        insertNode( &rootPtr, ptr );
    }
    
    /* 二分木を先順走査でなぞる */
    printf( "\n\n先順走査の結果:\n" );
    preOrder( rootPtr );
    
    /* 二分木を中順走査でなぞる */
    printf( "\n\n中順走査の結果:\n" );
    inOrder( rootPtr );
    
    /* 二分木を後順走査でなぞる */
    printf( "\n\n後順走査の結果:\n" );
    postOrder( rootPtr );
    
    return 0;
}

void insertNode( TreeNodePtr *treePtr, char *value )
{ 
    if ( *treePtr == NULL ) { /* *treePtr is NULL */
        *treePtr = malloc( sizeof( TreeNode ) );
        
        if ( *treePtr != NULL ) { 
            ( *treePtr )->data = *value;
            ( *treePtr )->leftPtr = NULL;
            ( *treePtr )->rightPtr = NULL;
        }
        else{
            printf( "空きメモリがないため%d は挿入できません。\n", value );
        }
    }
    else{
        if ( *value < ( *treePtr )->data ){
            insertNode( &( ( *treePtr )->leftPtr ), value );
        }
        else if ( *value > ( *treePtr )->data ){
            insertNode( &( ( *treePtr )->rightPtr ), value );
        }
    }
}
/*二分木を中順走査でなぞる*/
void inOrder( TreeNodePtr treePtr )
{ 
    if ( treePtr != NULL ) { 
        inOrder( treePtr->leftPtr );
        printf( "%3d", treePtr->data );
        inOrder( treePtr->rightPtr );
    }
}
/*二分木を先順走査でなぞる*/
void preOrder( TreeNodePtr treePtr )
{ 
    if ( treePtr != NULL ) { 
        printf( "%3d", treePtr->data );
        preOrder( treePtr->leftPtr );
        preOrder( treePtr->rightPtr );
    }
}
/*二分木を後順走査でなぞる*/
void postOrder( TreeNodePtr treePtr )
{ 
    if ( treePtr != NULL ) { 
        postOrder( treePtr->leftPtr );
        postOrder( treePtr->rightPtr );
        printf( "%3d", treePtr->data );
    }
}

No.18090

Re:自己参照構造体
投稿者---RAPT(2004/11/14 21:36:53)

で、分かりやすくなったので回答。

> ptr = strtok( buff, " " );
> while ( ptr != NULL ) {
>     ptr = strtok( NULL, " " );
>     insertNode( &rootPtr, ptr );
> }
最初の単語が切り捨てられ、最後にアクセス違反となる。


ptr = strtok( buff, " " );
while ( ptr != NULL ) {
    insertNode( &rootPtr, ptr );
    ptr = strtok( NULL, " " );
}
通常はこのように書く。


> ( *treePtr )->data = *value;
これは、「文字」のコピーだが、目的を満たしているか？


> printf( "空きメモリがないため%d は挿入できません。\n", value );
%d と value？　valueの型は char * だから、アドレスを表示させようとしている？
アドレスを表示するなら %p が適切だが。

No.18091		Re:自己参照構造体投稿者---oohasi(2004/11/14 22:41:26)
		分かりにくくなってしまい申し訳ございません。そしてわざわざ書き直して頂けき、ありがとうございます。 > ptr = strtok( buff, " " ); > while ( ptr != NULL ) { > ptr = strtok( NULL, " " ); > insertNode( &rootPtr, ptr ); > } 最初の単語が切り捨てられ、最後にアクセス違反となる。 ptr = strtok( buff, " " ); while ( ptr != NULL ) { insertNode( &rootPtr, ptr ); ptr = strtok( NULL, " " ); } 通常はこのように書く。　この部分を直し、実行すると数字がプリントアウトされるようになりました。入力された文字を出力するには、 > ( treePtr )->data = value; これは、「文字」のコピーだが、目的を満たしているか？この部分を直せば良いのでしょうか？また、 > printf( "空きメモリがないため%d は挿入できません。\n", value ); %d と value？　valueの型は char * だから、アドレスを表示させようとしている？アドレスを表示するなら %p が適切だが。この部分は確かにその通りです。ご指摘ありがとうございます。

No.18096

Re:自己参照構造体
投稿者---RAPT(2004/11/15 00:37:21)

？？？
何がやりたいか、がかかれていないことに気付いています？

なにをどうしたくて、こんなことしたら、こうなると思ったが、こうなった。
これがこうなるようにしたいのだが、どうすればよいか？

と具体的に書いてください。


えー、「文字」を出力するなら %c です。
「文字列」（単語）を扱いたいなら、構造体を書き換えて、「文字列」を
扱えるようにする必要があります。

「文字列」の大小関係を比較するには strcmp()関数を使用します。

No.18101		Re:自己参照構造体投稿者---oohasi(2004/11/15 01:17:35)
		申し訳ないです。何がやりたいか、がかかれていないことに気付いています？＞最初に書いた気でいました。したい事は、二分木に挿入する値： On a clear day you can see forever. 先順走査: On a clear can day you see forever. 中順走査: On a can clear day forever. see you 後順走査: can forever. see you day clear a On となる様にしたいのです。（赤が使用者入力部分）今のままでは、 /二分木を中順走査でなぞる/ void inOrder( TreeNodePtr treePtr ) { if ( treePtr != NULL ) { inOrder( treePtr->leftPtr ); printf( "%%c", treePtr->data ); inOrder( treePtr->rightPtr ); } } としても文字しか出力されず、文字列を出すためにはどうすればいいのでしょうか？えー、「文字」を出力するなら %c です。「文字列」（単語）を扱いたいなら、構造体を書き換えて、「文字列」を扱えるようにする必要があります。＞文字列を扱いたいのです。構造体を書き換えるとは具体的にどうゆう事でしょうか？質問ばかりですいません。

No.18143

Re:自己参照構造体
投稿者---RAPT(2004/11/15 22:23:22)

char data;
は「文字」です。「文字列」を扱うには「文字」の「配列」を使います。
char data[100];
とすると、「文字」100個分の「文字列」を保存できます。

２－４．文字と文字列
でその違いを勉強してきてください。

No.18150

Re:自己参照構造体
投稿者---oohasi(2004/11/16 02:43:12)

返答ありがとうございます。何か基礎ができてないのにい難しい事をしすぎなのかも知れませんが、ここまでやったので自分の意思通り動くようにするには、どうすればいいのかがとても勉強になる気がするので質問させて下さい。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define SIZE 256
struct treeNode { /*自己参照構造体*/
    struct treeNode *leftPtr;
    char data;
    struct treeNode *rightPtr;
};

typedef struct treeNode TreeNode;
typedef TreeNode *TreeNodePtr;
/*関数プロトタイプ*/
void insertNode( TreeNodePtr *, char );
void inOrder( TreeNodePtr );
void preOrder( TreeNodePtr );
void postOrder( TreeNodePtr );

int main()
{ 
    char buff[SIZE];
    char *ptr;
    TreeNodePtr rootPtr = NULL;

    /* 入力された文字列を二分木に挿入する */
    printf( "\n" );
    gets( buff );
    ptr = strtok( buff, " " );
    while ( ptr != NULL ) {
        insertNode( &rootPtr, *ptr );
        ptr = strtok( NULL, " " );
    }

    /* 二分木を先順走査でなぞる */
    printf( "\n\n先順走査の結果:\n" );
    preOrder( rootPtr );

    /* 二分木を中順走査でなぞる */
    printf( "\n\n中順走査の結果:\n" );
    inOrder( rootPtr );

    /* 二分木を後順走査でなぞる */
    printf( "\n\n後順走査の結果:\n" );
    postOrder( rootPtr );

    return 0;
}

void insertNode( TreeNodePtr *treePtr, char value )
{ 
    if ( *treePtr == NULL ) {     /* *treePtr is NULL */
        *treePtr = malloc( sizeof( TreeNode ) );

        if ( *treePtr != NULL ) { 
            ( *treePtr )->data = value;
            ( *treePtr )->leftPtr = NULL;
            ( *treePtr )->rightPtr = NULL;
        }
        else{
            printf( "空きメモリがないため%p は挿入できません。\n", value );
        }
    }
    else{
        if ( value < ( *treePtr )->data ){
            insertNode( &( ( *treePtr )->leftPtr ), value );
        }
        else if ( value > ( *treePtr )->data ){
            insertNode( &( ( *treePtr )->rightPtr ), value );
        }
    }
}
/*二分木を中順走査でなぞる*/
void inOrder( TreeNodePtr treePtr )
{ 
    if ( treePtr != NULL ) { 
        inOrder( treePtr->leftPtr );
        printf( "%c ", treePtr->data );
        inOrder( treePtr->rightPtr );
    }
}
/*二分木を先順走査でなぞる*/
void preOrder( TreeNodePtr treePtr )
{ 
    if ( treePtr != NULL ) { 
        printf( "%c ", treePtr->data );
        preOrder( treePtr->leftPtr );
        preOrder( treePtr->rightPtr );
    }
}
/*二分木を後順走査でなぞる*/
void postOrder( TreeNodePtr treePtr )
{ 
    if ( treePtr != NULL ) { 
        postOrder( treePtr->leftPtr );
        postOrder( treePtr->rightPtr );
        printf( "%c ", treePtr->data );
    }
}

このプログラムで最初の文字が出る様になりました。当たり前と言われそうですが・・・。
実行結果としては、
C:\kaitou>mojiretu
二分木に挿入する値:
I am looking for job.
先順走査の結果：
i a f l j
中順捜査の結果：
a f i j l
後順走査の結果：
f a j l i
となります。
ここで言われた通り、配列にしなければ文字列を表現することが不可能なのは分かるのですが、どこを配列にしても結果がうまく出ません。勿論、二分木をなぞる時には変換仕様を%cから%sには変えて実行してるのですが・・・。今回の場合どこを配列にすればいいのでしょうか？

No.18154		Re:自己参照構造体投稿者---かずま(2004/11/16 04:26:52)
		> ここで言われた通り、配列にしなければ文字列を表現することが不可能なのは > 分かるのですが、どこを配列にしても結果がうまく出ません。 > 勿論、二分木をなぞる時には変換仕様を%cから%sには変えて実行してるのです > が・・・。今回の場合どこを配列にすればいいのでしょうか配列は既に存在します。main() の char buff[SIZE]; です。今回の場合､ gets(buff); を一度しか実行しないので､buff が上書きされることはありません。 strtok で切り出した文字列を TreeNode構造体の data が指せばよいでしょう。 char data; ---> char data; void insertNode( TreeNodePtr , char ); ---> void insertNode( TreeNodePtr , char ); insertNode( &rootPtr, ptr ); ---> insertNode( &rootPtr, ptr ); void insertNode( TreeNodePtr treePtr, char value ) ---> void insertNode( TreeNodePtr treePtr, char value ) printf( "空きメモリがないため%p は挿入できません。\n", value ); ---> printf( "空きメモリがないため%s は挿入できません。\n", value ); if ( value < ( treePtr )->data ){ ---> int diff = strcmp(value, (treePtr)->data); if (diff < 0) { else if ( value > ( *treePtr )->data ){ ---> else if (diff > 0) { printf( "%c ", treePtr->data ); (3箇所) ---> printf( "%s ", treePtr->data );

No.18179		Re:自己参照構造体投稿者---oohasi(2004/11/17 03:37:12)
		>gets(buff); を一度しか実行しないので､buff が上書きされることはありません。なるほど。storkの勉強をした時も配列は１つの宣言で良かったので、それを参考にすれば良かったんですね。（勝手な納得でした。）遅くなりましたがとても参考になりました。ありがとうございました。