二叉搜索树递归-我需要使用setLeft和right吗？

Question

我已经创建了一个节点类，并且在二叉搜索树类中，我需要使用insert方法来插入节点。因此，我创建了一个新节点，并检查根是否为空，如果根为空，则该节点成为根节点。如果root不为null，则需要创建并调用一个从root开始并递归调用getLeft或getRight的递归方法。我只是在想，因为在我可以调用getLeft或getRight之前，确实需要先设置左右节点吗？如果是这样，我将在哪里使用setLeft正确？是插入节点方法还是递归方法？

Answer 1

class Node {
  Node left;
  Node right;
  Object data;

  public void insert(Object data) {
    // decide whether it goes to the left or to the right. 
    // assume the left:
    if (left != null) {
      left.insert(data);
    } else {
      left = new Node(data);
    }
  }
}

Answer 2

您可以尝试这样插入：

Node root;

class Node {
    Item data;
    Node left;
    Node right;

    public Node(Item e) {
        data = e;
    }
}

public void insert(Item item) {
    root = insert(root, item);
}

private Node insert(Node node, Item item) {
    if (node== null) {
        return new Node(item);
    } else if (item.compareTo(node.data) == 0) {
        return node;
    } else if (item.compareTo(node.data) < 0) {
        node.right = insert(node.right, item);
        return node;
    } else {
        node.left = insert(node.left, item);
        return node;
    }
}