c - 什么是十进制搜索树？

Question

我收到了以下作业，但我并不完全理解:

Write a program to implement a “Decimal Search Tree”, a popular tool used for searching in Libraries, police stations, Traffic control, …..

A Decimal search tree is a tree where each node has 10 children, one for each digit. The tree is built from the file of random 3-digit numbers generated from the first program. Obviously, the depth of the tree would be 4 levels. Then provide the following capabilities for the user:

List all numbers in the tree

Search for a certain number in the tree

Search for all numbers beginning with certain digits( e.g. “45*”)

Add a certain new number

Delete a certain number

谁能给我解释一下这是什么意思吗？我知道什么是二叉搜索树，但不明白这里的意思。

Answer 1

这看起来像是 trie data structure 的特殊版本。 trie 是一种用于存储字符串(或者在本例中为数字)的树。它的工作原理是一次将数字分解为一位数。

trie 中的每个节点总共有 10 个子指针，每个数字一个。要在 trie 中查找数字，您需要读取第一个数字，然后跟随该数字标记的指针。然后，查找第二个数字，然后跟随该数字标记的指针。重复这个过程，最终会到达 trie 中与该数字对应的节点。 trie 中的每个节点都存储一个 bool 值，指示该节点是否标记单词的结尾。因此，您可以通过检查您到达的节点是否设置了该位来检查您要查找的数字是否存在于 trie 中。

有关更多信息，我建议您查看维基百科文章。它应该有很多有用的信息!

希望这有帮助!