Java 中的二叉搜索树添加方法

Question

我有一段代码用于将节点插入 Java 中的二叉搜索树，例如：

public class BST {
private Node head;

public BST() {
    this.head = null;
}

public void add(int data, Node head) {
    if (head == null)
        head = new Node(data);
    else {
        if (data < head.data)
            add(data, head.left);
        else
            add(data, head.right);
    }
}

public void add(int data) {
    add(data, this.head);
}

public void preOrder(Node head) {
    if (head != null) {
        System.out.print(head.data + " ");
        preOrder(head.left);
        preOrder(head.right);
    }
}

public void preOrder() {
    preOrder(this.head);
}

public static void main(String[] args) {
    BST bst = new BST();
    for (int i = 0; i < 10; i++) {
        bst.add(i);
    }
    bst.preOrder();
}
}

为什么我运行程序没有打印出我的信息？谢谢你回答我的问题！！

Answer 1

递归 returns 时不更新 left/right 指针。此外，局部变量 head 与实例变量不同。因此，当方法 returns.

时，您创建的新节点将被丢弃。

这是一种方法。

私有 add 方法 returns 在递归时得到（重新）分配的更新节点 returns。

private Node add(int data, Node node) {
    if (node == null)
        return new Node(data);
    else {
        if (data < node.data)
            node.left = add(data, node.left);
        else
            node.right = add(data, node.right);
    }
   return node;
}

public void add(int data) {
    this.head = add(data, this.head);
}

Answer 2

还有一个选项：

  public void add(int data) {
    if(head == null) {
      this.head = new Node(data);
    }
    else {
      add(data, this.head);
    }
  }

  public void add(int data, Node node) {
    if(data < node.data) {
      if(node.left == null) {
        node.left = new Node(data);
      }
      else {
        add(data, node.left);
      }
    }
    else {
      if(node.right == null) {
        node.right = new Node(data);
      }
      else {
        add(data, node.right);
      }
    }
  }

Java 中的二叉搜索树添加方法

Binary Search Tree's add method in Java

java

binary-search-tree