标准trie树应用之串排序

缘起

本文给出标准trie的第二个应用——字符串排序

问题: 给定n个互不相同的小写英文单词， 请将他们按照字典序从小到大输出

分析

算法是显然的——首先使用这些单词建立trie树，因为trie的子节点都是按照字典序升序排序的，所以只需要先序遍历trie即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include "stdafx.h"

#include <stdio.h>
#include <string.h>
#define LOCAL


const int SIZE = 26;

typedef struct TrieNode
{
	int ch;
	bool end;
	TrieNode *next[SIZE];
	TrieNode(int ch=0):ch(ch),end(false) {memset(next, 0, sizeof(next));}
}TrieNode,*Trie;

void init(Trie &root) {root = new TrieNode;}

void insert(Trie root, char *key)
{
	Trie p = root;
	int i = 0;
	while(key[i])
	{
		if (!p->next[key[i]-'a']) p->next[key[i]-'a'] = new TrieNode(key[i]);
		p = p->next[key[i++]-'a'];
	}
	p->end =  true;
}

void print(Trie current, char *text, int n) // 先序遍历trie, current是当前节点, text是当前已经积攒的要打印的字符, n是当前已经积攒的字符串长度
{
	if (current->ch) text[n] = current->ch; // 只有当前字符存在的时候(根节点就不行),才加入
	if (current->end) // 如果当前节点是一个字符串的结束, 则就要打印了
	{
		text[n+1] = 0;
		puts(text);
	}
	for (int i = 0;i<SIZE; i++)
	{
		if (current->next[i])
		{
			print(current->next[i], text, n+1); // 遍历其子节点
		}
	}
}

void del(Trie &root)
{
	if (!root) return;
	for (int i = 0; i<SIZE; i++)del(root->next[i]);
	delete root;
	root = 0;
}


int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	Trie root = 0;
	init(root);
	char key[15];
	while(~scanf("%s", key)) insert(root, key);
	print(root, key, -1); // 之所以是-1. 是因为-1对应根节点, 根节点一定不会奏效(因为它的ch是0)
	del(root);
	return 0;
}
/*
测试数据
jack jacktom hanmeimei lilei hansmith mikxin lizhi mike
*/