Двоичное дерево поиска toString Java

Question

Я применил метод toString для BST, но выглядит так, как будто работает, но не стабилен. , например для этого дерева toString работает отлично: , но для этого, это неправильно

кто может помочь, что происходит?

@Override 
    public String toString() { 
     return "(" + toStringB(new StringBuilder(), root()).toString() + ")"; 
    } 

    private StringBuilder toStringB(StringBuilder string, Node<E> node) { 
     if (node != null) { 
      string.append(node.getElement()); 
      if (left(node) != null) { 
       toStringB(string.append(" ("), left(node)); 
      } 
      if (right(node) != null) { 
       toStringB(string.append(", "), right(node)); 
       string.append(')'); 
      } 
     } 
     return string; 
    } 

Answer 1

Ваша проблема заключается здесь:

 if (left(node) != null) { 
      toStringB(string.append(" ("), left(node)); 
     } 
     if (right(node) != null) { 
      toStringB(string.append(", "), right(node)); 
      string.append(')'); 
     } 

Если у вас есть левый узел, но не имеет права узел, вы будете добавлять (left. Если у вас есть правый узел без левого узла, вы добавите , right). Это дает вам неправильные совпадающие круглые скобки и запятые запятые.

Я хотел бы отметить, ваши "отлично работает" пример на самом деле не является правильным, либо:

(10 (7 (3 (2, 5), 9), 10, 30 (11 (10)))

Давайте спрячем узлы под 7 и 30:

(10 (7 (...), 10, 30 (...))

Ваш корневой узел 10 имеет 3 детей 7, 10 и 30. Это не двоичное дерево!

О, и несбалансированные круглые скобки.