トライ木を用いた検索について

[yude]

あけましておめでとうございます。

さっそくですが、質問させていただきます。

後期の学校の課題があり1月15日までに、タイトルにある「トライ木を用いた検索」を行いたいです。
検索と言っても、辞書検索のようなものではなく、真理値表における数値検索を行いたいのです。
例えば、

001[tab=30]1
010[tab=30]2
011[tab=30]2
100[tab=30]3
11*[tab=30]4

のような真理値表があったとします(左は2進数で、右は出力する値の10進数、 * はドントケアを意味する)。
このときキーボードからの入力で001と入力すれば、1と出力し、110や111の入力があった場合は4と出力したいです。

まずトライ木について調べるうちに、二分木やソート、連結リスト、ポインタなどを知っておかなければならないと思い
図書館で「Cで学ぶデータ構造とプログラム(Leendert Ammeraal著, オーム社)」を借り、一通り勉強しました。
この本では辞書検索用のトライ木について述べられており、このプログラムをどうにか利用して目的のプログラムを書こうと考えました。
まず参考書のプログラムを以下に記載します。

コード:

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<ctype.h>
#define MAXWORDLENGTH 80
#define NBRANCHES ('Z'-'A'+2)	//　27のこと, ASCII文字の時

typedef struct{
	int num;
	void *ptr[NBRANCHES];	//	子とデータの2種類指すため void 型
}branchnode;

typedef struct{
	int num;
	char *key;
}datanode;

typedef branchnode *brptr;
typedef datanode *dataptr;

void error(char *str)
{
	printf("\nError: %s\n", str);
	exit(1);
}

void printtrie(void *p)
{
	dataptr dp = (dataptr) p;

	void *q;
	int k;

	if(dp->num)					//	num > 0 のとき、pはデータノードを指す
		printf("%5d %s\n", dp->num, dp->key);
	else						//	num = 0 のときは、pは分岐ノードを指す
		for(k = 0; k < NBRANCHES; k++){
			if((q = ( ( brptr ) p)->ptr[k] ) != NULL )		//	(brptr) p で分岐ノードに変換
				printtrie(q);
		}
}

dataptr found(void *p, char *word)
{
	int i = 0, k;
	char ch;

	dataptr dp = (dataptr) p;	//	データノードの場合
	brptr bp = (brptr) p;		//	分岐ノードの場合

	while(p != NULL && bp->num == 0){
		ch = word[i++];
		k = (ch ? ch - 'A' + 1 : 0);			//	アルファベットが何番目か(ch = Aのときは1番目, Zのときは26番目e.t.c.)
		if(k < 0 || k >26)				//	アルファベット以外のとき
			return NULL;

		p = bp->ptr[k];						
		bp = (brptr) p;						
	}	

	dp = (dataptr) p;
	return (p == NULL ? NULL : strcmp(word, dp->key) == 0 ? dp : NULL);
	
}

brptr newbrnode(void)
{
	brptr bp;
	int k;

	bp = (brptr) malloc(sizeof(branchnode));
	if(bp == NULL)
		error("Not enough memory");

	bp->num = 0;
	for(k = 0; k < NBRANCHES; k++){
		bp->ptr[k] = NULL;
	}
	return bp;
}

dataptr newdatanode(char *word)
{
	char *pch;
	dataptr dp;

	dp = (dataptr) malloc(sizeof(datanode));
	pch = (char *) malloc(strlen(word) + 1);

	if(dp == NULL || pch == NULL)
		error("Not enough memory");
	
	strcpy(pch, word);
	dp->num = 1;
	dp->key = pch;

	return dp;
}

void insert(void **pp, char *word, int i)	//	wordをトライ木に挿入。引数ppはこのトライ木の根のアドレスを含んでいる。
{
	char ch, ch1;
	brptr bp, bp1;
	dataptr dp;
	int k, k1;

	for(;;){
		if(*pp == NULL){
			*pp = (void *)newdatanode(word);
			break;
		}	
		bp = *(brptr *) pp;		//	分岐ノードの場合
		dp = *(dataptr *) pp;		//	データノードの場合
		ch = word[i];
		k = (ch ? ch - 'A' + 1 : 0);
				
		if(bp->num == 0)		//	分岐ノード
			pp = &bp->ptr[k];
		else{				//	データノード
			if(strcmp(word, dp->key) == 0){
				dp->num++;
				break;
			}
			bp1 = newbrnode();
			*pp = (void *) bp1;
			ch1 = dp->key[i];	//	既存のデータノードの文字
			k1 = (ch1 ? ch1 - 'A' + 1 : 0);
			bp1->ptr[k1] = (void *) bp;
			pp = &bp1->ptr[k];
		}
		i++;
	}
}

int getword(FILE *fp, char *str)
{
	int ch, i=0;
	
	while(ch = getc(fp), ch != EOF && !isalpha(ch));	//	英字でない文字を読み飛ばす

	while(isalpha(ch)){					//	英字が続く限りstrに読み込む
		str[i++] = toupper(ch);
		ch = getc(fp);
		if(i > MAXWORDLENGTH)
			error("Word too long");
	}
	str[i] = '\0';
	return i;
}

int main(void)
{
	FILE *fp;
	char filename[51], word[MAXWORDLENGTH + 1];
	void *root;
	dataptr q;

	printf("Input file : ");
	scanf("%50s", filename);

	fp = fopen(filename, "r");
	if(fp == NULL)
		error("File not available");

	root = NULL;
	while(getword(fp, word) > 0)
		insert(&root, word, 0);
	fclose(fp);

	printf("\nContents of file:\n");
	
	if(root != NULL)
		printtrie(root);
	
	while( printf("\nEnter a word, or type STOPSEARCH to stop: "), getword(stdin, word), strcmp(word, "STOPSEARCH") ){
		q = found(root, word);
		if(q == NULL)
			printf("key not found\n");
		else
			printf("key found : count field = %d\n", q->num);
	}
				
	return 0;
}

今、私が分からないこととしては、プログラムの内容(insert関数の部分)もそうですが、
まず目的のプログラムを書くにあたっての方針が分かりません。
参考プログラムにおいて、「この関数をこういう方針にすればいいのでは？」や「こういう関数が必要」等の
アドバイスをいただけないのでしょうか？

ご教授よろしくお願いいたします。


環境 　
　OS ： Windows 7
　コンパイラ名 ： Borand C++