Trie树（c++实现）(二)
}
++pre->terminableSize;
}
template
void trie::insert(const char *str)
{
return insert(str, str + strlen(str));
}
template
template
bool trie::find(Iterator beg, Iterator end)
{
pNode cur = root;
pNode pre;
for(; beg != end; ++beg)
{
if(!cur->children[index[*beg]])
{
return false;
break;
}
pre = cur;
cur = cur->children[index[*beg]];
}
if(pre->terminableSize > 0)
return true;
return false;
}
template
bool trie::find(const char *str)
{
return find(str, str + strlen(str));
}
template
template
bool trie::downNodeAlone(Iterator beg)
{
pNode cur = root;
int terminableSum = 0;
while(cur->nodeSize != 0)
{
terminableSum += cur->terminableSize;
if(cur->nodeSize > 1)
return false;
else //cur->nodeSize = 1
{
for(int i = 0; i < Size; ++i)
{
if(cur->children[i])
cur = cur->children[i];
}
}
}
if(terminableSum == 1)
return true;
return false;
}
template
template
bool trie::erase(Iterator beg, Iterator end)
{
if(find(beg, end))
{
pNode cur = root;
pNode pre;
for(; beg != end; ++beg)
{
if(downNodeAlone(cur))
{
delete cur;
return true;
}
pre = cur;
cur = cur->children[index[*beg]];
}
if(pre->terminableSize > 0)
--pre->terminableSize;
return true;
}
return false;
}
template
bool trie::erase(const char *str)
{
if(find(str))
{
erase(str, str + strlen(str));
return true;
}
return false;
}
template
int trie::sizeAll(pNode ptr)
{
if(ptr == NULL)
return 0;
int rev = ptr->terminableSize;
for(int i = 0; i < Size; ++i)
rev += sizeAll(ptr->children[i]);
return rev;
}
template
int trie::sizeNoneRedundant(pNode ptr)
{
if(ptr == NULL)
return 0;
int rev = 0;
if(ptr->terminableSize > 0)
rev = 1;
if(ptr->nodeSize != 0)
{
for(int i = 0; i < Size; ++i)
rev += sizeNoneRedundant(ptr->children[i]);
}
return rev;
}
template
class Index
{
public:
int operator[](char
vchar)
{ return vchar % Size; }
};
int main()
{
trie<26, Index<26> > t;
t.insert("hello");
t.insert("hello");
t.insert("h");
t.insert("h");
t.insert("he");
t.insert("hel");
cout << "SizeALL:" << t.sizeAll(t.root) << endl;
cout << "SizeALL:" << t.sizeNoneRedundant(t.root) << endl;
t.erase("h");
cout << "SizeALL:" << t.sizeAll(t.root) << endl;
cout << "SizeALL:" << t.sizeNoneRedundant(t.root) << endl;
}