java - 输出错误: Binary Search Tree implementation using Java

Question

我是 Java 新手，我一直在尝试实现 BST，但程序仅输出最后插入的值。我的 root_node 所指向的内容是否有误？以下是我的 Tree.java 和 Node.java 源代码。

树.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 block 。 但是之后， 两个分支都重新分配方法的 node 参数。 因此 else 方法的效果将保留在 insertNode 方法中，因此不会添加其他值。

除了重写 insertNode 方法之外， 您还需要其他更改。 例如， 目前还没有办法设置或修改节点的左右节点。 您需要为此添加某种方法，无论是通过 setter 还是构造函数。

例如，添加适当的 setter 后，这将起作用:

  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;
  }