YUI's Blog

 Trie树也叫字典树，是一种用于快速检索的多叉树结构。如英文字母的字典树是一个26叉树。数字的字典树是一个10叉树。Trie树把要查找的关键词看作一个字符序列，并根据构成关键词字符的先后顺序构造用于检索的树结构；一棵m度的Trie树或者为空，或者由m棵m度的Trie树构成。特别的：和二叉查找树不同，在Trie树中，每个节点上并非存储一个元素。在Trie树中查找一个关键字的时间和树中包含的结点数无关，而取决于组成关键字的字符数。

特点：

①利用串的公共前缀->节约内存。

②根节点（root）不包含任何字母。

③其余结点仅包含一个字母（非元素）。

④每个结点的子结点包含字母不同。

查找过程：

①在Trie树上进行检索总是始于根结点。

②取得要查找关键词的第一个字母，并根据该字母选择对应的子树并转到该子树继续进行检索。

③在相应的子树上，取得要查找关键词的第二个字母，并进一步选择对应的子树进行检索。

④在某个结点处，关键词的所有字母已被取出，则读取附在该结点上的信息，即完成查找。

#include <iostream>
using namespace std;
const int M = 26 ;
const int base = 'a' ;
class Trie {
    protected:
        struct node {
            int cnt ;
            node *child[M] ;
            node( ) {
                cnt = 0 ;
                for( int i=0;i<M;i++ )
                    child[i] = NULL ;
            }
        }*root;
    public:
        Trie( ) : root( NULL ) {
            root = new node ;
        }
        void insert( char *str );
        int count( char *str );
};
void Trie::insert( char *str ) {
    node *cur = root ;
    while( cur != NULL && *str != '\0' ) {
        int index = *str - base ;
        if( cur->child[index] == NULL )
            cur->child[index] = new node ;
        cur = cur->child[index] ;
        cur->cnt ++ ;
        str++ ;
    }
}
int Trie::count( char *str ) {
    node *cur = root ;
    while( cur != NULL && *str != '\0' ) {
        int index = *str - base ;
        if( cur->child[index] == NULL )
            return 0 ;
        cur = cur->child[index] ;
        str++ ;
    }
    return cur->cnt ;
}
int main( ) {
    char str[11] ;
    Trie t ;
    while( gets(str) , strcmp(str,"") )
        t.insert( str ) ;
    while( gets(str) ) {
        printf( "%d\n" , t.count( str ) ) ;
    }
    return 0 ;
}

#include <iostream>
using namespace std;
const int M = 2 ;
const int base = '0' ;
class Trie {
	protected:
		struct node {
			bool isword ;
			node *child[M] ;
			node( ) {
				isword = false ;
				for( int i=0;i<M;i++ )
					child[i] = NULL ;
			}
		}*root ;
	public:
		Trie( ) : root(NULL) {
			root = new node ;
		}
		~Trie( ) {
			del( root ) ;
		}
		bool insert( char *str );
		void del( node *cur );
};
bool Trie::insert( char *str ) {
	node *cur = root ;
	for( int i=0;str[i];i++ ) {
		int index = str[i] - base ;
		if( cur->child[index] == NULL )
			cur->child[index] = new node ;
		else {
			if( !str[i+1] )
				return false ;
		}
		cur = cur->child[index] ;
		if( cur->isword )
			return false ;
	}
	cur->isword = true ;
	return true ;
}
void Trie::del( node *cur ) {
	if( cur == NULL ) return ;
	for( int i=0;i<M;i++ )
		if( cur->child[i] != NULL )
			del( cur->child[i] ) ;
	delete cur ;
}
int main( ) {
    char str[11] ;
    int Case = 1 ;
    while( gets(str) ) {
        if( str[0] == '9' ) continue ;
        Trie t ;
        bool flag = t.insert( str ) ;
        while( gets(str) , str[0] != '9' ) {
            if( flag && ! t.insert( str ) )
                flag = false ;
        }
        printf( "Set %d is " , Case++ );
        if( !flag ) printf( "not " );
        printf( "immediately decodable\n" );
    }
    return 0 ;
}

#include <iostream>
using namespace std;
const int M = 10 ;
const int base = '0' ;
class Trie {
	protected:
		struct node {
			bool isword ;
			node *child[M] ;
			node( ) {
				isword = false ;
				for( int i=0;i<M;i++ )
					child[i] = NULL ;
			}
		}*root ;
	public:
		Trie( ) : root(NULL) {
			root = new node ;
		}
		~Trie( ) {
			del( root ) ;
		}
		bool insert( char *str );
		void del( node *cur );
};
bool Trie::insert( char *str ) {
	node *cur = root ;
	for( int i=0;str[i];i++ ) {
		int index = str[i] - base ;
		if( cur->child[index] == NULL )
			cur->child[index] = new node ;
		else {
			if( !str[i+1] )
				return false ;
		}
		cur = cur->child[index] ;
		if( cur->isword )
			return false ;
	}
	cur->isword = true ;
	return true ;
}
void Trie::del( node *cur ) {
	if( cur == NULL ) return ;
	for( int i=0;i<M;i++ )
		if( cur->child[i] != NULL )
			del( cur->child[i] ) ;
	delete cur ;
}
int main( ) {
	int T,n ;
	char str[11] ;
	scanf( "%d" , &T );
	while( T-- && scanf( "%d%*c" , &n ) ) {
		Trie t ;
		bool flag = true ;
		while( n-- && gets(str) ) {
			if( flag && ! t.insert( str ) )
				flag = false ;
		}
		puts( flag ? "YES" : "NO" );
	}
	return 0 ;
}

