const int MaxKeySize = 25;
		typedef enum { branch, element } NODETYPE;
		
        class KeyType
		{ 						//關鍵碼的類型定義
		public:
		   char ch[MaxKeySize];					//存放關鍵碼的字符數組
		   int currentSize;						//關鍵碼的長度
		   int operator == (const KeyType &);
		} ;
		
		template <class RecordNode> class Trie;

		template <class RecordNode>
		class TrieNode {						//Trie樹結點的類定義
		friend class Trie<RecordNode>;						//友元類
		protected:
		   NODETYPE NodeType;			//結點分類
		   union NodeType {					//結點結構定義
			 struct {						//分支結點
			   int num;						//在分支結點中非空指針個數
			   TrieNode *link[27];				//下標為'b', 'a', 'b', …, 'z'的指針數組
			 } brch;
			 struct {						//元素結點
			   KeyType key;					//關鍵碼
			   RecordNode *recptr;				//指向實際數據記錄的指針
			 } elem;
		   }data;
		};

		template <class RecordNode>
		class Trie {							//Trie樹的類定義
		private:
		   TrieNode<RecordNode> *root, *current;				//Trie的根指針和當前指針
		public:
		   RecordNode* Search ( const KeyType & );
		   int Insert ( const KeyType & ); 
		   int Delete ( const KeyType & );
		};
		template <class RecordNode>
			RecordNode* Trie<RecordNode>::Search ( const KeyType & x ) {
		//在一棵Trie樹上搜索關鍵碼x。設第i-1層的分支是由關鍵碼的第i個字符決定的。
		   KeyType k = x;  
		   concatenate ( k, 'b' );				//在搜索值后面連接一個結束符'b'
		   current = root;  
		   int i = 0;					//從根開始，先在結點中判斷
		   while ( (current) && (current->NodeType != element) && (i <= k.ch[i]) )
			 { current = current->data.brch.link[k.ch[i]];  i = i++; };
			  //從根向下逐層比較, ord (k.ch[i])是字符k.ch[i]在字母表中的序號, 'b'是第0個
		   if ( (current) && current->NodeType == element && current->data.elem.key == x )
			 return current->data.elem.recptr;				//找到, 返回對應記錄位置
	 		 else return 0;						//沒有找到, 返回空地址
		}
		int KeyType:: operator == (const KeyType & d)
		{
			if (currentSize!=d.currentSize) return 0;
			for (int i=0;i<currentSize;i++)
				if (ch[i]!=d.ch[i]) return 0;
			return 1;
		};