Бинарное дерево в Java - почему в моем дереве есть «пустой» узел (с пустой строкой)?

Question

По сути, моя проблема с моим кодом заключается в том, что где-то в его реализации он создает пустой узел, который затем вставляется в мое двоичное дерево.Этот узел существует, так как мой метод sizeOfTree считает его таким.Код работает просто отлично, единственная проблема - это узел.Итак, здесь я определил TreeNode, на основе которого построено двоичное дерево:

    package hr.fer.oop.lab1.prob6;

    public class TreeNode {
    TreeNode left=null;
    TreeNode right=null;
    String data;
    public TreeNode(String data) {
    this.data=data;
    }
    }

А вот и все остальное:

package hr.fer.oop.lab1.prob6;
import hr.fer.oop.lab1.prob6.TreeNode;
public class BinaryTree {
TreeNode root;
public BinaryTree() {
TreeNode node = new TreeNode("");
root=node;
}
public void insert (String data) {
    if (this.root==null) {
        this.root=new TreeNode(data);
        return;
    }
    else {
    TreeNode node = this.root;
    TreeNode parent = new TreeNode("");
    while(node!=null) {
        parent = node;
        if (node.data.compareTo(data)<=0) {
            node=node.left;
        }
        else{
            node=node.right;
        }
    }
        if (parent.data.compareTo(data)<=0) {
            parent.left=new TreeNode(data);
        }
        else {
            parent.right=new TreeNode(data);
        }
    }
    return;
}

private boolean subTreeContainsData(TreeNode node, String data) {
    if ((node.data).compareTo(data)<1E-15) return true;
    TreeNode temp=new TreeNode("");
    temp=node;
    if((temp.left.data).equals("")&&(temp.right.data).equals("")) return false;
    return (subTreeContainsData(temp.left, data)||subTreeContainsData(temp.right, data));
}
private boolean containsData(String data) {
    return subTreeContainsData(root, data);
}
private int sizeOfSubTree(TreeNode node) {
    if (node==null) return 0; 
    return 1 + sizeOfSubTree(node.left) + sizeOfSubTree(node.right);
}
public int sizeOfTree() {
    return sizeOfSubTree(root);
}
private void writeSubTree(TreeNode node) {
    if (node!=null) {
    writeSubTree(node.left);
    System.out.println(node.data);
    writeSubTree(node.right);
    }
    return;
}
public void writeTree() {
    writeSubTree(root);
}
private void reverseSubTreeOrder(TreeNode node) {
    if (node==null) return;
    TreeNode helpNode;
    helpNode=node.left;
    node.left=node.right;
    node.right=helpNode;
    reverseSubTreeOrder(node.left);
    reverseSubTreeOrder(node.right);
}
public void reverseTreeOrder() {
    reverseSubTreeOrder(root);
}
public static void main (String[] args) {
    BinaryTree tree = new BinaryTree();
    tree.insert("Jasna");
    tree.insert("Ana");
    tree.insert("Ivana");
    tree.insert("Anamarija");
    tree.insert("Vesna");
    tree.insert("Kristina");

    System.out.println("Writing tree inorder:");
    tree.writeTree();
    tree.reverseTreeOrder();
    System.out.println("Writing reversed tree inorder:");
    tree.writeTree();
    int size=tree.sizeOfTree();
    System.out.println("Number of nodes in tree is "+size+".");
    boolean found = tree.containsData("Ivana");
    System.out.println("Searched element is found: "+found);
}
}

Большое спасибо за любую предоставленную помощь.

Answer 1

Вы создаете пустое TreeNode в своем конструкторе и делаете его корнем дерева:

public BinaryTree() {
    TreeNode node = new TreeNode("");
    root=node;
}

Позже, в вашем insert методе, ваше if (this.root==null) условие всегда false, поэтому вы не можете назначить первый вставленный узел корню.

Просто удалите его:

public BinaryTree() {
}