0

我有一个如下列表。我想知道如何在 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;
        }
    }
}
4

1 回答 1

1

我不确定你想如何将你的列表变成树，因为我无法使用我能想到的任何明显的算法来重现你的两个例子。

按行填充，宽度优先

通常，我会从左到右填写一个级别，然后再继续下一个级别。对于您的示例输入，这将导致以下树：

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

如果这是您的解释，那么您可能最好维护对当前节点的引用，并且在将最后一个预期的子节点添加到它之后，从父节点切换到父节点，直到您到达仍然需要子节点的节点。

于 2012-09-28T06:37:17.103 回答