java - Java 中的二叉树 - 为什么我的树中有一个 "empty"节点(带有空白字符串)？

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，因此您不需要t 将第一个插入的节点分配给根。

只需删除它:

public BinaryTree() {
}