二进制搜索树 - 插入

Question

给出一个指向二叉搜索树根的指针和一个要插入树中的值。将此值插入二进制搜索树中的适当位置，并返回更新的二叉树的根。你只需要完成这个功能。

我给了我的代码，但一个测试用例不起作用。这里是我的代码：

static Node Insert(Node root,int value){ 
    Node d =root; 
    Node q = new Node(); 
    q.left = null; 
    q.right=null; 
    q.data = value; 
    while(true){ 
     if(value<d.data){ 
      if(d.left==null){d.left = q; 
          return root; } 
      else{ 
       d= d.left ; 
      } 
     } 
     else{ 
      if(value>d.data){ 
       if(d.right==null){d.right=q; 
           return root;} 
       else d = d.right; 
      } 
     } 
    } 
} 

Answer 1

你缺少两种情况：value == d.data和空树。

value == d.data：在这种情况下，树不会以任何方式被修改，但是您的代码不会中断，并且会以无限循环结束。

简单的解决办法是在插入这些行while -loop：

if(value == d.data) 
    return root; 

，其中树是空的情况下是相当实现特定的，所以很难提出这种情况下，任何解决方案。