0

我有一个 Java 类： BinaryTree< t > 我从文件中填充如下：

E .
T -
I ..
N -.
M --
A .-
W .--
R .-.
S ...
etc (to end of alphabit)

二叉树有：

setRight(BinaryTree) -sets the right element
setLeft(BinaryTree) -sets the left element   
setRootElement(t) -sets the root element
getRight() -gets the right element
getLeft()  -gets the left element 
getRootElement() -gets the root element of the node IE/ a Character
size() -returns the size of the tree

这些是给我的 BinaryTree 类中唯一可用的方法

所以我想做的是我想一个接一个地读取文件的每一行，得到字母和“莫尔斯电码”字符串。注意：我只能使用 Scanner 类来读取文件！

然后我想从文件的内容和一些规则中递归地填充这棵树：

一个 ”。” 表示向左定位，因此文件的第一部分意味着将带有“E”字符的节点定位在根的左侧

“-”表示向右定位，因此文件中的第二行表示将带有“T”字符的节点定位在根的右侧。

因此，“W .--”表示从根节点开始向左侧添加一个节点，然后向右侧添加一个节点，然后在该节点的右侧添加一个节点。

最后，树看起来像：

树 http://i56.tinypic.com/339tuys.png

由于我是 Recursion 的新手，因此在使用扫描仪从文件中读取文件时，我很难想象如何递归地填充树。

我是否必须在其他地方读取文件并将信息传递给递归方法？？？

或者我可以用递归方法直接读取文件吗？这似乎不可能。

此外，您将使用什么作为基本案例，我很想使用 t.size() == 27，因为这是最终树的大小。

任何建议或意见将不胜感激！！

谢谢！

4

1 回答 1

1 
Scanner sc = new Scanner(new File(...));
while (sc.hasNext()) {
  String letter = sc.next();
  String morse = sc.next();
  BinaryTree forPosition = theBinaryTree;
  for(int i = 0; i < morse.length(); i++) {
    if (morse.charAt(i) == '.') {
      if(forPosition.getLeft() == NULL) {
        forPosition.setLeft() = new BinaryTree();
      }
      forPosition = forPosition.getLeft();
    }
    else {
      // similar
    }
  }
  forPostion.setRootElement(letter);
}

一个奇怪的递归版本：

Scanner sc = new Scanner(new File(...));
while (sc.hasNext()) {
  String letter = sc.next();
  String morse = sc.next();
  findTheNode (theBinaryTree, letter, morse);
  }
  forPostion.setRootElement(letter);
}

findTheNode (BinaryTree node, String letter, String morse) {
  if (morse.length() == 0) {
    node.setRootElement(letter);
    return;
  } // found

  if (morse.charAt(0) == '.') {
    if (node.getLeft() == NULL) {
      node.setLeft() = new BinaryTree();
    }
    findTheNode (node.getLeft(), letter, morse.substring(1));
  }
  else {
    // similar
  }   
}

希望以上两项工作。

结果可能如下所示。

递归通常用于遍历和二叉搜索树，但这种树更类似于Trie，在字母表中只有 2 个字符（即.和-）。树的构造规则（.左，-右）使得没有必要使用递归。

于 2011-03-18T02:33:36.843 回答