Построение бинарного дерева поиска строк в 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, и я пытаюсь t = new TreeNode (s); или t = new TreeNode (s, null, null), когда t == null изначально, дерево остается нулевым, когда возвращается в buildTree. Тем не менее, кажется, обновить дерево в методе вставки. Как я мог решить эту проблему?

Кроме того, кажется, что проблема с моими CompareTo в методе вставки, потому что он часто возвращает это:

Исключение в потоке "main" java .lang.StackOverflowError

Любая помощь будет очень признательна, потому что я застрял на этом довольно долгое время!

Answer 1

1. Предложите, чтобы при разработке класса: TreeBuilder было построено дерево вашей строки, а затем возвращена его голова (у одного дерева должен быть headNode). Разделите метод рекурсии на другой используемый класс: Builder

class TreeBuilder{
    private TreeNode head = null;                 // head Node

    public TreeNode buildTree(String source) {
        for (int i = 0; i < source.length(); i++) {
            String current = String.valueOf(source.charAt(i));
            Builder.makeTree(head, current);
        }
        return this.head;
    }
}

2.Используйте класс Builder

class Builder{
    public static void makeTree(TreeNode head,String current) {
        if (head == null) {                 // make head first
            head = new TreeNode(current);
        }else {                             
            recurse(head, current);         // make body left
        }
    }

    public static void recurse(TreeNode temp, String current){
        if ( current.compareTo(temp.getValue()) < 1) {  // current <= tempNode
            if (temp.getLeft() != null) {               // tempNode has a smaller leftNode than itself
                recurse(temp.getLeft(), current);       // recurse left
            }else {
                temp.setLeft(new TreeNode(current));    // current smaller than tempNode
            }
        }else {                                         // current > tempNode
            if (temp.getRight() != null) {              // tempNode has a bigger rightNode than itselft
                recurse(temp.getRight(), current);      // resurse right
            }else {
                temp.setRight(new TreeNode(current));   // current bigger than tempNode
            }
        }
    }
}

Ключом к построителю вашего дерева является сравнение текущего символа с headNode до тех пор, пока один листовый узел или внутренний узел ， не пропустят ваш проблемный c блок。

• если ток меньше, чем tempNode ， вы должны повторить сравнение с помощью tempNode leftNode [если существует левый узел], поскольку leftNode меньше, чем tempNode, вам нужно проверить, какой из них является наименьшее между current и leftNode и т. д.)

• , а также, если ток больше, чем tempNode, вы должны вернуть правое значение также

Answer 2

Это потому, что параметры передаются по ссылке в Java, поэтому, когда вы делаете

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

, вы назначаете новую ссылку для t, а не присваиваете «значение» для полученной ссылки

Поскольку вы возвращаете t, оно должно работать, если вы делаете

t = insert(t, current);

Что касается ошибки, у вас должен быть какой-то случай, производящий бесконечный l oop вызовов для вставки, вы должны иметь возможность обнаружить это отладка