trie in linked list

linked_list_trie.cpp

#include <cstdio>
#include <cstdlib>
#include <string>
#include <fstream>
#include <iostream>

//#define DEBUG

using namespace std;

struct Node{
	char ch;
	bool isword;
	Node* sibling;
	Node* children;
	Node(char c='\0'): ch(c)
	{
		isword = false;
		sibling = NULL;
		children = NULL;
	}
};

void str_insert(Node *root, const string& str)
{
	Node *tmp, *pt = root;
	for(int i=0;str[i];i++){
		if(pt -> children == NULL){
			fprintf(stderr, "new a node %c\n", str[i]);
			pt -> children = new Node(str[i]);
			pt = pt -> children;
			continue;
		}
		if(pt -> children -> ch > str[i]){
			fprintf(stderr,"new node %c at start\n", str[i]);
			tmp = new Node(str[i]);
			tmp -> sibling = pt -> children;
			pt -> children = tmp;
			pt = tmp;
			continue;
		}
		pt = pt -> children;
		while(pt->sibling && (pt->sibling->ch) <= str[i]){
			fprintf(stderr, "pass %c\n", pt->ch);
			pt = pt-> sibling;
		}
		if(pt->ch == str[i]){
			fprintf(stderr, "found character %c\n", str[i]);
			continue;
		}
		if(!(pt->sibling)){
			fprintf(stderr, "reach end, create node %c at end\n", str[i]);
			pt -> sibling = new Node(str[i]);
			pt = pt -> sibling;
		}else{
			fprintf(stderr, "insert %c between two nodes %c-%c\n", str[i], pt->ch, pt->sibling->ch);
			tmp = new Node(str[i]);
			tmp -> sibling = pt -> sibling;
			pt -> sibling = tmp;
			pt = tmp;
		}
	}
	fputs("mark as valid word\n", stderr);
	pt -> isword = true;
}

bool str_search(Node *root, const string& str)
{
	Node *pt = root;
	for(int i=0;str[i];i++){
		pt = pt -> children;
		if(pt == NULL){
			fputs("meets trie end\n", stderr);
			return false;
		}
		while(pt && pt->ch < str[i])
			pt = pt -> sibling;
		if(!pt || pt->ch != str[i]){
			fprintf(stderr, "cannot find %c, ", str[i]);
			if(!pt)
				fputs("reach end\n", stderr);
			else
				fprintf(stderr, "stop after reach %c\n", pt->ch);
			return false;
		}
		fprintf(stderr, "find %c\n", pt->ch);
	}
	fputs("node found, return isword\n", stderr);
	return pt->isword;
}

void print_trie(Node *root, int level)
{
#ifndef DEBUG
	return ;
#endif
	if(!root)
		return ;
	Node *pt = root;
	for(int i=0;i<level;i++)
		putchar('=');
	if(root->ch == '\0')
		puts("root");
	else
		printf("%c\n", root->ch);
	print_trie(root->children, level+1);
	print_trie(root->sibling, level);
}

int main(int argc, char *argv[])
{
	string line;
	Node *root = new Node;
#ifndef DEBUG
#ifdef WIN32
	freopen("nul","w",stderr);
#else
	freopen("/dev/null","w",stderr);
#endif
#endif
	ifstream fin("input.txt");
	ifstream fser("search.txt");

	while(getline(fin, line)){
		cout << "insert " << line << endl;
		str_insert(root, line);
	}

	print_trie(root, 0);

	while(fser >> line){
		cout << "search " <<  line << " : " << (str_search(root, line)?"valid":"invalid") << endl;
	}

	return 0;
}