java 二叉搜索树插入递归似乎总是 return 空根

Question

你好我目前正在尝试使用一些在线参考构建一个 Java BST，但是我在插入过程中遇到了问题，因为我意识到在我尝试进行 inOrder 遍历后它没有创建树，经过一些尝试后，我发现将根传递到我的插入方法时出现问题。

我的节点class:

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);
}

我的主要class:

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();
}

我从打印 root 得到了“a”作为 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;

java 二叉搜索树插入递归似乎总是 return 空根

java Binary search tree insertion recursion seem to always return null root

java

binary-search-tree

dsa