带有遍历的二叉搜索树空指针异常

Question

我正在用java实现一个二叉搜索树，递归地编写方法。我做了插入方法，现在我被困在第一种遍历方法上，即顺序方法。当我在测试代码中调用它时，在添加了一些元素 (tree.inorderTraversal( 后，我在递归 in order 方法中得到一个空指针异常，我不明白为什么。插入方法有问题吗？

public void insertInBinaryTree(E newItem)
{
BinaryTreeNode<E> node = new BinaryTreeNode<E>(newItem);
if (root == null) {
root = node;
} else {
insert(root, newItem);  
}
}
// Recursively insert a node containing newItem into a non-empty tree. Used
// by insertInBinaryTree
private void insert(BinaryTreeNode<E> treeNode, E newItem)
{
if (newItem.compareTo(treeNode.getItem()) < 0) {
if (treeNode.getLeftChild() != null) {
insert(treeNode.getLeftChild(), newItem);
}
else {
treeNode.setLeftChild(new BinaryTreeNode<E>(newItem));
}
}
else {
if (treeNode.getRightChild() != null) {
insert(treeNode.getRightChild(), newItem);
}
else {
treeNode.setRightChild(new BinaryTreeNode<E>(newItem));
}
}
}
// If the tree is not empty, initiates an inorder traversal. This should
// print all items in ascending order. If the tree is empty, just prints
// "Tree is empty"
public void inorderTraversal()
{
System.out.println("nInorder Traversal");
if (root == null) {
System.out.println("Tree is empty");
} else {    
inorder(root);
}

}
// Recursive inorder traversal of a non-empty tree. Used by
// inorderTraversal.
private void inorder(BinaryTreeNode<E> treeNode)
{
inorder(treeNode.getLeftChild());
System.out.print(treeNode.getItem());
inorder(treeNode.getRightChild());
}

Answer 1

在 inorder 方法中，由于其递归方法，第一个语句应该检查参数上的 null，如果是这样，它应该返回。否则，递归永远不会结束，并且在没有左子节点或右子节点时访问 treeNode.getLeftChild(( 或 treeNode.getRightChild(( 时会遇到 NPE。

Answer 2

您缺少空检查。它应该是

private void inorder(BinaryTreeNode<E> treeNode)
{
if(treeNode != null)
{
inorder(treeNode.getLeftChild());
System.out.print(treeNode.getItem());
inorder(treeNode.getRightChild());
}
}