在Java中构建字符串的二进制搜索树

Question

我正在尝试构建一棵字符串树，但是似乎遇到了一些我不确定如何解决的问题。

   public static TreeNode buildTree(TreeNode t, String s)
   {
      int size = s.length();
      while(size > 0)
      {
         String current = s.substring(0,1);
         insert(t, current);
         s = s.substring(1);
         size--;
      }
      System.out.println("This is the tree:");
      System.out.println(t);
      return t;
   }
     	/**************************
   	Recursive algorithm to build a BST: if the node is null, insert the 
   	new node. Else, if the item is less, set the left node and recur to 
   	the left. Else, if the item is greater, set the right node and recur 
   	to the right.   
   	*****************************/
   private static TreeNode insert(TreeNode t, String s)
   {  
      if(t == null)
      {
         t = new TreeNode(s, null, null); 
         return t;
      }
      else
      {
         String s1 = (String) t.getValue();
         String s2 = s;
         //this line below is problematic
         if(s2.compareTo(s1) == -1 || s2.compareTo(s1) == 0) //s2 comes before s1
         {
            t.setLeft(new TreeNode(s2));
            insert(t.getLeft(), s);
         }
         else
         {
            t.setRight(new TreeNode(s2));
            insert(t.getRight(), s); 
         }
      }
      return t;
   }

这里是类TreeNode：

class TreeNode 
{
   private Object value; 
   private TreeNode left, right;
   
   public TreeNode(Object initValue)
   { 
      value = initValue; 
      left = null; 
      right = null; 
   }
   
   public TreeNode(Object initValue, TreeNode initLeft, TreeNode initRight)
   { 
      value = initValue; 
      left = initLeft; 
      right = initRight; 
   }
   
   public Object getValue()
   { 
      return value; 
   }
   
   public TreeNode getLeft() 
   { 
      return left; 
   }
   
   public TreeNode getRight() 
   { 
      return right; 
   }
   
   public void setValue(Object theNewValue) 
   { 
      value = theNewValue; 
   }
   
   public void setLeft(TreeNode theNewLeft) 
   { 
      left = theNewLeft;
   }
   
   public void setRight(TreeNode theNewRight)
   { 
      right = theNewRight;
   }
}

当我从buildTree方法调用insert方法时，我尝试t = new TreeNode（s）;或当t == null时，t = new TreeNode（s，null，null），当树返回到buildTree时，树保持为空。但是，似乎在insert方法中更新了树。我该如何解决这个问题？

而且，在insert方法中我的compareTo似乎有问题，因为它经常返回以下内容：

线程“主” java.lang.StackOverflowError中的异常

任何帮助都会非常感激，因为我已经坚持了很长时间！

Answer 1

这是因为参数是通过Java中的引用传递的，所以当您这样做时>>

t = new TreeNode(s, null, null);
您正在为t分配新的引用，而不是为接收到的引用分配“值”

由于您正在返回t，如果您这样做，它将正常工作

t = insert(t, current);
关于错误，在某些情况下必须产生无限次插入调用循环，您应该能够在调试时检测到它

Answer 2

1. 建议设计一个Class：TreeBuilder来构建字符串的树，然后返回它的head（一棵树必须有一个headNode。将递归方法隔离到另一个util类：TreeMaker