我是 Java 的新手,我想创建一个具有插入和前序遍历的二叉搜索树类,但是当我完成插入时,根对象仍然为 null,并且编译器在前序遍历期间抛出 NullPointerException。
我的节点类:
class Node {
int info;
Node left;
Node right;
public Node() {
info = 0;
left = null;
right = null;
}
Node(int x) {
info = x;
left = null;
right = null;
}
}
我的二叉搜索树类:
public class BinarySearchTree {
private Node root;
public BinarySearchTree() {
root = null;
}
private void insertPrivate(Node node, int x) {
if(node == null) {
node = new Node(x);
}
else {
if(x < node.info) {
insertPrivate(node.left, x);
}
else if (x > node.info) {
insertPrivate(node.right, x);
}
}
}
public void insert(int x) {
insertPrivate(root, x);
}
private void preorderPrivate(Node node) {
if(node != null) {
System.out.println(node.info);
preorderPrivate(node.left);
preorderPrivate(node.right);
}
}
public void preorder() {
preorderPrivate(root);
}
public static void main(String[] args) {
BinarySearchTree t = new BinarySearchTree();
t.insert(12);
t.insert(13);
t.preorder();
}
}
最佳答案
问题是对这段代码中 Java 引用的误解。
private void insertPrivate(Node node, int x) {
if(node == null) {
node = new Node(x);
}
....
Java 引用按值传递到函数参数中。
让我举个例子来说明一下。
Node root = new Node(x);
// root == Node(x);
doSomething(root);
// Pass Node(x) into function;
void doSomething(Node node) {
// root == Node(x);
// node == Node(x);
node = new Node(y); // This updates node but not root
// root == Node(x);
// node == Node(y);
}
您将不得不重组您的程序。一种方法是让 insertPrivate
返回一个 Node
并将该值分配给 root。它不是最有效的,但它会起作用。
public void insert(int x) {
root = insertPrivate(root, x);
}
private Node insertPrivate(Node node, int x) {
if(node == null) {
node = new Node(x);
}
else {
if(x < node.info) {
node.left = insertPrivate(node.left, x);
}
else if (x > node.info) {
node.right = insertPrivate(node.right, x);
}
}
return node;
}
关于java - 二叉搜索树插入 - 根保持为空,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/30802839/