Блог

В качестве упражнения по программированию мне нужно переписать некоторые существующие методы и классы, которые составляют двоичное дерево. (Сигнатуры методов и конструкторы должны оставаться неизменными). Почему-то я действительно не понимаю, что я здесь сделал.

Должен ли метод toString быть общедоступным, потому что он перезаписывает метод toString класса объекта? И как я могу избежать возврата нулей?

Вот код, к которому я пришел до сих пор:

Класс дерева

 Node root = null;

void addNode(int val) {
        Node newNode = new Node(val);
        root = newNode.addNode(root, val);
    }
  

Класс узла

 Node(int val) {
    val = val;
    left = null;
    right = null;
}

Node addNode(Node focusNode, int newNodeVal) {

    if (focusNode == null)
        return this;
    if (newNodeVal == focusNode.val)
        return focusNode;
    if (newNodeVal < focusNode.val)
        focusNode.left = this.addNode(focusNode.left, newNodeVal);
    else
        focusNode.right = this.addNode(focusNode.right, newNodeVal);

    return focusNode;
}

public String toString() {
    return this.left   " "   this.val   " "   this.right;
}
  

Используйте a StringBuilder для сохранения String представления узла и добавления данных дочерних узлов только в конкретный узел, которого нет null . Вот пример использования инфиксной навигации по узлам:

 public String toString() {
    StringBuilder sb = new StringBuilder();
    if (this.left != null) {
        sb.append(this.left);
        sb.append(' ');
    }
    sb.append(this.val);
    if (this.right != null) {
        sb.append(' ');
        sb.append(this.right);
    }
    return sb.toString();
}
  

 public String toString() {
    if(this.left==null){
        return this.val   this.right;
    } else if (this.right==null){
        return this.left   this.val;
    } else if (this.left == null amp;amp; this.right == null){
        return "";
    } else {
        return this.left   " "   this.val   " "   this.right;
    }
}
  

Вы присваиваете своим узлам значение null для запуска, и ваш метод toString предполагает, что они были изменены. Представьте дерево, в которое вы добавили 5, затем 3. Затем вызывается toString в дереве. Он попытается напечатать узел, 5 — значение, слева — 3, справа — null. При попытке вызвать

 return this.left   " "   this.val   " "   this.right;
  

Вы говорите, чтобы напечатать

 3 5 NULL
  

Вы можете инициализировать left и right с пустым Node объектом (с no val ), и когда вы его распечатаете, вы увидите null как val пустой Node :

 Node(Integer val) {
    this.val = val;
    left = new Node(null);
    right = new Node(null);
}
  

Это работает только в том случае, если вы создаете val Integer .

В вашем коде также есть ошибка: val = val останется this.val нетронутым. Вы должны использовать this.val = val;

toString() переопределяется, а не перезаписывается. Он должен возвращать a String , и вы не можете избежать null s, если ваш Node лист.

Что вы можете сделать, так это написать toString() так, чтобы иметь смысл иметь null val такое:

 public String toString() {
    return "#{val = "   val   ", left = "   left   ", right = "   right   "}"
}
  

Пожалуйста, обратите внимание, что это будет рекурсивно пересекать ваше дерево, поэтому для печати вашего дерева вам нужно только позвонить root.toString() .