JavaScript二叉搜索树addItem方法失效问题排查求助

看起来你遇到的问题大概率出在递归方法addNode的赋值逻辑上——很多时候我们写递归添加节点时，容易忽略在递归调用后需要将返回的新节点赋值给当前节点的left或right指针，尤其是当当前节点的子节点为null的时候。

我先根据你描述的场景，补全并修正可能有问题的代码部分，你可以对比自己的实现看看：

首先是完整的Node类（补全你没写完的show方法）：

class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }

  show() {
    console.log(this.value);
  }
}

然后是二叉搜索树类的实现，重点看addItem和addNode的逻辑：

class BinarySearchTree {
  constructor() {
    this.root = null; // 根节点初始为空
  }

  addItem(value) {
    const newNode = new Node(value);
    // 如果根节点为空，直接赋值为新节点
    if (this.root === null) {
      this.root = newNode;
    } else {
      // 否则调用递归方法添加到合适位置
      this.addNode(this.root, newNode);
    }
  }

  addNode(currentNode, newNode) {
    // 新节点值小于当前节点，往左子树处理
    if (newNode.value < currentNode.value) {
      if (currentNode.left === null) {
        // 左子节点为空，直接赋值
        currentNode.left = newNode;
      } else {
        // 否则递归处理左子节点，直接修改currentNode的left指针即可
        this.addNode(currentNode.left, newNode);
      }
    } else {
      // 新节点值大于等于当前节点，往右子树处理
      if (currentNode.right === null) {
        currentNode.right = newNode;
      } else {
        this.addNode(currentNode.right, newNode);
      }
    }
  }

  // 可选：添加中序遍历方法验证节点是否正确添加
  inOrderTraverse(node = this.root) {
    if (node !== null) {
      this.inOrderTraverse(node.left);
      node.show();
      this.inOrderTraverse(node.right);
    }
  }
}

你可能犯的几个常见错误： #

• 根节点初始状态处理遗漏：如果你的addItem没有判断this.root === null的情况，直接调用addNode，那根节点永远不会被赋值，树一直是空的。
• 递归时未正确赋值子节点：另一种常见的写法是让addNode返回新节点，这时候就必须把递归结果赋值给currentNode.left或currentNode.right，否则新节点无法挂载到树上——这很可能就是你遇到的问题！比如正确的写法应该是：

  addNode(currentNode, newNode) {
    if (currentNode === null) {
      return newNode;
    }
    if (newNode.value < currentNode.value) {
      currentNode.left = this.addNode(currentNode.left, newNode);
    } else {
      currentNode.right = this.addNode(currentNode.right, newNode);
    }
    return currentNode;
  }
  

你可以测试一下上面的代码：

const bst = new BinarySearchTree();
bst.addItem(5);
bst.addItem(3);
bst.addItem(7);
bst.inOrderTraverse(); // 应该输出3、5、7

如果你的代码和上面的差异在于递归时没有赋值，那修正后应该就能正常添加节点了。

内容的提问来源于stack exchange，提问作者raiyan106