java二进制搜索树插入递归似乎总是返回null根

Question

嗨，我目前正试图用一些在线引用构建一个Java BST，但在插入过程中遇到了一个问题，因为在我尝试执行inOrder遍历后，我意识到它不会创建树，在一些尝试后，我在将根传递到插入方法时发现了问题。

我的节点类：

public class TreeNode
{
String m_key;
Object m_value;
TreeNode m_left;
TreeNode m_right;

//constructor
public TreeNode(String inKey, Object inVal)
{
if(inKey==null)
{
throw new IllegalArgumentException("Key cannot be null.");
}

m_key = inKey;
m_value = inVal;
m_left = null;
m_right = null;
}
}

我的插入方法：

public void insert(String key, Object data)
{
m_root = insertRec(m_root, key, data);
}
private TreeNode insertRec(TreeNode x, String key, Object val)
{
if(x == null)
{ 
x = new TreeNode(key,val);
}

int cmp = key.compareTo(x.m_key);
if(cmp<0)
{
x.m_left = insertRec(x.m_left, key, val);
}
else if(cmp>0)
{
x.m_right = insertRec(x.m_right, key, val);
}
else
{
x.m_value = val;
}

return x;     
}

打印根：

public void printRoot()
{
System.out.println("the root is: " + m_root.m_key);
}

我的主要课程：

public static void main(String[] args)
{
binaryTree bt = new binaryTree();
bt.insert("a", "data a");
bt.insert("b", "data b");
bt.insert("c", "data c");
bt.printRoot();
}

我得到了"；a"；作为打印root的root结果，我尝试打印root.m_left，它显示为null。有什么我可能错过的吗？

Answer 1

第一个if-statement之后的递归部分将始终执行。此外，假设它是BST，如果comp <= 0重复left:

if(x == null) { 
x = new TreeNode(key,val);
} else {  
int cmp = key.compareTo(x.m_key);
if(cmp <= 0) {
x.m_left = insertRec(x.m_left, key, val);
} else {
x.m_right = insertRec(x.m_right, key, val);
}
}
return x;