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 left和right成员之外，每次尝试在树中添加现有单词时， 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 回答