基数树，赵元松+左儿子右兄弟版（白话文） .
今日系我第一日种树兼第一日整一个类第一次做数据结构小扩展，真系好值得纪念｛^____^｝Y首先介绍一下基数树，呢种树位于二叉查找树岛，生长系基数二叉树树林。基数树系一种有分类作用ge数据结构，我以呢种树为基础结构，以字母为关键字，加左统计域count实现字典查找。
总ge黎讲就系：
基础结构：基数树
增加域：count（统计包含【从某根到呢个结点所组成ge前缀】ge单词树）
维护新域：插入ge时候每经过一个点，该点数目加一。
支持操作：Insert，Search。
专门适合解决类似呢种ge问题：
先输入n个单词，再输入n个前缀，求包含前缀ge单词有几个：
Simple Input：
fuck
sex
dick
shit
annal
fu
s
c
Simple Output：
1
2
0
姐系字典查找甘ge野{= =}凸
Tire可以系一种无根树，亦可以讲Root有兄弟，例如上面ge样例输入可以生成一颗以下甘ge树：
f---s------d---a
| | | |
u e--h i n
| | | | |
cx i c n
| | | |
k t k a
|
l
其中每个结点包含三个域，son（最左ge儿子），brother（右兄弟），count,一个关键字alph。
1、建树：
可以简单插入单词黎建树。即运行n次Insert就ok啦~~~最坏情况O(26*maxlen）。【maxlen为所输入最长字符串】
2、查找：
顺住前缀字母落下一层。直到检索完单词返回该结点count，最坏情况都系O（26*maxlen）。
下面结合我ge代码黎讲啦就{>O<}V
hdu 1251 156ms 15600K 1201B C++ 10SGetEternal{（。）（。）}!
#include<string>#include<iostream>using namespace std; struct node //定义树d结点{ node *son,*brother; char alph; int count;}; class tire //定义一颗树{ private: node *root,*x,*w; //只定义指针根root，x系寻迹指针，w系临时指针（型d就叫开辟指针） public:tire () //构造函数，初始化根. {make_node(root); }~tire(){}; //析构函数。void make_node(node *&point) //制造细路ge过程，所以就叫做make_****(node) {point=new node;point->son=NULL;point->brother=NULL;point->count=0;point->alph=' '; }void Insert(char *str) //插入去ge过程，唔洗递归 {int i;x=root; //初始化寻迹指针x为根rootfor (i=0;i<strlen(str);i++) //逐字母检索单词{ while (x->brother!=NULL && x->alph!=str) x=x->brother; //检查兄弟，直到兄弟为空（吾等于尽头窝）或者搵到关键字。 if (x->alph==' ') //如果检查到当前结点关键字为空，新增关键字！！！ { x->alph=str; make_node(w); //调用制造细路 x->brother=w; //再将岩岩出世ge细路当系自己细佬 } x->count++; //累计单词+1 if (i<strlen(str)-1 && x->son==NULL)//&&前边系省空间用ge，下边唔洗讲拉下哇｛= =｝ { make_node(w); x->son=w; } x=x->son;} }int Search(char *str) //查找过程~~~~~~，唔系好复杂，自己睇 {int i;x=root;for (i=0;i<strlen(str);i++){ while (x!=NULL && x->alph!=str) x=x->brother; if (x==NULL) return 0; //其实我等于系每层增加左一个哨兵。 else if (i<strlen(str)-1) x=x->son; }return x->count; //如果搵唔到系上面return 0就会结束，黎到呢度一定搵到啦~~~~ }}; int main() //主函数{ tire zkl; char word; //注意要额外追加一个位，摆'/n‘ while (gets(word) && strlen(word)!=0) //读入空行等于长度为零咯~~ {zkl.Insert(word); //不断插入 } while (gets(word)) {printf("%d/n",zkl.Search(word)); //不断mid出 } return 0;}
最后，我无整Clear成员，留翻d细路系度（赵元松），并且距地d关系好复杂{OTZ}
其实可以用h（n）=n Hash表，会快n倍，但系我想试下左孩子右兄弟，所以空间复杂度系少左，但系慢左好多~~~
听日再种一种，如果得ge话{^___^}。
页:
[1]