錯誤的輸出：使用Java的二進制搜索樹實現

Question

我是Java的新手，我一直試圖實現一個BST，但程序只輸出最後插入的值。我對root_node指向哪些方面有錯嗎？以下是我的源代碼Tree.java和Node.java。

Tree.java

public class Tree { 

    private Node root_node; 

    public void Tree() { 
     this.root_node = null; 
    } 

    public void insertNode (int value) { 

     root_node = insertNode(root_node, value); 
    } 

    public Node insertNode (Node node, int insert_value) { 

     if (node == null) { 
      return (new Node(insert_value)); 
     } 
     else { 
      if (node.getNodeValue() < insert_value) 
       node = insertNode(node.getLeftNode(), insert_value); 
      else 
       node = insertNode(node.getRightNode(), insert_value); 

      return (node); 
     } 
    } 

    public void printNode() { 

     printNode(root_node); 
    } 

    public void printNode (Node node) { 

     if (node != null){ 

      System.out.print(node.getNodeValue() + " "); 

      printNode(node.getLeftNode()); 
      printNode(node.getRightNode()); 
     } 
    } 

    public static void main(String[] args) { 

     Tree tree = new Tree(); 

     tree.insertNode(54); 
     tree.insertNode(87); 
     tree.insertNode(11); 
     tree.insertNode(25); 

     tree.printNode(); 
    } 
} 

Node.java

public class Node { 

    private int node_value; 

    private Node left_node, right_node; 

    public Node(int root_value) { 

     this.node_value = root_value; 

     this.left_node = null; 
     this.right_node = null; 

    } 

    public int getNodeValue() { return (this.node_value); } 

    public Node getLeftNode() { return (this.left_node); } 

    public Node getRightNode() { return (this.right_node); } 
} 

的錯誤是我的源代碼只顯示最後插入沒有。在這種情況下是25。

Answer 1

insertNode的執行不正確。 你總是調用此方法：

root_node = insertNode(root_node, value); 

，然後如果你看一下方法：

if (node == null) { 
    return (new Node(insert_value)); 
} 
else { 
    if (node.getNodeValue() < insert_value) 
     node = insertNode(node.getLeftNode(), insert_value); 
    else 
     node = insertNode(node.getRightNode(), insert_value); 

    return (node); 
} 

在第一次通話中，第一if條件將匹配， 將創建一個新節點並將其分配給調用者中的root_node。

但是，在隨後的調用中， 會發生什麼？ 第一個if不匹配，因此將採取else塊。 但是，然後， 兩個分支重新分配方法的參數node。 因此，else方法的效果將保留在insertNode方法中，因此不會添加任何其他值。

除了重寫insertNode方法， 您還需要其他更改。例如， 目前沒有辦法設置或修改節點的左右節點。 您需要爲setters或構造函數添加一些方法。

例如，適當的制定者加入，這將工作：

public Node insertNode(Node node, int insert_value) { 
    if (node == null) { 
     return new Node(insert_value); 
    } 
    if (node.getNodeValue() < insert_value) { 
     node.setLeftNode(insertNode(node.getLeftNode(), insert_value)); 
    } else { 
     node.setRightNode(insertNode(node.getRightNode(), insert_value)); 
    } 
    return node; 
    } 

Answer 2

有什麼事發生的是，這樣的錯誤了：

您創建第一個打電話給你root_node（應該叫rootNode以下Java約定）。 然後你調用getLeftNode或getRightNode，但那些不存在，所以我想他們返回null。

 if (node.getNodeValue() < insert_value) 
      node = insertNode(node.getLeftNode(), insert_value); 
     else 
      node = insertNode(node.getRightNode(), insert_value); 

在第二次調用時返回null。

現在您的root_node再次爲空，結果您只有最後插入的值等等。所以這似乎是您調用打印時代碼只返回最後一個節點值的原因。

Answer 3

在你Tree類中，mehtod public Node insertNode (Node node, int insert_value)不正確，首德是這樣的：

 if (node.getNodeValue() < insert_value) { 
      Node left = insertNode(node.getLeftNode(), insert_value); 
      node.left_node = left; 
     } 

     else { 
      Node right = insertNode(node.getRightNode(), insert_value); 
      node.right_node=right; 
     } 

你應該保存由insertNode返回的新節點轉換爲當前節點的leftchild節點字段或rightchild節點字段，如果不是，則printNode將僅打印root節點並返回，因爲root節點的左側或右側子節點爲null。