我目前正在尝试创建一种使用二叉树的方法,该方法可查找用户输入的单词的字谜。
如果树不包含该单词的任何其他字谜(即,如果键不在树中,或者关联链表中的唯一元素是用户提供的单词),则会显示消息“未找到任何字谜”
例如,如果键“ opst”出现在树中,并且带有包含单词“ spot”,“ pots”和“ tops”的关联链接列表,并且用户输入了单词“ spot”,则程序应打印“ pots”和“顶部”(但不是现货)。
public boolean find(K thisKey, T thisElement){
return find(root, thisKey, thisElement);
}
public boolean find(Node current, K thisKey, T thisElement){
if (current == null)
return false;
else{
int comp = current.key.compareTo(thisKey);
if (comp>0)
return find(current.left, thisKey, thisElement);
else if(comp<0)
return find(current.right, thisKey, thisElement);
else{
return current.item.find(thisElement);
}
}
}
当我创建此方法以查找提供的元素是否在树(以及关联的键)中时,被告知不要重复使用此代码来查找字谜。
K是扩展Comparable并表示键的泛型类型,T是表示列表中项的泛型类型。
如果需要我做过的其他方法,我可以编辑这篇文章,但是我绝对迷路了。 (只需要一个正确方向的指针)
最佳答案
尚不清楚到底是什么使您绊倒(除了“我写了一个不错的查找方法,但不允许使用它。”),所以我认为最好的方法是从头开始。
我认为您会发现,以正确的方式构造数据后,实际的算法将相对容易遵循(许多计算机科学问题都具有此功能)。
您有三件事:
1)许多链表,每个链表包含一组字母的字谜集。我假设您可以根据需要生成这些列表。
2)二叉树,将字符串(键)映射到从这些字符串生成的字谜列表。再次,我假设您能够对这些树执行基本操作-添加元素,按键查找元素等。
3)用户输入的字符串。
见解:一组字母的字谜形成一个等效类。这意味着字谜列表的任何成员都可以用作与列表关联的键。此外,这意味着您无需在树中存储指向同一列表的多个键(前提是我们对结构化数据有点聪明;请参见下文)。
具体来说,树中的“ spot”和“ opts”键都不需要指向同一列表,因为一旦您可以使用任何“ spot”字谜找到列表,就可以得到所有“ spot”字谜。 “点”。
巧妙地构建数据:鉴于我们的洞察力,假设我们的树为每个独特的字谜集恰好包含一个键。因此,“ opts”映射到{“ opts”,“ pots”,“ spot”等}。如果我们的用户给我们提供了一个我们不将其用作字谜集的键的字符串,会发生什么?我们如何弄清楚如果用户键入“ spot”,我们应该找到以“ opts”为键的列表?
答案是将存储在我们数据结构中的数据标准化。这是一种计算机科学的说法,即我们对存储数据的方式执行任意规则。 (对数据进行规范化是一种有用的技术,在许多不同的计算机科学领域中都会反复出现。)第一个规则是,树中只有一个键可以映射到给定的链表。其次,如果我们确保实际存储的每个密钥都是可预测的,那又意味着即使用户键入“ spot”,我们也应该搜索“ opts”怎么办?
有许多方法可以实现这种可预测性-一种简单的方法是确保每个键的字母都按字母顺序排列。然后,我们知道每个字谜集将由按字母顺序排在首位的集合中的(唯一!)成员键入。始终执行该规则可以轻松搜索树-我们知道,无论用户提供什么字符串,我们想要的键都是由按字母顺序输入用户输入形成的字符串。
放在一起:我将在此处提供高级算法,以使其更加具体。
1)从用户那里获取一个字符串(保留此字符串,稍后我们将需要它)
2)将此字符串转换为遵循我们规范化方案的搜索关键字
(您可以在“ K”类的构造函数中执行此操作,以确保您在程序的任何位置都不会拥有未归一化的密钥。)
3)在树中搜索该键,并获取与其关联的链接列表。此列表包含用户输入字符串的每个字谜。
4)打印列表中不是用户原始字符串的每个项目(请参阅为什么我们方便使用该字符串?)
外卖:
通常,您的数据会具有一些特殊的功能,使您更加聪明。在这种情况下,事实是字谜列表的任何成员都可以是我们为该列表存储的唯一键。
对数据进行标准化可以使您具有可预测性,并可以有效地对其进行推理。如果每个键都可以是其字谜列表的任意成员,那么“查找”算法将有多困难?
结论:使数据结构完全正确(我要存储什么?各部分之间如何连接?它如何表示?)将使编写算法变得更加容易。
关于java - 使用二叉树查找字谜,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/3717343/