java - 在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= new TreeNode(s, null, null) 当 t==null 最初时，树返回到 buildTree 时保持为 null。但是，它似乎在插入方法中更新了树。我该如何解决这个问题？

此外，插入方法中的比较似乎有问题，因为它经常返回以下内容:

Exception in thread "main" java.lang.StackOverflowError

任何帮助将非常感激，因为我已经坚持这个问题很长一段时间了!

Answer 1

这是因为在Java中参数是通过引用传递的，所以当你这么做的时候

t = new TreeNode(s, null, null);

您正在为 t 分配一个新引用，而不是为收到的引用分配一个“值”

既然你要返回，如果你这样做，它应该会起作用

t = insert(t, current);

关于错误，您必须在某些情况下产生无限循环的调用插入，您应该能够在调试中检测到它