java - Java 中的二叉树插入

Question

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

Answer 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

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