杭电ACM1671――Phone List~~字典树

#include <iostream> #include <cstring> using namespace std; class node //结点的结构体 { public: node* P[10]; }; node* root; //定义根节点 int ans; //叶子结点数 void insert(char* str) //插入操作的函数 { int len = strlen(str); node *q, *p; q = root; for(int i = 0; i < len; i++) { int id = str[i] - '0'; if(q->P[id] == NULL) //该位置不存在，new1个 { p = new node; for(int j = 0; j < 10; j++) p->P[j] = NULL; q->P[id] = p; q = q->P[id]; } else //存在，直接等于他的后继 q = q->P[id]; } } void fun(node *a) //递归找有多少个叶子结点 { int flag = 0; for(int i = 0; i < 10; i++) { if(a->P[i] != NULL) { flag = 1; break; } } if(!flag) //该结点是叶子结点，ans++ { ans++; return; } for(int j = 0; j < 10; j++) if(a->P[j] != NULL) fun(a->P[j]); } void dele(node *a) //删除操作的函数，也是递归完成 { for(int i = 0; i < 10; i++) if(a->P[i] != NULL) dele(a->P[i]); delete a; } int main() { // freopen("data.txt", "r", stdin); int t, n; char str[15]; cin >> t; while(t--) { root = new node; ans = 0; for(int j = 0; j < 10; j++) //初始化根节点的指针数组P root->P[j] = NULL; cin >> n; for(int i = 0; i < n; i++) { cin >> str; insert(str); //插入 } fun(root); //算叶子结点数目 if(ans == n) //叶子结点等于输入的n 的个数，则YES cout << "YES" << endl; else //否则NO cout << "NO" << endl; dele(root); //删除 } return 0; }