插入在二叉搜索樹

Question

我將在BST在下列方式：

private void BSTinsert(int toInsert){ 
     if(root==null){ 
      root = new Node(toInsert); 
      return; 
     } 
     Node tempRoot = root; 
     while(tempRoot!=null){ 
      if(tempRoot.data > toInsert){ 
       tempRoot = tempRoot.left; 
      }else{ 
       tempRoot = tempRoot.right; 
      } 
     } 
     tempRoot = new Node(toInsert); 
} 

但是，當我嘗試從根打印樹，它拋出一個空指針異常。但是，當我嘗試打印出tempRoot時，插入它打印正確，但沒有root和tempRoot相同的東西，因爲我已經等同他們？我在這裏錯過了什麼？

Answer 1

tempRoot是一個局部變量，所以當您將新節點賦值給它時，現有樹中沒有任何引用它的地方。新節點應鏈接到其父節點（通過left或right引用）。

目前您的代碼只能正確插入第一個節點，因爲該節點成爲根節點。

一個建議的校正（未測試）：

private void BSTinsert(int toInsert){ 
    if(root==null){ 
     root = new Node(toInsert); 
     return; 
    } 
    Node tempRoot = root; 
    while(tempRoot!=null){ 
     if(tempRoot.data > toInsert){ 
      if (tempRoot.left == null) { 
       tempRoot.left = new Node(toInsert); 
       return; 
      } else { 
       tempRoot = tempRoot.left; 
      } 
     }else{ 
      if (tempRoot.right == null) { 
       tempRoot.right = new Node(toInsert); 
       return; 
      } else { 
       tempRoot = tempRoot.right; 
      } 
     } 
    } 
}