java - Java 中的 BinaryTree - 构建单词并显示它
问题描述
我对大学有一个我想不通的问题。我有一个文件,其中包含构建二叉树的说明
r a
rr b
rl c
rrr h
rrl i
rlr j
rll k
d
l e
ll f
lr g
lll l
llr m
lrl n
lrr o
r - 右,l - 左,要打印的内容。“d”是根
我加载文件,将每一行分成指令和一个值,但我不知道下一步该做什么——我被卡住了。
我必须构建一棵树并使用递归来解决它......并打印来自树状“hbad”、“kcad”、“lfed”等的所有单词......
我现在的代码:
import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
int i = 0;
String key[] = new String[2];
String root = "";
ArrayList<String> lineFile = new ArrayList<String>();
Scanner scan = null;
try {
scan = new Scanner(new File("tree.txt"));
} catch (FileNotFoundException e) {
e.printStackTrace();
}
while (scan.hasNextLine()) {
lineFile.add(scan.nextLine());
}
for (i = 0; i < lineFile.size(); i++) {
if (lineFile.get(i).length() > 1) {
key = lineFile.get(i).split(" ");
System.out.print(key[0] + " " + key[1]);
} else {
root = lineFile.get(i);
}
System.out.println(" " + lineFile.get(i).length());
}
System.out.println(root);
}
}
请帮助...任何示例实现,链接或其他...
解决方案
如上所述,二叉树由一组节点组成。每个节点有两个子节点,left 和 right,它们也是节点。一个简单的节点实现可能如下所示:
public class BinaryTreeNode<T> {
private final T value;
private BinaryTreeNode<T> left;
private BinaryTreeNode<T> right;
public BinaryTreeNode(T value) {
this.value = value;
}
public T getValue() {
return value;
}
public BinaryTreeNode<T> getLeft() {
return left;
}
public void setLeft(BinaryTreeNode<T> left) {
this.left = left;
}
public BinaryTreeNode<T> getRight() {
return right;
}
public void setRight(BinaryTreeNode<T> right) {
this.right = right;
}
}
这个版本是通用的,但您可以将 value 设置为 String 并让生活更轻松。从根值创建树的基础:
BinaryTreeNode<String> tree = new BinaryTreeNode<>(root);
解析您的输入并将其添加到树中比较棘手。为了简化一点,我创建了一个新的指令类,每行的两个部分(位置和值)拆分。为了方便起见,我创建了一个内部类(不需要 getter/setter),但这不是必需的:
private class Instruction {
String node;
String value;
public Instruction(String node, String value) {
this.node = node;
this.value = value;
}
}
创建指令列表:
List<Instruction> instructions = new ArrayList<>();
并将其填充到您的循环中:
instructions.add(new Instruction(key[0], key[1]));
现在进行递归加载。这可能不是最好的解决方案,但它有效:
private void buildSubTree(BinaryTreeNode node, List<Instruction> instructions) {
// Get the left branch
List<Instruction> left = instructions.stream()
.filter(i -> i.node.startsWith("l"))
.collect(Collectors.toList());
// Get the right branch
List<Instruction> right = instructions.stream()
.filter(i -> i.node.startsWith("r"))
.collect(Collectors.toList());
// Find the first left instruction
Instruction firstLeft = left.stream().filter(i -> i.node.length() == 1).findFirst().orElse(null);
// Find the first right instruction
Instruction firstRight = right.stream().filter(i -> i.node.length() == 1).findFirst().orElse(null);
if (firstLeft != null) {
// Set the left child
node.setLeft(new BinaryTreeNode(firstLeft.value));
// Find left children by reducing instruction node String (remove first character)
List<Instruction> leftChildren = left.stream().map(i -> new Instruction(i.node.substring(1), i.value)).collect(Collectors.toList());
// Recursively build left branch
buildSubTree(node.getLeft(), leftChildren);
}
if (firstRight != null) {
// Set the right child
node.setRight(new BinaryTreeNode(firstRight.value));
// Find right children by reducing instruction node String (remove first character)
List<Instruction> rightChildren = right.stream().map(i -> new Instruction(i.node.substring(1), i.value)).collect(Collectors.toList());
// Recursively build right branch
buildSubTree(node.getRight(), rightChildren);
}
}
构建树:
buildSubTree(tree, instructions);
该方法将在给定节点(第一次调用中的根节点)下构建两个子树,并使用每个子节点和每一侧的简化指令集递归调用自身。可以在此处进行一些改进,并使指令类更具功能性以提供帮助。
从列表中构建单词更容易:
private List<String> buildWordsFromTreeLeafUp(BinaryTreeNode<String> startNode) {
// List of words to return
List<String> words = new ArrayList<>();
// First populate the list with words from each child branch
if (startNode.getLeft() != null) {
words.addAll(buildWordsFromTreeLeafUp(startNode.getLeft()));
}
if (startNode.getRight() != null) {
words.addAll(buildWordsFromTreeLeafUp(startNode.getRight()));
}
// Add the startNodes value to each word
words = words.stream().map(s -> s + startNode.getValue()).collect(Collectors.toList());
// Add the value as a word of it's own
words.add(startNode.getValue());
return words;
}
我敢打赌,这不是最优雅的实现,但它完成了工作。
如果您只想要完整长度(4 个字母)的单词,这里是单词构建方法最后一部分的替代方法:
if (words.isEmpty()) {
// Add the value as a word of it's own
words.add(startNode.getValue());
} else {
// Add the startNodes value to each word
words = words.stream().map(s -> s + startNode.getValue()).collect(Collectors.toList());
}
编辑
上面的最后一个代码块可以替换 buildWordsFromTreeLeafUp() 中的等效行。这是它的工作原理:
- 如果当前节点是叶子节点(即在没有子节点(左或右)的分支末端的节点,那么此时单词列表将为空。如果是,我们添加 this 的值(字母)节点作为一个词。
- 如果列表中已经有单词,则意味着至少有一个子节点。在这种情况下,我们不会将当前字母添加为新单词。相反,我们将当前字母附加到列表中已经存在的每个单词的末尾。这样,当递归一次返回一步时,我们只写完整的四个字母单词。
该方法写入所有单词,一次一个字母,但针对每个单词。
在上面的第一个实现中,我们也将当前字母添加为新单词。这样,除了所有 4 个字母的单词之外,我们还将获得所有 3 个和 2 个字母的单词(从树的中间某处开始)以及一个仅包含根元素的 1 个字母的单词 ('d')。
推荐阅读
- hash - 如何按出现的顺序获取哈希键
- airflow - 新鲜气流服务器未执行示例任务
- pine-script - 将 RSI 的 SMA 和 MA 绘制在一起
- google-analytics - GA 网页浏览量和屏幕浏览量有什么区别?
- java - Apache-poi Java:如何更改 WORD 文档中列表编号的字体名称和大小?
- javascript - 使用 HTML5 时必需的属性不起作用?
- python - 如何从一个表中选择 id 并插入/更新到另一个表
- python - 获取驱动程序的硒问题
- r - 将常量从逻辑恢复为在输出中呈现
- asp.net-core - ASP.NET Core 3.1 Web 应用程序在 ISS 上的 ANCM 进程内启动失败