1

我目前正在学习二叉树和二叉搜索树,我正在进行的一项练习涉及读取文本文件,按字母顺序将每个单词存储在二叉树中,并使用不同的方法遍历树。以下是具体规格:

读入文本并构建包含文本中所有单词的二叉搜索树(按字母顺序),存储单词并在节点中记录单词的频率(每个单词在文本中出现的次数),并执行课堂上提到的树遍历。

我的问题是,当我将单词添加到树中时,如何跟踪它的频率?我们从来没有在课堂上讨论过相同的节点,所以我被困在这里。任何建议表示赞赏!

4

5 回答 5

3

简单的。二叉树节点将由两个元素组成,一个是字符串(比如键),另一个是整数计数(比如值)。在添加元素时检查它是否已经存在,如果是,则简单地增加计数,否则将元素添加为计数为 1 的新二叉树节点。

于 2012-04-08T21:21:16.013 回答
2

很难回答家庭作业问题...

因此,您的节点显然会包含它所代表的单词。当您插入一个新词时,您会创建节点,但在此之前,您会搜索该词。如果您的树中已经存在该单词的节点,只需检索该节点并在其中增加一个计数器。

public class MyNode
{
   String word;
   Integer counter;
}

得到它?:)

于 2012-04-08T21:20:50.200 回答
0

将单词添加到树时如何跟踪单词的频率

1)除了 a 的data leftright成员之外,每次尝试在树中添加现有单词时, TreeNode添加另一个成员并递增 1。count

2)您可以使用单独的哈希表来保留单词和出现的映射。如果单词存在于哈希表中,只需增加计数。如果它不存在,则将其添加到树中。由于哈希表,这需要额外的空间

于 2012-04-08T21:20:27.000 回答
0

使用 HashMap,用 String、Integer 填充。遍历文本中的单词,如果尚未添加,则将其放入 Integer(occurrence) == 1 的地图中。如果之前添加过,则将 Integer 增加 1。

处理完所有文本后,您可以使用 String 和 Integer 填充对象列表,根据它们的 compareTo 方法对它们进行排序。

于 2012-04-08T21:23:21.877 回答
0

以防有人需要。

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)

这里的例子

于 2019-01-25T15:42:33.437 回答