二進制搜索樹 - 插入

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; 

，其中樹是空的情況下是相當實現特定的，所以很難提出這種情況下，任何解決方案。