二叉搜索树(BST)find方法if语句顺序错误致类型错误的原因

问题描述 #

我在给二叉搜索树（BST）实现find()方法时遇到了问题，原因是if语句的逻辑写错了。当使用下面两个独立的if语句时（不管这两行顺序如何），程序会抛出错误：TypeError: Cannot read properties of null (reading 'val')，但把第二个if改成else if就能正常运行，我搞不懂其中的原因。

报错时的核心代码片段：

if (val > current.val) current = current.right // 独立if会触发报错
if (val < current.val) current = current.left  // 独立if会触发报错

完整代码：

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

class BST {
  constructor() {
    this.root = null;
  }

  insert(val) {
    let newNode = new Node(val)
    if (!this.root) {
      this.root = newNode
      return this;
    }

    let current = this.root
    while (true) {
      if (val === current.val) return undefined
      if (val < current.val) {
        if (current.left === null) {
          current.left = newNode
          return this;
        } else {
          current = current.left
        }
      }
      if (val > current.val) {
        if (current.right === null) {
          current.right = newNode
          return this;
        } else {
          current = current.right
        }
      }
    }
  }

  find(val) {
    if (!this.root) return false

    let current = this.root
    while (current) {
      if (val === current.val) return true
      console.log(current.val)
      if (val > current.val) current = current.right // 独立if逻辑
      if (val < current.val) current = current.left  // 独立if逻辑
    }
    return false
  }
}

let tree = new BST();
console.log(tree.insert(10));
console.log(tree.insert(5));
console.log(tree.insert(13));
console.log(tree.insert(11));
console.log(tree.insert(2));
console.log(tree.insert(16));
console.log(tree.insert(7));

console.log(tree.find(333))

问题原因与解决办法 #

为什么两个独立if会报错？ #

当使用两个独立的if语句时，第一个if执行后可能会把current赋值为null，这时第二个if再去访问current.val就会触发报错。

拿查找333的过程举例：

1. 初始current是根节点10，333>10，current变成13（10的右子节点）。
2. 第二个if判断333<13？不成立，current保持13，进入下一轮循环。
3. current是13，333>13，current变成16（13的右子节点）。
4. 第二个if判断333<16？不成立，current保持16，进入下一轮循环。
5. current是16，333>16，current变成null（因为16没有右子节点）。
6. 此时第二个if语句会执行val < current.val的判断，但current已经是null，访问null.val直接抛出TypeError。

为什么换成else if就正常？ #

改成else if后，两个判断是互斥执行的：

• 只有当第一个if（val > current.val）不成立时，才会执行else if的判断。
• 当current被赋值为null的情况不会触发后续判断——因为while循环的条件是while(current)，当current变成null时，循环直接退出，不会执行里面的判断逻辑。

修正后的find方法 #

把两个独立的if改成else if即可：

find(val) {
  if (!this.root) return false

  let current = this.root
  while (current) {
    if (val === current.val) return true
    console.log(current.val)
    if (val > current.val) {
      current = current.right
    } else if (val < current.val) {
      current = current.left
    }
  }
  return false
}

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