我有一个 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 类来读取文件!
然后我想从文件的内容和一些规则递归地填充这棵树:
A "." means tack to left so the first part of the file would mean tack node with 'E' character to the Left of the root
A "-" means tack to right so the second line in the file would mean tack node with 'T' character to the Right of the root.
So "W .--" would mean tack node with 'W' from root One node to the left, then one node to the right then tack on to the right of that Node.
最终树看起来像:
tree http://i56.tinypic.com/339tuys.png
由于我是递归新手,因此在使用扫描仪读取文件时,我很难想象如何递归地填充树。
我是否必须在其他地方读取文件并将信息传递到递归方法中???
或者我可以直接用递归方法读取文件吗?这似乎不可能。
此外,您会使用什么作为基本案例,我很想使用 t.size() == 27,因为这是最终树的大小。
如有任何建议或意见,我们将不胜感激!!
谢谢!
最佳答案
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
}
}
<小时/>
希望以上两项都能发挥作用。
结果可能类似于this .
<小时/>递归通常用于 traversal和 binary search tree ,但这棵树更类似于 Trie ,字母表中只有 2 个字符(即 .
和 -
)。树的构造规则(左为.
,右为-
)使得不需要使用递归。
关于java - 递归填充树,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/5347172/