我目前正在学习二叉树和二叉搜索树,我正在进行的一项练习涉及读取文本文件,按字母顺序将每个单词存储在二叉树中,并使用不同的方法遍历树。以下是具体规格:
读入文本并构建包含文本中所有单词的二叉搜索树(按字母顺序),存储单词并在节点中记录单词的频率(每个单词在文本中出现的次数),并执行课堂上提到的树遍历。
我的问题是,当我将单词添加到树中时,如何跟踪它的频率?我们从来没有在课堂上讨论过相同的节点,所以我被困在这里。任何建议表示赞赏!
我目前正在学习二叉树和二叉搜索树,我正在进行的一项练习涉及读取文本文件,按字母顺序将每个单词存储在二叉树中,并使用不同的方法遍历树。以下是具体规格:
读入文本并构建包含文本中所有单词的二叉搜索树(按字母顺序),存储单词并在节点中记录单词的频率(每个单词在文本中出现的次数),并执行课堂上提到的树遍历。
我的问题是,当我将单词添加到树中时,如何跟踪它的频率?我们从来没有在课堂上讨论过相同的节点,所以我被困在这里。任何建议表示赞赏!
简单的。二叉树节点将由两个元素组成,一个是字符串(比如键),另一个是整数计数(比如值)。在添加元素时检查它是否已经存在,如果是,则简单地增加计数,否则将元素添加为计数为 1 的新二叉树节点。
很难回答家庭作业问题...
因此,您的节点显然会包含它所代表的单词。当您插入一个新词时,您会创建节点,但在此之前,您会搜索该词。如果您的树中已经存在该单词的节点,只需检索该节点并在其中增加一个计数器。
public class MyNode
{
String word;
Integer counter;
}
得到它?:)
将单词添加到树时如何跟踪单词的频率
1)除了 a 的data
left
和right
成员之外,每次尝试在树中添加现有单词时, TreeNode
添加另一个成员并递增 1。count
2)您可以使用单独的哈希表来保留单词和出现的映射。如果单词存在于哈希表中,只需增加计数。如果它不存在,则将其添加到树中。由于哈希表,这需要额外的空间
使用 HashMap,用 String、Integer 填充。遍历文本中的单词,如果尚未添加,则将其放入 Integer(occurrence) == 1 的地图中。如果之前添加过,则将 Integer 增加 1。
处理完所有文本后,您可以使用 String 和 Integer 填充对象列表,根据它们的 compareTo 方法对它们进行排序。
以防有人需要。
scala BST 容器的实现。
trait BSTree[+A]
case object Empty extends BSTree[Nothing]
case class Node[+A](left: BSTree[A], x: A, right: BSTree[A]) extends BSTree[A]
object BSTree {
def insert[T](t: BSTree[T], k: T)(
implicit ord: T => Ordered[T]
): BSTree[T] = t match {
case Empty => Node(Empty, k, Empty)
case Node(l, x, r) if k < x => Node(insert(l, k), x, r)
case Node(l, x, r) if k == x => Node(l, k, r)
case Node(l, x, r) => Node(l, x, insert(r, k))
}
def toList[T](t: BSTree[T]): List[T] = t match {
case Empty => Nil
// preorder traverse
case Node(l, x, r) => x :: toList(l) ++ toList(r)
}
def apply[T](as: T*)(implicit ord: T => Ordered[T]): BSTree[T] = as.foldLeft(
Empty: BSTree[T])((t, e) => insert(t, e))
}
object Main extends App {
case class WordCount(c: Char, var count: Int) {
override def toString: String = s"'$c' -> $count"
}
implicit def wordCountConvert(x: WordCount): Ordered[WordCount] =
(that: WordCount) => if (x.c.<(that.c)) -1
else if (x.c == that.c) {
that.count = x.count + 1
0
} else 1
val content = "Scala Cool!"
val wordCountTree = BSTree(content.filter(_.isLetter).map(WordCount(_, 1)): _*)
println(BSTree.toList(wordCountTree))
}
并在此处输出
List('S' -> 1, 'C' -> 1, 'c' -> 1, 'a' -> 2, 'a' -> 1, 'l' -> 2, 'o' -> 2, 'l' -> 1, 'o' -> 1)