基数树，赵元松+左儿子右兄弟版（白话文） .

今日系我第一日种树兼第一日整一个类第一次做数据结构小扩展，真系好值得纪念｛^____^｝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

             |    |    |     |     |

             c  x    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为根root
  for (i=0;i<strlen(str);i++)            //逐字母检索单词
  {
   while (x->brother!=NULL && x->alph!=str[i]) x=x->brother;   //检查兄弟，直到兄弟为空（吾等于尽头窝）或者搵到关键字。
   if (x->alph==' ')                                       //如果检查到当前结点关键字为空，新增关键字！！！
   {
    x->alph=str[i];                                      
    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[i]) 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[12];             //注意要额外追加一个位，摆'/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话{^___^}。