Проблема с сортировкой в ​​двоичном дереве поиска

Question

У меня возникли проблемы с созданием этого дерева двоичного поиска. Идея состоит в том, что человек вводится, а затем сортируется по их имени.

Класс Я использую для человека является:

package Tree; 

public class Person { 
    private int age; 
    private String name; 
    private String gender; 

    public Person(String name, String gender,int age) { 
     this.age = age; 
     this.name = name; 
     this.gender = gender; 
    } 

    public int getAge() { 
     return age; 
    } 

    public void setAge(int age) { 
     this.age = age; 
    } 

    public String getName() { 
     return name; 
    } 

    public void setName(String name) { 
     this.name = name; 
    } 

    public String getGender() { 
     return gender; 
    } 

    public void setGender(String gender) { 
     this.gender = gender; 
    } 

    @Override 
    public String toString() { 
     return "Person [age=" + age + ", name=" + name + ", gender=" 
       + gender + "]"; 
    } 
} 

и дерево поиска:

package Tree; 

public class BinarySearchPerson { 

private boolean empty; 
private Person person; 
private static BinarySearchPerson left; 
private static BinarySearchPerson right; 

public BinarySearchPerson(Person person, BinarySearchPerson left, 
     BinarySearchPerson right) { 
    this.empty = false; 
    this.person = person; 
    this.left = left; 
    this.right = right; 
} 

public BinarySearchPerson() { 
    this.empty = true; 
} 

public boolean isEmpty() { 
    return empty; 
} 

public Person getPerson() { 
    if (isEmpty()) { 
     throw new IllegalStateException(
       "Trying to access root of an empty tree"); 
    } 
    return person; 
} 

public void setPerson(Person person) { 
    this.person = person; 
} 


public BinarySearchPerson getLeft() { 
    if (isEmpty()) { 
     throw new IllegalStateException(
             "Trying to access subtree of an empty tree"); 
    } 
    return left; 
} 


public void setLeft(BinarySearchPerson left) { 
    this.left = left; 
} 


/** 
* gets the right subtree of this node 
*/ 
public BinarySearchPerson getRight() { 
    if (isEmpty()) { 
     throw new IllegalStateException(
             "Trying to access subtree of an empty tree"); 
    } 
    return right; 
} 


public void setRight(BinarySearchPerson right) { 
    this.right = right; 
} 



public static BinarySearchPerson insert(Person person, BinarySearchPerson bt){ 
    int n = person.getName().compareTo(bt.person.getName()); 


    if (n<0){ 
     if(bt.getLeft().isEmpty() == true){ 
      bt.setLeft(new BinarySearchPerson(person,new BinarySearchPerson(),new BinarySearchPerson())); 
      return bt; 
     } 
     else{ 
      return insert(person, bt.getLeft()); 

     } 
    } 

    if (n>0){ 
     if(bt.getRight().isEmpty() == true){ 
      bt.setRight(new BinarySearchPerson(person,new BinarySearchPerson(),new BinarySearchPerson())); 
      return bt; 
     } 
     else{ 
      return insert(person, bt.getRight()); 
     } 
    } 
    else return bt; 


} 



} 

Проблема я получаю это сделать с помощью метода сортировки называемой вставки, вблизи дно. По какой-то причине он просто делает бесконечное количество ветвей слева или справа в зависимости от того, где имя будет сортироваться. Я не могу понять, где я ошибаюсь, поэтому любая помощь будет отличной.

Answer 1

Итак, я не вижу ваш код, который на самом деле вызывает вставку изначально, поэтому я не могу это проверить. Однако, что вы пытаетесь вернуть из метода insert? Разве это не новый созданный BinarySearchPerson? Если да, не должен ли вы возвращать вновь созданный элемент вместо того, на котором вы сейчас находитесь? Кроме того, новые BinarySearchPersons, которые вы создаете, не имеют ссылок на предыдущие. Вы должны должны сделать что-то вроде этого (сделать это также для правой стороны):

if (n<0){ 
    if(bt.getLeft().isEmpty() == true){ 
     BinarySearchPerson newLeft = new BinarySearchPerson(person,new BinarySearchPerson(),bt); 
     bt.setLeft(newLeft); 
     return newLeft; 
    } 
    else{ 
     return insert(person, bt.getLeft()); 

    } 
} 

Answer 2

Удалить статический модификатор из

частного статического BinarySearchPerson влево; частный статический BinarySearchPerson справа;

Каждый узел в дереве должен иметь свои левые и правые.