Question

c++ trie树与指针

为什么用指针写trie树，而不像线段树一样数组模拟？

Answer 1

性质：
1.根节点不包含字符，除根节点外的每一个节点都只包含一个字符。
2.从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
3.每个节点的所有子节点包含的字符都不相同。
优点：
1.查询快。对于长度为m的键值，最坏情况下只需花费O(m)的时间；而BST需要O(m log n)的时间。
2.当存储大量字符串时，Trie耗费的空间较少。因为键值并非显式存储的，而是与其他键值共享子串。
操作：
1.初始化或清空：遍历Trie，删除所有节点，只保留根节点。

Answer 2

用数组也可以实现的，你可以当做作业练习一下