#include <iostream>
#include <cstring>
using namespace std;
const int M = 26 ;
const int base = 'a' ;
class Trie {
	protected:
		struct node {
			bool isword ;
			node *child[M] ;
			node( ) {
				isword = false ;
				for( int i=0;i<M;i++ )
					child[i] = NULL ;
			}
		}*root ;
	public:
		Trie( ) : root(NULL) {
			root = new node ;
		}
		~Trie( ) {
			del( root );
		}
		bool insert( char *str );
		void del( node *cur );
};
bool Trie::insert( char *str ) {
	node *cur = root ;
	for( int i=0;str[i];i++ ) {
		int index = str[i] - base ;
		if( cur->child[index] == NULL )
			cur->child[index] = new node ;
		cur = cur->child[index] ;
	}
	if( cur->isword )
		return false ;
	else
		cur->isword = true ;
	return true ;
}
void Trie::del( node *cur ) {
	if( cur == NULL ) return ;
	for( int i=0;i<M;i++ )
		if( cur->child[i] != NULL )
			del( cur->child[i] ) ;
	delete cur ;
}
int main( ) {
	char str[1000] ;
	while( gets(str) , str[0] != '#' ) {
		Trie t ;
		char *p = strtok( str , " " );
		int sum = 0 ;
		while( p ) {
			bool flag = true ;
			if( ! t.insert( p ) )
				flag = false ;
			if( flag ) sum ++ ;
			p = strtok( NULL , " " );
		}
		printf( "%d\n" , sum );
	}
	return 0 ;
}

#include <iostream>
#include <string>
using namespace std;
const int M = 26 ;
const int base = 'a' ;
class Trie {
protected:
	struct node {
		char str[11] ;
		node *child[M] ;
		node( ) {
			str[0] = '\0' ;
			for( int i=0;i<M;i++ )
				child[i] = NULL ;
		}
	}*root ;
public:
	Trie( ) : root(NULL) {
		root = new node ;
	}
	void insert( char *str , char *word );
	void find( const char *str );
};
void Trie::insert( char *str , char *word ) {
	node *cur = root ;
	for( int i=0;str[i];i++ ) {
		int index = str[i] - base ;
		if( cur->child[index] == NULL )
			cur->child[index] = new node ;
		cur = cur->child[index] ;
	}
	strcpy( cur->str , word );
}
void Trie::find( const char *str ) {
	node *cur = root ;
	for( int i=0;str[i];i++ ) {
		int index = str[i] - base ;
		if( cur->child[index] == NULL ) {
			printf( "%s" , str ); return ;
		}
		cur = cur->child[index] ;
	}
	if( strcmp(cur->str,"") == 0 )
		printf( "%s" , str );
	else printf( "%s" , cur->str );
}
int main( ) {
	char sms[3000+1] , str[10+1] , str2[10+1] ;
	Trie t ;
	scanf( "%s" , &str );
	while( scanf( "%s" , &str ) , strcmp(str,"END") ) {
		scanf( "%s" , &str2 );
		t.insert( str2 , str );
	}
	scanf( "%s%*c" , &str );
	while( gets(sms) , strcmp(sms,"END") ) {
		string tmp = "" ;
		for( int i=0;sms[i];i++ ) {
			if( sms[i] <= 'z' && sms[i] >= 'a' )
				tmp += sms[i] ;
			else {
				end:;
				t.find( tmp.c_str() );
				printf( "%c" , sms[i] );
				tmp = "" ;
			}
		}
		if( tmp != "" )
			goto end;
		printf( "\n" );
	}
	return 0 ;
}

#include <iostream>
#include <algorithm>
using namespace std;
const int M(26) ;
const int base('a') ;
struct xx {
	char str[20] ;
	xx( ) {
		str[0] = '\0';
	}
}word[50000] ;
class Trie {
protected:
	struct node {
		bool isword ;
		node *child[M] ;
		node( ) : isword(0) {
			for( int i=0;i<M;i++ )
				child[i] = NULL ;
		}
	}*root ;
public:
	Trie( ) : root(new node) {}
	void insert( char *str ) {
		node *cur(root) ;
		for( int i=0;str[i];i++ ) {
			int index = str[i] - base ;
			if( cur->child[index] == NULL )
				cur->child[index] = new node ;
			cur = cur->child[index] ;
		}
		cur->isword = 1 ;
	}
	void ishat( char *str ) {
		node *cur = root ;
		for( int i=0;str[i];i++ ) {
			int index = str[i] - base ;
			cur = cur->child[index] ;
			if( cur->isword && str[i+1] != '\0' && query( &str[i+1] ) ) {
				printf( "%s\n" , str ); return ;
			}
		}
	}
	bool query( char *str ) {
		node *cur(root);
		for( int i=0;str[i];i++ ) {
			int index( str[i] - base );
			if( cur->child[index] == NULL )
				return false ;
			cur = cur->child[index] ;
		}
		return cur->isword ;
	}
};
bool cmp( const xx & a , const xx & b ) {
	return strcmp( a.str , b.str ) < 0 ;
}
int main( ) {
	Trie t ;
	int n(0) ;
	while( scanf( "%s%*c" , &word[n].str ) != EOF ) {
		t.insert( word[n].str );
		n++ ;
	}
	sort( word , word+n , cmp );
	for( int i(0);i<n;i++ ) {
		t.ishat( word[i].str );
	}
//	system("pause");
	return 0 ;
}