错误的输出：使用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。