关于向二叉搜索树添加节点的问题

Question

我正在编写一个二叉搜索树及其所有方法的代码，并且我已经运行跨过 add 方法，但是有一行让我感到困惑。

到目前为止，这是我所掌握的方法：

// 6) Methods: add

public boolean add(int newData) {
    if (!treeContains(newData)) return false;
    
    else {
        add(root, newData);
        nodeCount++;
        return true;    
    }
}

public Node add(Node node, int newData) {
    
    if (node == null) {
        node = new Node(newData, null, null);               // QUESTION
    }
    
    if (newData > node.data) {
        add(node.rightChild, newData);
        }
    else {                                                  // else if newData is less or equal to node data
        add(node.leftChild, newData);
        }
    return node;
}

在我写“// QUESTION”的地方，我知道如果我们到达那里，我们基本上已经站在某个节点的 node.leftChild 或 node.rightChild 中，所以当我们创建一个节点（在 // QUESTION 中）它会自动弹出吗？这有点令人困惑，因为感觉我应该指定新节点去那里，就像使用类似的东西：

node.leftChild == node;  // (or node.rightChild)

如果有人对此有好的看法，我将不胜感激。谢谢！

Answer 1

您传递给添加方法恕我直言的节点永远不应为空。您应该在调用此方法之前处理 null 情况。

我猜你需要这样的东西：

public Node add(Node node, int newData) {
  if (newData == node.data) {
    // ??? Not sure what do you need here, but it's there already.
    return node;
  }
  if (newData > node.data) {
    if (node.rightChild == null) {
      node.rightChild = new Node(newData, null, null);
      return node.rightChild;
    } else {
      return add(node.rightChild, newData);
    }
  } else {                                                  
    if (node.leftChild == null) {
      node.leftChild = new Node(newData, null, null);
      return node.leftChild;
    } else {
      return add(node.leftChild, newData);
    }
  }
}

顺便说一句。不确定这一行是否正确：

 if (!treeContains(newData)) return false;

如果节点已经存在，add() 方法 return 不应该为 false 吗？如果不存在则添加它？您确定需要在 IF 中取反吗？

关于向二叉搜索树添加节点的问题

Question about adding a node to a binary search tree

java

data-structures

tree

binary-search-tree