我正在尝试使用递归Insert方法编写BST,但似乎我陷入了程序无法跳出的行中。
如果在从Main调用insert时对元素键进行了排序,则可以使用,如果对它们不进行排序,则不起作用,我无法弄清楚为什么。
public static void main(String[] args) {
BST bst = new BST();
bst.insert(2,"Val_0");
bst.insert(1,"Val_1");
}
public class BSTNode {
public int key;
public String val;
public BSTNode left,right,parent;
public BSTNode(int key,String val) {
this.key = key;
this.val = val;
this.left = new BSTNode();
this.right = new BSTNode();
this.parent = new BSTNode();
}
public BSTNode() {
// TODO Auto-generated constructor stub
}
}
public class BST {
private BSTNode root;
public BST() {
this.root = null;
}
public void insert(int key,String val) {
root = insertRec(new BSTNode(key,val));
}
private BSTNode insertRec(BSTNode node) {
if (root == null) {
root = node;
return root;
}
if (node.key < root.key) {
root.left = insertRec(root.left);
root.left.parent = root;
}if( node.key > root.key) {
root.right = insertRec(root.right);
root.left.parent = root;
}
return node;
}
}
错误:线程“ main”中的异常java.lang.StackOverflowError,调试器在node.key