我有一个如下所示的列表。我想知道如何在 Java 中使用这种类型的列表创建二叉树。任何人都可以为这种类型的列表提供一些 Java 中的二叉树插入代码吗?
例如:
List 1: AND AND AND G M S T
二叉树将是:
AND
AND AND
G M S T
对于这个列表:
List 2: AND AND G M S
二叉树将是:
AND
AND S
G M
我尝试了以下插入方法:
public void insert(RDFQuery node, RDF leafValue) {
flag++;
if ((flag%2)!=0) {
if (node.left != null) {
flag--;
nodeStore=node.left;
leftFlag=1;
insert(node.left, leafValue);
}
else {
node.left = new RDFQuery(leafValue);
}
}
if ((flag%2)==0) {
if (leftFlag==1) {
node=nodeStore;
leftFlag=0;
}
if (node.right != null) {
flag--;
insert(node.right, leafValue);
}
else {
node.right = new RDFQuery(leafValue);
rightFlag=0;
}
}
}
最佳答案
我不确定您想如何将您的列表变成树,因为我无法使用我能想到的任何明显算法来重现您的两个示例。
按行填充,宽度优先
通常,我会从左到右填写一个级别,然后再继续下一级别。对于您的示例输入,这将导致以下树:
List 2: AND AND G M S
AND
/ \
AND G
/ \
M S
您可以通过多种方式实现这一点。一个是维护两个数字:您当前插入的行的索引(即深度)和该行中新叶子的索引。该行中该索引的位模式会告诉您左右子项的顺序,从根部开始,最高有效位。深度会告诉您必须考虑多少位,即哪一位是您必须处理的最重要的位。
前缀表示法
另一方面,您的元素名称表明其中一些元素具有固定的数量。我认为 AND
在所有情况下都是二元运算符,而简单符号可能是无效的。但是,通过这种解释,您的第一个示例将产生不同的列表:
AND
/ \
AND AND
/ \ / \
G M S T
AND ( AND ( G, M ), AND ( S, T ) )
List 1: AND AND G M AND S T
如果这是您的解释,那么您可能最好维护对当前节点的引用,并且在将最后一个预期的子节点添加到它之后,从一个父节点切换到另一个父节点,直到您到达一个仍然需要子节点的节点。
关于java - Java 中的二叉树插入,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12631934/