単語数算出二分木の再帰版

K&R本 6.5

前回の記事で単語算出の処理を書きました。

ですがK&Rのサンプルを見ていると二分木にデータを追加する処理に再帰を使っていました。

ということで僕が作ったプログラムも再帰版に書き換えてみようかと思います。

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

#define WORDMAX 100

struct NODE {
    char *word;
    int count;
    struct NODE *left;
    struct NODE *right;
};
typedef struct NODE NODE;

NODE *create_node (char *str);
NODE *add_node (NODE *head,char *str);
void preorder(NODE *n);
int getword (char *word,int max);

NODE *create_node (char *str) {
    NODE *node;
    size_t len = strlen(str);
    node = (NODE *)malloc(sizeof(NODE));
    if ( node == NULL ) {
        return NULL;
    }
    node->count = 1;
    node->right = node->left = NULL;
    node->word = (char *)malloc(len+1);
    if ( node->word == NULL ) {
        return NULL;
    }
    strcpy_s(node->word,len+1,str);
    return node;
}

// 再帰で実装する
NODE *add_node (NODE *p,char *str) {
    int strtype;
    if ( p == NULL ) {
        p = create_node(str);
    }
    else if ( (strtype = strcmp(str,p->word)) == 0 ) {
        p->count++;
    }
    else if ( strtype > 0 ) {
        p->right = add_node(p->right,str);
    }
    else {
        p->left = add_node(p->left,str);
    }
    return p;
}

void preorder(NODE *n){
    if( n == NULL ) return;
    printf("%s = %d\n", n->word,n->count );
    preorder( n->left );
    preorder( n->right );
}

// とりあえず英数字_のみ
int getword (char *word,int max) {
    int c;
    while( (c=getchar()) != EOF ) {
        if ( (isalnum(c)||c=='_') && --max ) {
            *word++ = (char)c;
        }
        else {
            break;
        }
    }
    *word = '\0';
    return c;
}

int main (void) {
    NODE *head = NULL;
    char str[WORDMAX];
    
    while ( getword(str,WORDMAX) != EOF ) {
        if ( strlen(str) ) head = add_node(head,str);
    }
    
    preorder(head);
    return 0;
}

add_node関数がめちゃくちゃシンプルになりました。再帰とマッチしてますね。素晴らしいです。